Алгоритм нахождения пересечения множеств - Алгоритмы

> Сдаётся, что алгоритмы у нас одинаковые
>
Ооочень сильно в этом сомневаюсь!!!

> Быстрее он именно благодаря отсутствию переменных состояния.
>
Говоришь так как будто бы проверил свою гипотезу!!!

> А также благодаря тому, что в каждом состоянии выполняются оптимальный для
> этого состояния набор операций сравнения.
>
Но чтоб добраться до этого "оптимального" кода ты проходишь через такие дебри!!!

> Представь, что вы разворачиваешь цикл от 1 до 10. Кода получается почти
> в 10 раз больше. Но работает он чуть быстрее.
>
Но явно не в этом случае!!!

> Примерно тоже происходит и здесь. Твоя реализация всегда крутится в
> большом цикле. А моя может покрутиться в маленьком и выйти (всё зависит от
> входных данных). До остального кода дело даже не дойдёт. А если и дойдёт,
> проход по всему коду эквивалентен нескольким циклам твоей реализации.
>
Вобщем похоже, что алгоритм, используемый, тобою сам по себе крайне корявый!!!
Пройдись пошагово по моему коду и увидишь, что в одном цикле выполняется тоько то что нужно и ничего больше!!!

> Возможно, если бы я не преследовал этой цели, код мог бы быть и компактнее при той же производительности.
>
Сравни свою и мою реализации на массивах!!!

Алгоритм, используемый, мною:

0    10    20    30    40    50    60    70
Входные массивы:
      |----|      |----|      |--------|  [10, 20, 30, 40, 50, 65]
   |----|         |-------------| |----|  [ 5, 15, 30, 53, 57, 65]
Результат:
      |-|         |----|      |-| |----|  [10, 15, 30, 40, 50, 53, 57, 65]

При продвижении по первому массиву устанавливаем/сбрасываем 0-й разряд переменной состояния, а для второго массива 1-й разряд!!! Если соответствующий разряд установлен, значит мы находимся в сегменте, а если сброшен, то перед сегментом!!! В результирующий массив должны попадать только те значения, при которых оба разряда установлены!!!

Рассмотрим на примере:

0    10    20
      |----|
   |----|

Начальное состояние (0) — находимся перед сегментами, сравниваем значения границ сегментов (10 и 5) и выбираем наименьшее значение — 5, находящееся во втором массиве!!! Продвигаемся вперёд на 1 элемент во втором массиве и устанавливаем 1-й разряд состояния — находимся перед сегментом первого массива и в сегменте второго!!! Сравниваем границы (10 и 15), выбираем наименьшую — 10, переходим на следующий элемент первого и устанавливаем 0-й разряд состояния — находимся внитри сегментов входных массивов, поэтому текущую границу (10) записываем в результирующий массив!!! Сравниваем 20 и 15, передвигаемся вперёд во втором массиве, сбрасываем (XOR) 1-й разряд состояния — вышли из сегмента второго (находимся перед сегментом второго), но так как в предыдущем состоянии оба разряда были установлены (3), то записываем текущую границу (15) в результат!!! Так как во втором массиве больше нет границ, то выполнение прекращается — результат вычислен: [10, 15]!!!

Единственное дополнение к вышесказанному: если значения границ равны, то передвигаемся вперёд в каждом из массивов, устанавливая/сбрасывая соответствующие флаги!!!

Вот код для исследования:

main()
{
 INT Segments1[] = {6, 10, 20, 30, 40, 50, 65};
 INT Segments2[] = {6,  5, 15, 30, 53, 57, 65};
 INT Result[9];
 Intersection((SEGMENTS*) &Result, (SEGMENTS*) &Segments1, (SEGMENTS*) &Segments2);
}

Posted via RSDN NNTP Server 1.9

"ukshish" <42305@users.rsdn.ru> wrote in message news:1208746@news.rsdn.ru...
> Сдаётся, что алгоритмы у нас одинаковые

Так оно и есть.

> (хотя я тоже не вникал в твою реализацию).

А зря.

> Быстрее он именно благодаря отсутствию переменных
состояния.

А он не быстрее. Оба способа реализации работают с одной скоростью. Твой более generic, поэтому компилятор не всегда его может красиво ассемблировать. На скорости не сказывается, 2N и есть 2N.

.

Posted via RSDN NNTP Server 1.9

Здравствуйте, Stanky, Вы писали:

