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

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

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

быстрый поиск в некотором массиве [D6, D7, Win95/98, Win2k]

Hamlet © (2002-12-06 15:41:00)
Как максимально быстро организовать поиск среди динамически изменяемого набора данных?
Подробнее: Есть некоторая таблица с бо-ольшим количеством записей. Есть некоторый набор данных, в котором элементы этой таблицы добавляются/удаляются во время работы программы. Периодически необходимо для каждого элемента таблицы определять, находится ли он в этом наборе или нет. Структуру таблицы менять нельзя.
Сейчас реализовано через TStringList c перебором всех значений, но работает крайне медленно. Как можно сделать по-другому?

murzikN (2002-12-07 07:44:00) [1]
Используй TSortList.
Скачать можно по адресу
http://www.ivanovtver.chat.ru/sortlist.zip

Fantasist (2002-12-07 05:28:00) [2]
Ха, так как я понял, основное время тратиться на перебор таблицы. Имеет значение из чего состоит выборка - если из элементов этой таблицы (Table1), то лучше просто составить список из номеров выбранных элементов и синхронизировать этот список при изменении таблицы. Тогда надо будет всего лишь пройтись по этим трем-пяти элементам и ничего проверять не надо. Если же это какие-то левые значения, то это сложнее. Перебирать таблицу из 10000 элементов все-равно долго. Тут надо думать о логике программы, потому как схема с перебором всех элементов явно не классна.

Sha (2002-12-06 19:25:00) [3]
1. Поиск в сортированном StringListе достаточно быстрый.
2. Если надо быстрее, заведи дополнительный сортированный
целочисленный массив и храни в нем CRC32 строк.
По нему и отсекай. И только если CRC32 совпала ищи в
StringListе. Проверено - все летает.

Hamlet (2002-12-06 16:37:00) [4]
мне нужно конкретное решение - как наиболее быстро будет работать. С указанием конкретных типов, а еще лучше - с примером кода. Я и сам понимаю, что отсортированный массив может и будет быстрее, но как грамотно его организовать, чтобы действительно было быстрее?
К тому же он будет быстрее только в том случае, когда элемент таблицы есть в выборке. А их в основном в выборке нет. Т.е. фактически мне нужно ускорить как раз отсечение ненужных элементов, а не поиск нужных.

Hamlet (2002-12-06 16:34:00) [5]
дело не в поиске. Внимательно см. условие задачи.

TTCustomDelphiMaster (2002-12-06 16:30:00) [6]
Поиск в отсортированном массиве намного быстрее.

Hamlet (2002-12-06 16:26:00) [7]
2 mrcat: пробовал и так, ничуть не убыстряется. См. ответ выше

mrcat (2002-12-06 16:24:00) [8]
begin
if sList[z]=Table1.Fields[1].Value then begin
OK:=true;
break;end;
end;

Hamlet (2002-12-06 16:24:00) [9]
еще раз повторяю - в том то и дело что любые изменения в таблице невозможны. Кроме того, как создавать этот вектор, в виде чего? Создавать какую-либо дополнительную таблицу не хочется, это дополнительный код/дисковое место.

han_malign (2002-12-06 16:15:00) [10]
... Как думаешь что быстрее - перебор значений списка, или модификация/проверка элемента булевского массива по абсолютному индексу?
З.Ы. Естественно нужно отслеживать изменения таблицы(добавление,удаление,перемещение элементов), и соответственно изменять индекс. В принципе, есть древний, как информатика, финт ушами - при присоединении элемента к набору, в строковое поле добавляется специальный символ, соответственно при отсоединении - удаляется(скажем #0 в конец - безболезнено при отображении(если не TMemo - оно будет |рисовать)) (С)Удаление записей в DBase таблице. Короче нужно найти в полях хотя-бы один битик значение которого не влияет на работу всего остального, ну или где надо маски(фильтры) проставить.

Hamlet (2002-12-06 16:04:00) [11]
нет, но, имхо, сортировка почти не ускорит процесс, т.к. в выборке в среднем 3-5 элементов, а в таблице до 10.000, так что основное время занимает фильтрация ненужных записей. Зато будет тратиться время на сортировку при каждом удалении/добавлении элемента, что происходит довольно часто.

MBo (2002-12-06 16:02:00) [12]
SList сортирован?

Hamlet (2002-12-06 15:59:00) [13]
2 han_malign: а будет ли это быстрее списка?

Hamlet (2002-12-06 15:55:00) [14]
в общих чертах:
Table1 - таблица с данными (не-SQL)
SList:TStringList - в нем лежит выборка

for i:=0 to Table1.recordCount-1 do
begin
for z:=0 to SList.Count-1 do
begin
if sList[z]=Table1.Fields[1].Value then OK:=true;
end;
if OK then
begin
........
end
end

т.е., если элемент таблицы есть в выборке, то для него выполняется действие, если нет - то нет.

han_malign (2002-12-06 15:52:00) [15]
строить свой индекс, конкретно - завести булевский вектор по размеру таблицы и проставлять в нем флаг присутствия в наборе для каждого елемента

Anatoly Podgoretsky (2002-12-06 15:50:00) [16]
Да и поточнее, про массивы, про TStringList или про базы речь

Виктор Щербаков (2002-12-06 15:45:00) [17]
Ты бы код привел. А то не совсем понятно о чем речь.

Наверх

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