Быстрый поиск отстутствующих элементов в массиве

← →
@!!ex © (2008-02-22 21:03) [0]

Есть два массива.
"оригинал"(количество элементов M) и "зеркало"(количество элементов N).
Нужно найти все элементы, которые пристутствуют в массиве "зеркало" и отстутствуют в массиве "оригинал".
Причем максимально быстрым способом.
Перебор M*N раз не улыбается...

← →
Palladin © (2008-02-22 21:04) [1]

сортировка и двоичный/итерационный поиск тебе в руки

← →
@!!ex © (2008-02-22 21:10) [2]

> [1] Palladin © (22.02.08 21:04)

А сортировка - это сколько переборов? :)

← →
Johnmen © (2008-02-22 21:11) [3]

> А сортировка - это сколько переборов? :)

Нисколько.

← →
Palladin © (2008-02-22 21:15) [4]

:) ну ептыть, спросил... сортировка quicksort"ом вообще в переборах не измеряется... так же как и сортировка вставкой например :) одна только сортировка пузырком измеряется в переборах :)

← →
palva © (2008-02-22 21:20) [5]

Сортировать оба массива, а потом читать параллельно. Если текущие элементы обоих массивов совпадают, то в обоих массивах переходить к следующему элементу, если один из текущих меньше, то откладывать его как отсутствующий в другом массиве и читать этот массив дальше.

← →
@!!ex © (2008-02-22 21:24) [6]

> [4] Palladin © (22.02.08 21:15)

курю quicksort - раньше никогда с ним не работал.
А Вставка имеет другую проблему - постоянное перемещение данных.

← →
@!!ex © (2008-02-22 21:25) [7]

> [5] palva © (22.02.08 21:20)

Кстати, как вариант... тем более что можно сделать, чтобы если сортируется основной массив, зеркало было автоматически отсортированно.

← →
Palladin © (2008-02-22 21:28) [8]

> курю quicksort - раньше никогда с ним не работал.

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

← →
@!!ex © (2008-02-22 21:37) [9]

> [8] Palladin © (22.02.08 21:28)

нафиг никогд ане надо было.
и, кстати, я решил отказаться от quicksort"a в пользу поразрядной сортировки. Она таки быстрее. :)

← →
@!!ex © (2008-02-22 21:38) [10]

> [8] Palladin © (22.02.08 21:28)

В геймдеве нет задач, в которых у quicksort"a было бы преимущество перед поразрядной сортировкой.

← →
Johnmen © (2008-02-22 21:42) [11]

> поразрядной сортировки.

Что это, Бэрримор? (с)

← →
@!!ex © (2008-02-22 21:47) [12]

> [11] Johnmen © (22.02.08 21:42)

гугль знает.
сортировка позволяющая отсортировать данные за количество операци пропорциональному количеству элементов, но только числа, и скорость зависит от количества разрядов в числе. Word сортируется быстро.

← →
Palladin © (2008-02-22 21:48) [13]

> @!!ex © (22.02.08 21:38) [10]

чего чего ты казал? "в геймдеве" всегда были задачи сортировок узлов, вертексов, и вообще всего того что описывает точко-фигуру, иначе бы я не разрабатывал свою библиотеку ориентированную на 4 байта...

> Что это, Бэрримор? (с)

это плод воображения ATвсклвсклекс"а

← →
@!!ex © (2008-02-22 21:50) [14]

> чего чего ты казал? "в геймдеве" всегда были задачи сортировок
> узлов, вертексов, и вообще всего того что описывает точко-
> фигуру, иначе бы я не разрабатывал свою библиотеку ориентированную
> на 4 байта...

да. и это решается поразрядной сортировкой.. :)

рад, что ты узнал что-то новое и полезное... чувствую - растешь... точнее подрастаешь...

← →
@!!ex © (2008-02-22 21:53) [15]

Кстати, статья по этой сортировке, есть и на дельфимастере
http://www.delphimaster.ru/articles/dsort/index.html

← →
Palladin © (2008-02-22 21:53) [16]

> @!!ex © (22.02.08 21:47) [12]

ты болен... реально...

> сортировка позволяющая отсортировать данные за количество
> операци пропорциональному количеству элементов

это есть сортировка при вхождениии, то бишь у тебя есть нулевой массив элементов, входящий первый (а так же и второй и третий и четвертый) все сразу ставятся на свое место, бо бинарным/итеративным поиском при вхождении определяется сразу его место... сортировка эта оптимальна в случае жутко непостоянного набора данных... однако, геймдев всегда подразумевает статические наборы координат для объектов разного уровня детализации, но координаты всегда относительны... то есть станционарны...

← →
Palladin © (2008-02-22 22:00) [17]

> @!!ex © (22.02.08 21:53) [15]

ты с дуба рухнул? ты читал вообще в чем заключается этот метод? это приближение к итеративному методу. ключ сортировки замкнут в определенных рамках ладно... это все фигня... ты подумал о скорости обращения к элементу? ты подумал что будет в случае разрастания диапазона ключей? этот метод (как и любые специализированные) применяется в своем случае...

← →
@!!ex © (2008-02-22 22:27) [18]

> ты болен... реально...

доктор, на чем основано ваше утверждение?

> однако, геймдев всегда подразумевает статические наборы
> координат для объектов разного уровня детализации, но координаты
> всегда относительны... то есть станционарны...

геймдев не ограничивается лишь координатами, и честно говоря непонятно, как связаны LOD"ы с сортировкой... Как бы они по другому принципу работают...

> [17] Palladin © (22.02.08 22:00)

1) Стоит всеже цетировать верное сообщение...
2) Пример из геймдева, когда quicksort выигрывает - можно?

← →
@!!ex © (2008-02-22 22:28) [19]