>> Сдаётся, что алгоритмы у нас одинаковые
S>Ооочень сильно в этом сомневаюсь!!!
А жаль.

>> Быстрее он именно благодаря отсутствию переменных состояния.
S>Говоришь так как будто бы проверил свою гипотезу!!!
OK. Рассмотрим два варианта некого абстрактного кода.

1.

if( a > b ) state|= 1;
if( c > d ) state|= 2;
if( state == 3 ) return;

if( a > b ) if( c > d ) return;

Для меня очевидно, что второй вариант быстрее.

>> А также благодаря тому, что в каждом состоянии выполняются оптимальный для
>> этого состояния набор операций сравнения.
>>
S>Но чтоб добраться до этого "оптимального" кода ты проходишь через такие дебри!!!
Я также как и ты всего лишь сравниваю очередную границу интервала с предыдущей. Ничего более. Просто ты производишь это сравнение только в двух местах. У меня же в зависимости от State и PreviousState это сравнение может произойти в одном из многочисленных кусков кода.

>> Представь, что вы разворачиваешь цикл от 1 до 10. Кода получается почти
>> в 10 раз больше. Но работает он чуть быстрее.
S>Но явно не в этом случае!!!
Да, мой код вызывает большое недоверие. Признаюсь, я и сам не смог бы его понять. Его можно только написать самому. И побыстрее отладить. Иначе потом вникать будет очень тяжело.

>> Примерно тоже происходит и здесь. Твоя реализация всегда крутится в
>> большом цикле. А моя может покрутиться в маленьком и выйти (всё зависит от
>> входных данных). До остального кода дело даже не дойдёт. А если и дойдёт,
>> проход по всему коду эквивалентен нескольким циклам твоей реализации.
>>
S>Вобщем похоже, что алгоритм, используемый, тобою сам по себе крайне корявый!!!
S>Пройдись пошагово по моему коду и увидишь, что в одном цикле выполняется тоько то что нужно и ничего больше!!!
Увы, это не так. Помимо операций сравнения границ интервалов присутствуют операции с переменными состояния. Также, в моей реализации есть одна существенная оптимизация. Предположим, несколько подряд интервалов одного множества меньше очередной границы интервала второго множества. В этом случае мой алгоритм сравнивает только правые границы интервалов первого множества. И, пока они остаются меньше, сравнение левых границ пропускается. А твоя реализация никогда не пропускает сравнений.

S>Сравни свою и мою реализации на массивах!!!

S>Алгоритм, используемый, мною:
S>

S>0    10    20    30    40    50    60    70
S>Входные массивы:
S>      |----|      |----|      |--------|  [10, 20, 30, 40, 50, 65]
S>   |----|         |-------------| |----|  [ 5, 15, 30, 53, 57, 65]
S>Результат:
S>      |-|         |----|      |-| |----|  [10, 15, 30, 40, 50, 53, 57, 65]
S>

К сожаление, в этом примере как раз не встречается такого места, где очередное сравнение можно пропустить. Поэтому выигрыш моего алгоритма ограничится отсутствием переменных состояния.

ЗЫ Убедиться в своей правоте на практике, это так заманчиво. Но время, увы, слишком дорого.

> А жаль.
>
Как я понимаю ты работаешь с сегментом вцелом?

> OK. Рассмотрим два варианта некого абстрактного кода.

> 1.

>

> if( a > b ) state|= 1;
> if( c > d ) state|= 2;
> if( state == 3 ) return;
>

> 2.

>

> if( a > b ) if( c > d ) return;
>

> Для меня очевидно, что второй вариант быстрее.
>
Это было б так, если б не было ошибки в первом варианте (похоже, что ты не понял мой алгоритм), должно быть так:

if (a >= b)...
if (b <= a)...

Этим учитываются такие варианты взаимного расположения сегментов:

    |---|    |---|    |---|
|---|        |---|        |---|

