быстрый поиск в некотором массиве

← →
Hamlet (2002-12-06 15:41) [0]

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

← →
Виктор Щербаков © (2002-12-06 15:45) [1]

Ты бы код привел. А то не совсем понятно о чем речь.

← →
Anatoly Podgoretsky © (2002-12-06 15:50) [2]

Да и поточнее, про массивы, про TStringList или про базы речь

← →
han_malign © (2002-12-06 15:52) [3]

строить свой индекс, конкретно - завести булевский вектор по размеру таблицы и проставлять в нем флаг присутствия в наборе для каждого елемента

← →
Hamlet (2002-12-06 15:55) [4]

в общих чертах:
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

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

← →
Hamlet (2002-12-06 15:59) [5]

2 han_malign: а будет ли это быстрее списка?

← →
MBo © (2002-12-06 16:02) [6]

SList сортирован?

← →
Hamlet (2002-12-06 16:04) [7]

нет, но, имхо, сортировка почти не ускорит процесс, т.к. в выборке в среднем 3-5 элементов, а в таблице до 10.000, так что основное время занимает фильтрация ненужных записей. Зато будет тратиться время на сортировку при каждом удалении/добавлении элемента, что происходит довольно часто.

← →
han_malign © (2002-12-06 16:15) [8]

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

← →
mrcat © (2002-12-06 16:24) [9]

begin
if sList[z]=Table1.Fields[1].Value then begin
OK:=true;
break; end;
end;

← →
Hamlet (2002-12-06 16:24) [10]

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

← →
Hamlet (2002-12-06 16:26) [11]

2 mrcat: пробовал и так, ничуть не убыстряется. См. ответ выше

← →
TTCustomDelphiMaster © (2002-12-06 16:30) [12]

Поиск в отсортированном массиве намного быстрее.

← →
Hamlet (2002-12-06 16:34) [13]

дело не в поиске. Внимательно см. условие задачи.

← →
Hamlet (2002-12-06 16:37) [14]

мне нужно конкретное решение - как наиболее быстро будет работать. С указанием конкретных типов, а еще лучше - с примером кода. Я и сам понимаю, что отсортированный массив может и будет быстрее, но как грамотно его организовать, чтобы действительно было быстрее?
К тому же он будет быстрее только в том случае, когда элемент таблицы есть в выборке. А их в основном в выборке нет. Т.е. фактически мне нужно ускорить как раз отсечение ненужных элементов, а не поиск нужных.

1. Поиск в сортированном StringListе достаточно быстрый.
2. Если надо быстрее, заведи дополнительный сортированный
целочисленный массив и храни в нем CRC32 строк.
По нему и отсекай. И только если CRC32 совпала ищи в
StringListе. Проверено - все летает.

Ха, так как я понял, основное время тратиться на перебор таблицы. Имеет значение из чего состоит выборка - если из элементов этой таблицы (Table1), то лучше просто составить список из номеров выбранных элементов и синхронизировать этот список при изменении таблицы. Тогда надо будет всего лишь пройтись по этим трем-пяти элементам и ничего проверять не надо. Если же это какие-то левые значения, то это сложнее. Перебирать таблицу из 10000 элементов все-равно долго. Тут надо думать о логике программы, потому как схема с перебором всех элементов явно не классна.

← →
murzikN (2002-12-07 07:44) [17]

Используй TSortList.
Скачать можно по адресу
http://www.ivanovtver.chat.ru/sortlist.zip

быстрый поиск в некотором массиве Найти похожие ветки