Да и вообще было бы интересно посмотреть на ваши геймдев проекты...

← →
Lip © (2008-02-22 23:29) [20]

> @!!ex ©

Поражен...
Странно что вы не сталкивались с алгоритмом быстрой сортировки.

По сабжу. Задачу вам ответили как решать.

1) QuickSort("оригинал");
2) Проходя по массиву "зеркало", смотреть двоичным поиском есть ли элемент в "оригинал".

← →
@!!ex © (2008-02-23 08:06) [21]

> Странно что вы не сталкивались с алгоритмом быстрой сортировки.

О его существовании - знаю. Но применять никогда не приходилось.

← →
@!!ex © (2008-02-23 08:35) [22]

Palladin, вот рузальтаты тестирования с http://algolist.manual.ru
вот графики:
http://algolist.manual.ru/sort/gif/30.gif
Вот комментарий к ним:
На диаграммах изображены результаты сравнений поразрядной сортировки (синяя линия) и быстрой(розовая линия), причем использовалась функция sort() из библиотеки STL.

short
Благодаря малой разрядности и простоте внутренних циклов, поразрядная перегнала быструю сортировку уже на 100 элементах.
long
При переходе к типу long произошло двукратное увеличение количества проходов RadixPass, поэтому худшая асимптотика быстрой сортировки показала себя лишь после 600 элементов, где она начала отставать.
float
По графику видно, что для этого типа поразрядная сортировка оказалась гораздо эффективнее, нежели для long. В чем дело, ведь размер одинаков - 4 байта ?
Оказывается, на типе float резко возрастает время работы быстрой сортировки. Возможно, это связано с тем, что процессор, прежде чем делать какие-либо операции, переводит его в double, а потом работает с этим типом, который 2 раза больше по размеру.. Так или иначе, быстрая сортировка стала работать в 2 раза медленнее, и поразрядная вышла вперед после 100 элементов.
double
График показан с десятикратным увеличением.
Размер типа увеличился в 2 раза, поэтому для небольших n поразрядная сортировка, конечно, отстает, но перегоняет быструю на массивах из нескольких тысяч элементов. Небольшое преимущество radixSort длится приблизительно до 16000 элементов, когда данные начинают вылезать за пределы кэша. Соответственно, начинает играть роль медленный непоследовательный доступ (с шагами по 8 байт) к основной памяти.. В результате поразрядная сортировка снова выбивается вперед лишь после 500000 элементов.

Как всетаки здесь любят унижать человека, считая, что являются гуру.
Значок ДМ - не повод думать, что вы всех умнее и знаете больше всех.

Нельзя ли озвучить исходную задачу - не очень понятно, например, откуда берется зеркальный массив

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

Сравнивать поразрядную сортировку с другими методами можно, но это не совсем корректно, поскольку алгоритмы имеют разную функциональность.

> @!!ex (23.02.2008 08:35:22) [22]

Я элементарно докажу, что самая быстрая сортировка это пузырек.
Кроме того авторы не представляют, как работает процессор и приплели сюда зачем то double, которым и не пахнет при работе с сопроцессором, при том для любой разрядности.

> [23] MBo © (23.02.08 10:25)

Есть список объектов на сервере.

Есть зеркала для всех клиентов. Зеркало - это список объектов на клиенте.
При обновлении нужно сравнить зеркало каждого клиента с оригиналом. Если объект есть в зеркале, но его нет в оригинале, нужно послать сообщение клиенту об удалении объекта.

> [24] palva © (23.02.08 10:36)

Да. Это понятно.

> [25] Anatoly Podgoretsky © (23.02.08 12:30)

Да я это понимаю.
Просто убило поведение человека, с намеками, что это ерунда, которой не существует, что она не применима и вообще.

> @!!ex © (23.02.08 14:08) [26]

Довольно странно, что сим сравнением озабочен владелец-управляющий "оригиналом".

Его классическая задача - предоставить по запросу управляющего "зеркалом" снимок "оригинала" и рассылать подписчикам извещения об изменениях этого "оригинала". Синхронизация же "зеркал" с "оригиналом" целиком и полностью возлагается на "подписчиков - управляющих "зеркалами".

> [27] Сергей М. © (23.02.08 14:39)

дело в том, что это позволит НЕ пересылать каждый раз все данные клиенту.
Например, есть объекты 1,2,3,4.
Они есть и на сервере и на клиенте.
На сервере "умер" объект 2.
Есть вариант: послать весь список клиенту, но это
1) потребует пересылать данные, которые возможно и не изменились
2) пересылать большой объем данных сразу

Если же делать синхронизацию на уровне сервера, то достаточно лишь будет послать сообщение о том, что объект 2 - умер. То же и при создании объекта.
Т.к. обновление идет несколько раз, а обновляется лишь часть объектов - первый вариант менее выгодный.
Хотя я не полностью уверен, никогда таких задач не решал.

> Если же делать синхронизацию на уровне сервера, то достаточно
> лишь будет послать сообщение о том, что объект 2 - умер

Не на "уровне сервера", а в контексте текущей сессии взаимодействия клиента с сервером.

Никакого поиска в массиме "оригинал" двоичного не надо. Берем два индекса и гуляем по массивам так
i1 := 0; i2 :=0;
whil (i1 < length (a1) and (i2 < length(a2)) do
if a1[i1]=a2[i2] then
inc (оба)
else
if a1[] < a2[] then
writeln (a1 отсутствует)
inc (i1)
else
writeln (a2 отсутствует)
inc (i2)
for i1 = i1 to length (a1)-1 do
writeln (a1 отсутствует)
и тоже для 2.

Быстрый поиск отстутствующих элементов в массиве Найти похожие ветки