И помимо установки состояния (которое, кстати происходит XOR'ом) при выполнении условия происходит перехёд вперёд на 1 элемент вперёд в соответствующем массиве!!!

> Просто ты производишь это сравнение только в двух местах. У меня же в
> зависимости от State и PreviousState это сравнение может произойти в одном
> из многочисленных кусков кода.
>
Всё это скакание по коду в разные его части слихвой перекроет затраты на проверку 2-х переменных!!!
Почему ты думаешь, что 2 переменные являются таким торможением?

> Помимо операций сравнения границ интервалов присутствуют операции с
> переменными состояния.
>
Потому что именно они дают ответ на вопрос: нужно заносить текущую границу в результат или нет?

> Также, в моей реализации есть одна существенная оптимизация. Предположим,
> несколько подряд интервалов одного множества меньше очередной границы
> интервала второго множества. В этом случае мой алгоритм сравнивает только
> правые границы интервалов первого множества. И, пока они остаются меньше,
> сравнение левых границ пропускается.
>
Мне кажется, что эта оптимизация в общем случае будет лишь тормозом, а не газом!!!

> А твоя реализация никогда не пропускает сравнений.
>
Потому что я не работаю с сегментом вцелом, а работаю лишь с набором границ, не разделяя их на правые и левые!!!

P. S. Можешь хотя бы переписать свой вариант для работы с массивом и сделать его более удобоваримым для понимания?

Posted via RSDN NNTP Server 1.9

Здравствуйте, Stanky, Вы писали:

>> А жаль.
S>Как я понимаю ты работаешь с сегментом вцелом?
Да, но это не принципиально. Опять абстрактный пример, не имеющий к данной задаче отношения:

1.

for( int i = 0; i < 2; i++ ) if( a[i] > b ) return;

if( a[0] > b ) return;
if( a[1] > b ) return;

>> OK. Рассмотрим два варианта некого абстрактного кода.

S>Это было б так, если б не было ошибки в первом варианте (похоже, что ты не понял мой алгоритм), должно быть так:
S>

S>if (a >= b)...
S>if (b <= a)...
S>

Пример был абстрактным. Алгоритм я понял.

>> Просто ты производишь это сравнение только в двух местах. У меня же в
>> зависимости от State и PreviousState это сравнение может произойти в одном
>> из многочисленных кусков кода.
>>
S>Всё это скакание по коду в разные его части слихвой перекроет затраты на проверку 2-х переменных!!!
S>Почему ты думаешь, что 2 переменные являются таким торможением?
Я на вскидку прикидываю число необходимых команд mov, cmp, jХХ и jmp.

>> Помимо операций сравнения границ интервалов присутствуют операции с
>> переменными состояния.
S>Потому что именно они дают ответ на вопрос: нужно заносить текущую границу в результат или нет?
Ответ на этот вопрос можно получить разными способами.

>> Также, в моей реализации есть одна существенная оптимизация. Предположим,
>> несколько подряд интервалов одного множества меньше очередной границы
>> интервала второго множества. В этом случае мой алгоритм сравнивает только
>> правые границы интервалов первого множества. И, пока они остаются меньше,
>> сравнение левых границ пропускается.
S>Мне кажется, что эта оптимизация в общем случае будет лишь тормозом, а не газом!!!
Уверен, это не так.

>> А твоя реализация никогда не пропускает сравнений.
S>Потому что я не работаю с сегментом вцелом, а работаю лишь с набором границ, не разделяя их на правые и левые!!!
Вот и именно. На все случаи пересечений у тебя универсальный ответ. Не кажется ли, что учитывая, какая граница левая, какая правая, некоторую предисторию можно выжать больше?

S>P. S. Можешь хотя бы переписать свой вариант для работы с массивом и сделать его более удобоваримым для понимания?
Эта задача не является приоритетной. К тому же, оптимизация по удобоваримости и скорости ведут почти в противоположные стороны.

Здравствуйте, SkyDance, Вы писали:

SD>А он не быстрее. Оба способа реализации работают с одной скоростью. Твой более generic, поэтому компилятор не всегда его может красиво ассемблировать. На скорости не сказывается, 2N и есть 2N.

А там не N+M, а от N/2 до N+M в зависимости от данных. И C поменьше (если VC++ с оптимизацией компилить, конечно).

Интересно бы твою реализацию посмотреть.

"ukshish" <42305@users.rsdn.ru> wrote in message news:1210574@news.rsdn.ru...
> А там не N+M, а от N/2 до N+M в зависимости от данных.

И у него так же.

> Интересно бы твою реализацию посмотреть.

Практически то же, что и у тебя, с той разницей, что вместо ветвлений — флаги как у Stanky. Ну и адаптация под наши специфические нужды.

.

Posted via RSDN NNTP Server 1.9

> Я на вскидку прикидываю число необходимых команд mov, cmp, jХХ и jmp.
>
Ну давай приведу тебе реальную картину:

            State ^= 2;
            ...
            State ^= 1;

соответствует

    xor    [State],2
    ...
    xor    [State],1

        if (State == 3 || PreviousState == 3)
            CombinedEdges[CombinedEdgesAmount++] = EdgeValue;
        PreviousState = State;

соответствует

    cmp    [State],3
    je     @@Save
    cmp    [PreviousState],3
    jne    @@NoSave

@@Save:
    mov    eax,[CombinedEdges]
    mov    ecx,[CombinedEdgesAmount]
    mov    edx,[EdgeValue]
    mov    [eax + ecx * 4],edx
    inc    [CombinedEdgesAmount]
@@NoSave:

    mov    eax,[State]
    mov    [PreviousState],eax

И что же мы имеем? 2 команды на изменение состояния из которых будет выполнена только 1 (2 в случае равенства границ), на проверку состояния уходит 4 команды в худшем случае, в лучшем 2 и на сохранение состояния ещё 2 команды!!! Итог: максимум 8 машинных команд будет выполнено "зря"!!! Что это такое огромное количество или может эти команды очень ресурсоёмки, чтоб так извращаться?

> Уверен, это не так.
>
А я абсолютно уверен в обратном

!!!
Ты б сперва проверил, прежде чем это утверждать — у меня был десяток реализаций этих вещей и в итоге я пришёл именно к тому, что привёл здесь!!!

> Вот и именно. На все случаи пересечений у тебя универсальный ответ. Не
> кажется ли, что учитывая, какая граница левая, какая правая, некоторую
> предисторию можно выжать больше?
>
Были у меня варианты с учётом этого — кроме головной боли они больше ничего не давали!!!
Именно универсальность иной раз и является самым оптимальным вариантом!!!
Например двусвязный список можно представить так, что предыдущим элементом первого элемента будет NULL и следующим последнего элемента тоже NULL!!! При такой организации в операциях вставки/удаления элемента в/из списка прийдётся проверять куда происходит вставка/удаление!!! Но от всех этих проверок можно избавиться (соответственно сократив время выполнения, размер исходника и программы в памяти), если предыдущим элементом первого будет последний, а следующим последнего первый!!! Так что иногда лучше и эфеективней привести всё в универсальный вид, чем изголяться для каждого по-отдельности!!! Разве RISC не выигрывает у CISC?

Posted via RSDN NNTP Server 1.9

Здравствуйте, Stanky, Вы писали:

S>Ну давай приведу тебе реальную картину:
S>

S>            State ^= 2;
S>            ...
S>            State ^= 1;
S>

S>соответствует
S>

S>    xor    [State],2
S>    ...
S>    xor    [State],1
S>

S>и
S>

S>        if (State == 3 || PreviousState == 3)
S>            CombinedEdges[CombinedEdgesAmount++] = EdgeValue;
S>        PreviousState = State;
S>

S>соответствует
S>

S>    cmp    [State],3
S>    je     @@Save
S>    cmp    [PreviousState],3
S>    jne    @@NoSave

S>@@Save:
S>    mov    eax,[CombinedEdges]
S>    mov    ecx,[CombinedEdgesAmount]
S>    mov    edx,[EdgeValue]
S>    mov    [eax + ecx * 4],edx
S>    inc    [CombinedEdgesAmount]
S>@@NoSave:

S>    mov    eax,[State]
S>    mov    [PreviousState],eax
S>

S>И что же мы имеем? 2 команды на изменение состояния из которых будет выполнена только 1 (2 в случае равенства границ), на проверку состояния уходит 4 команды в худшем случае, в лучшем 2 и на сохранение состояния ещё 2 команды!!! Итог: максимум 8 машинных команд будет выполнено "зря"!!!
Похоже, из этого я выигрываю только 2 xor'а и PreviousState=State. Еще в while (Edges1Amount && Edges2Amount) не по делу условие проверяется. Число границ чётное — проверять можно через одну (если всё переделать, разумеется).

S>Что это такое огромное количество или может эти команды очень ресурсоёмки, чтоб так извращаться?
Чтобы так извращаться, надо быть подлинным маньяком. А я таковым и являюсь.

>> Уверен, это не так.
S>А я абсолютно уверен в обратном

!!!
S>Ты б сперва проверил, прежде чем это утверждать — у меня был десяток реализаций этих вещей и в итоге я пришёл именно к тому, что привёл здесь!!!
Да, похоже твоя реализация минимальна по количеству кода (но не по скорости). Предполагаю, изначально написано было больше. Но в процессе оптимизации сократилось.
А проверять — кому это надо? Дискуссия куда интереснее. Не знаю, удалось ли мне зародить какие-то сомнения у тебя. Но я пока не столкнулся с достаточно весомыми для меня аргументами с твоей стороны. Аргументы выглядят так: "Твой алгоритм экономит на этом, значит он теряет на чём-то другом, и, в результате, получается только хуже" или "У меня тут пара лишних команд, ну это же пустяки." Может тебе перевести игру на моё поле? Найти в моём коде что-то неэффективное. Что он "корявый", я уже понял. Но процессор об него не спотыкается. (Подсказка)

> Похоже, из этого я выигрываю только 2 xor'а и PreviousState=State.
>
А куда же if (State == 3 || PreviousState == 3) девалось

?

> Еще в while (Edges1Amount && Edges2Amount) не по делу условие проверяется.
>
Ну ты наверное просто не точно выразился — эта проверка нужна и без неё никак, так как в цикле можно крутиться только когда в обоих массивах есть границы для рассмотрения!!!
На асме это будет выглядеть так:

    test    [Edges1Amount],0FFFFFFFFh
    jz      @@End
    test    [Edges2Amount],0FFFFFFFFh
    jz      @@End

    ;Тело цикла

@@End:

> Число границ чётное — проверять можно через одну (если всё переделать, разумеется).
>
Эта переделка обойдётся дороже (в смысле быстродействия) нежели проверять это в каждой итерации!!!

> Чтобы так извращаться, надо быть подлинным маньяком. А я таковым и являюсь.
>
Если программист извращенец, то он программист, обратное неверно. (с) не помню!!! Может ты просто извращенец

?

> Да, похоже твоя реализация минимальна по количеству кода (но не по
> скорости).
>
А она и не должна быть минимальна по скорости, совсем наоборот

!!!

> Не знаю, удалось ли мне зародить какие-то сомнения у тебя.
>
Нет, так как все эти извращения я самолично прошёл и убедился в их неэффективности и геморойности!!!

> Может тебе перевести игру на моё поле? Найти в моём коде что-то неэффективное.
>
Чтоб это сделать мне нужно понять твой алгоритм и разобраться в твоём коде, но ты сам согласился что это сделать нелегко

!!!
Если облегчишь мою участь, то гляну!!!

Posted via RSDN NNTP Server 1.9

> Похоже, из этого я выигрываю только 2 xor'а и PreviousState=State.
>
А куда же if (State == 3 || PreviousState == 3) девалось

    test    [Edges1Amount],0FFFFFFFFh
    jz      @@End
    test    [Edges2Amount],0FFFFFFFFh
    jz      @@End

    ;Тело цикла

@@End:

!!!
Если облегчишь мою участь, то гляну!!!

Posted via RSDN NNTP Server 1.9

Здравствуйте, Stanky, Вы писали:

>> Похоже, из этого я выигрываю только 2 xor'а и PreviousState=State.
S>А куда же if (State == 3 || PreviousState == 3) девалось

?
Вместо этого приходится больше сравнивать границы диапазонов между собой. Закон сохранения

>> Еще в while (Edges1Amount && Edges2Amount) не по делу условие проверяется.
>> Число границ чётное — проверять можно через одну (если всё переделать, разумеется).
S>Эта переделка обойдётся дороже (в смысле быстродействия) нежели проверять это в каждой итерации!!!
В моём варианте это бесплатно.

S>А она и не должна быть минимальна по скорости, совсем наоборот

!!!
А как же фраза "Потому что нужна именно скорость выполнения!!!" с фирменными тремя восклицательными знаками?

>> Может тебе перевести игру на моё поле? Найти в моём коде что-то неэффективное.
S>Чтоб это сделать мне нужно понять твой алгоритм и разобраться в твоём коде, но ты сам согласился что это сделать нелегко

!!!
Разбираться не обязательно. Например, можно посетовать на то, что в моём алгоритме вместо EdgeValue четыре переменных b1,e1,b2,e2. Если компилятор запихает EdgeValue в регистр, ситуация уже становится спорной.

	От:	Stanky
	Дата:	06.06.05 19:35
	Оценка:

	От:	SkyDance
	Дата:	07.06.05 06:09
	Оценка:

	От:	ukshish
	Дата:	07.06.05 07:06
	Оценка:

	От:	Stanky
	Дата:	07.06.05 08:01
	Оценка:

	От:	ukshish
	Дата:	07.06.05 08:55
	Оценка: