Быстрый поиск числа в списке

← →
Юра (2003-01-29 11:03) [0]

В процессе работы программы генерируется около 1000 чисел. Необходимо сохранить их, исключив повторы, и потом быстро искать. Функция поиска имеет возвращает TRUE, если искомое найдено, и FALSE в противном случае.
Возможные решения:
1. Порождаю класс от TList. Внутри числа в нем отсортированы по возрастанию. Поиск производится методом половинного деления.
2. Не надо изобретать велосипед - в TStringList это все уже реализовано. В сортированном списке строк поиск так и осуществляется.
3. Иное.
На каком варианте мне лучше остановиться?

← →
REA (2003-01-29 11:07) [1]

От сколько до скольки числа? Что важнее - память или быстродействие?

← →
Anatoly Podgoretsky (2003-01-29 11:11) [2]

Лучще рстановиться на массиве

← →
Юра (2003-01-29 11:14) [3]

Числа - LongInt, от 0. Важнее быстродействие.

← →
REA (2003-01-29 11:19) [4]

При генерации какое-нибудь дерево можно построить - искать будет проще. Алгоритмы поиска были на "алгоритмах", у Кнута что-то было.

← →
Юра (2003-01-29 11:19) [5]

> Anatoly Podgoretsky

Т.е. обычный отсортированный массив, поиск методом деления пополам?

← →
Anatoly Podgoretsky (2003-01-29 11:24) [6]

Да, тут и скорость и минимум памяти

← →
Sha (2003-01-29 11:50) [7]

Может это сгодится:
http://delphibase.endimus.com/?action=viewfunc&topic=matharray&id=10383

← →
REA (2003-01-29 11:55) [8]

Кстати в D7 есть THashedStringList, TBucketList - может что пригодится.

← →
han_malign (2003-01-29 12:11) [9]

>>Юра (29.01.03 11:19)
>>> Anatoly Podgoretsky
>>Т.е. обычный отсортированный массив, поиск методом деления пополам?

>>Anatoly Podgoretsky © (29.01.03 11:24)
>>Да, тут и скорость и минимум памяти

На счет скорости вы зря - копирование блока памяти размером до 1000*sizeo(longint) - довольно долгая операция

Самый быстрый метод - бинарное дерево, причем, для увеличения скорости и уменьшения фрагментации, память под узлы можно выделить заранее - памяти жрет всего в 3 раза больше(sizeof(longint)+2*sizeof(pointer))...

← →
Anatoly Podgoretsky (2003-01-29 12:21) [10]

Ты откуда взял про копирование, ведь уже не утро?
Поиск в несбалансированном дереве приблизается по скорости к линейному поиску.

← →
han_malign (2003-01-29 12:37) [11]

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

Быстрый поиск числа в списке Найти похожие ветки