Оптимизация поиска

[mutabor]

Как можно ускорить поиск неповторяющихся значений в массиве?
Например есть матрица 1000х1000, целочисленная. Нужно перебрать все элементы и определить сколько уникальных. Вопрос не в том как это сделать, а как оптимизировать.
Я делаю так: создаю дополнительный массив куда записываю уникальные значения. В двойном цикле перебираю матрицу

for 0 to 999 do
  for 0 to 999 do
   //тут перебор дополнительного массива, чтобы узнать не повторяется ли 
   //значение, из-за этого и задержка
   //если не повторяется, записываю в доп. массив новое значение

Скорость обработки матрицы уменьшается с геометрической прогрессией, ведь доп. массив растет.
Все что мне пришло в голову это прерывать поиск в дополнительном массиве, если обнаружен повтор. Но это не особо помогает, особенно если повторов в матрице мало.

[B_N]

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

[alexBlack]

Матрицу. как не представляй, перебор останется. А вот для дополнительного массива:

1) его нужно сортировать (использовать дерево или наподобие того, как это сделано в TStringList).

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

[B_N]

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

[alexBlack]

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

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

[B_N]

Да зачем их сохранять-то? задать матрицуне в виде массива массивов целых, а виде списка записей с полями <значение элемента>, <изначальное расположение элемента>, рассортировывать список по мере прохождения по нему, повторяющиеся из спискка удалять - в результате останутся только уникальные.

[Andrei]

Я бы представил массив в виде ленты (М1).
Дополнительно созда бы массив в виде ленты с неповторяющимися результатами (М2). S - сумма неповторяющихся значений. Переменная Dubl: Boolean -показывает повторяется значение или нет.

Dubl:=false;
Берем М1[1] и сравниваем со всеми последующими.
if M1[i]<>M1[1] копируем значение M1[i] в M2.
else Dubl:=True;

В конце прогонки:
if Dubl=false then S:=S+1;

В результате массив M2 в худшем случае будет содержать на одно значение меньше, а в лучшем - на значительное количество повторяющихся значений.

А дальше с массивом М2 поступаем так же как с массивом M1.
И гоняем до тех пор, пока количетво значений в массиве M2 не станет равным нулю.

В результате S покажет количество неповторяющихся значений.

Принцып, по-моему ясен. Если подумать и поизвращаться, то можно обойтись и одним массивом.

[mutabor]

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

Над этим думал, диапазон большой 0..16000000, кстати а какая в Дельфи вообще допустимая длина массива?

Надо будет ещё с сортировкой попробовать. Спасибо за советы!

2Андрей, не совсем понял принцип, что за сумма S? После нескольких сложений произойдет переполнение, или она не для этого? Можно без кода на словах.

[B_N]

Вряд ли в дельфи есть максимум на размер массива, а потом, ведь у нас есть виртуальная память.

Идея такая:
1. Задаем матрицу, как я писал выше (6-й пост)
2. Проходим по ней один раз с целью поиска более-менее среднего значения X.
3. Переставляем элементы списка так, чтобы в одной половине всё было меньше X, в другой - всё больше. То, что на этом этапе оказывается равным X, из списка удаляем. Порядком эелементов внутри наших подмножеств не интересуемся. Сохраняем адрес сечения.
4. Берем наугад любой элемент списка, выясняем, к какой половине он относится (больше он или меньше X) и повторяем пункты 2, 3. для этой половины. Другая половина нас, естественно, не нтересует, там заведомо не окажется равных ему значений.
и т.д. до исчерпания...
При желании восстанавливаем матрицу в прежнем виде по записям о первоначальых координатах оставшихся элементов, это уже смотря какая задача.

[Jeni]

Сообщение от mutabor

Над этим думал, диапазон большой 0..16000000, кстати а какая в Дельфи вообще допустимая длина массива?

Для Дельфи 16 млн. элементов сущий пустяк, тем более если это будут элементы типа Boolean длиной в один байт. Заполнить такой массив в цикле или посчитать в нем количество True/False элементов - несколько секунд. Такой метод действительно будет самым быстрым.