| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Господа, подскажите пожалуйста самый быстрый [D5, Win2k, WinXP]
Smok_er © (2002-05-31 09:27:00)способ обнаружения записи в StringList. Т.е. при добавлении очень большого числа строк и использовании метода IndexOf для определения, есть ли уже запись или нет, процесс начинается очень быстро, но по мере увеличения числа записей очень сильно замедляется.
Причем сначала я делал по-другому - сначала закидывал все в один стринглист, сортировал, а потом постепенно идя от последнего к первому элементу, с этого стринг лист закидывал в другой.
И еще один вопрос - если к стринглисту применить сортировку, то новые записи будут добавляться с учетом сортировки или в конец?
Smok_er (2002-06-05 23:49:00) [1]Спасибо за ответ! Долго не заходил в интернет по некоторым причинам.
Честно говоря, не очень хочется связываться с базами данных
Да они и не нужны в принципе, зато увеличат размер программы как минимум в 2 раза.
erik (2002-05-31 15:50:00) [2]А чем неустраивает DBGrid для вывода, а хранить строки можно в TClientDataSet. Это будет на порядок быстрее, если есть желание то можно использовать отсортированый масив. Выводить можно спомощю сверх быстрого "TArrayGrid - визуальный компонент для табличного представления данных" http://home.earthlink.net/~akonshin/delphi_ru.htm
Smok_er (2002-05-31 10:38:00) [3]2 handra
Спасибо за вариант, но к сожалению, именно из-за "дефицита" памяти и огромного числа строк (может быть порядка 100.000) я и ищу более быстрый и ресурсосберегающий метод.
Кстати, при sorted:=True увеличение быстродействия ну очень сильно ощутимо. Возросло где-то раз в 50-100.
Интересно, а как к примеру сортировать, если
1) нужна сортировка в обратном порядке;
2) сортировать числовые значения.
И еще один вопрос. Если использовать схему Name=Value, то если где-то в строке Name встречается знак "=" - происходит каша. Может есть способы, как от этого избавиться...?
Romkin (2002-05-31 10:36:00) [4]Да посмотрите же исходники - если TStringList.Sorted
то IndexOf... применяет быстрый поиск
Установи Duplicates := dupIgnore; Sorted := true;
И просто закидывай все строки - получится отсортированный список уникальных строк, причем очень быстро, быстрее написать сложно
handra (2002-05-31 10:19:00) [5]Конечно, можно хранит в параметрах Data у элементов TStringList значение 32-битной хэш-функции и искать по этому значению...
handra (2002-05-31 10:16:00) [6]
//Быстро, но требует памяти при большом количесве слов
unit wrd_tree;
interface
type
TWordTreeNode=class(TObject)
public
Links: Array[byte] of Pointer;
Id: Integer;
constructor Create;
destructor Destroy; override;
end;
TWordTree = class(TObject)
private
FRoot: TWordTreeNode;
public
constructor Create;
destructor Destroy; override;
function FindWord(wrd: string): Integer;
procedure AddWord(wrd: string; id: Integer);
end;
implementation
constructor TWordTreeNode.Create;
begin
FillChar(Links,sizeof(Links),0);
Id := 0;
end;
destructor TWordTreeNode.Destroy;
var i: Integer;
begin
for i:=Low(Links) to High(Links) do
if Links[i]<>nil then begin
TWordTreeNode(Links[i]).Destroy;
Links[i] := nil;
end;
Id := 0;
inherited;
end;
constructor TWordTree.Create;
begin
FRoot := TWordTreeNode.Create;
end;
destructor TWordTree.Destroy;
begin
FRoot.Free;
inherited;
end;
function TWordTree.FindWord(wrd: string): Integer;
var i: Integer;
node: TWordTreeNode;
begin
Result := 0;
node := FRoot;
for i:=1 to Length(wrd) do begin
node := node.Links[ord(wrd[i])];
if node=nil then Exit;
end;
Result := node.Id;
end;
procedure TWordTree.AddWord(wrd: string; id: Integer);
var i: Integer;
b: byte;
node: TWordTreeNode;
begin
node := FRoot;
for i:=1 to Length(wrd) do begin
b := ord(wrd[i]);
if node.Links[b]=nil then
node.Links[b] := TWordTreeNode.Create;
node := node.Links[b];
end;
node.Id := id;
end;
end.
MBo (2002-05-31 09:59:00) [7]Предыдущее 31.05.02 09:51 следует читать:
при sorted:=true IndexOf сам использует двоичный поиск
Smok_er (2002-05-31 09:55:00) [8]А можно пример реализации?
MBo (2002-05-31 09:51:00) [9]несравнимо быстрее- будет двоичный поиск
Smok_er (2002-05-31 09:49:00) [10]2 Vitaly
дело в том, что я сортировал в самом конце. Относительно свойства sorted не знал, но интересен вопрос в моем предыдущем постинге. Мы просто одновременно написали.
Smok_er (2002-05-31 09:46:00) [11]А скорость нахождения какой-то записи при этом будет быстрее?
Т.е. вопрос такой:
допустим, в стринглисте 2000 записей.
нам надо проверить 100000 записей, есть ли какие-то из них в стринг листе.
интересно, этот код будет работать быстрее, если стринглист StringList1 будет отсортирован?
if StringList1.IndexOf(a)=-1 then
StringList1.Add(a);
Vitaly (2002-05-31 09:45:00) [12]Надо же было сбацать такой хитрый алгоритм
и не проверить, а как же добавляются
новые строки при sorted := true.
MBo (2002-05-31 09:31:00) [13]если поставить sorted:=true, то новые строки встанут на место
| |
