Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Быстрый поиск числа в списке [D5, Win2k]

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

han_malign (2003-01-29 12:37:00) [1]
>Ты откуда взял про копирование
а как вы собираетесь новый элемент в начало/середину не пустого массива вставлять?
Несбалансированное дерево - это да - это плохо, но ведь можно и сбалансировать...

Anatoly Podgoretsky (2003-01-29 12:21:00) [2]
Ты откуда взял про копирование, ведь уже не утро?
Поиск в несбалансированном дереве приблизается по скорости к линейному поиску.

han_malign (2003-01-29 12:11:00) [3]
>>Юра (29.01.03 11:19)
>>> Anatoly Podgoretsky
>>Т.е. обычный отсортированный массив, поиск методом деления пополам?

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

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

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

REA (2003-01-29 11:55:00) [4]
Кстати в D7 есть THashedStringList, TBucketList - может что пригодится.

Sha (2003-01-29 11:50:00) [5]
Может это сгодится:
http://delphibase.endimus.com/?action=viewfunc&topic=matharray&id=10383

Anatoly Podgoretsky (2003-01-29 11:24:00) [6]
Да, тут и скорость и минимум памяти

REA (2003-01-29 11:19:00) [7]
При генерации какое-нибудь дерево можно построить - искать будет проще. Алгоритмы поиска были на "алгоритмах", у Кнута что-то было.

Юра (2003-01-29 11:19:00) [8]
> Anatoly Podgoretsky

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

Юра (2003-01-29 11:14:00) [9]
Числа - LongInt, от 0. Важнее быстродействие.

Anatoly Podgoretsky (2003-01-29 11:11:00) [10]
Лучще рстановиться на массиве

REA (2003-01-29 11:07:00) [11]
От сколько до скольки числа? Что важнее - память или быстродействие?

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »