Форум: "Основная";
Текущий архив: 2004.09.26;
Скачать: [xml.tar.bz2];
Вниз
Самый быстрый алгоритм поиска в TStringList Найти похожие ветки
← →
demidofff (2004-09-11 10:31) [0]Добрый день уважаемые,
я понимаю что этот вопрос может раз сто звучал, но чтото именно то что мне надо я не нашел. У меня есть следующее:
..
myList : TStringList;
..
res := myList.IndexOf(myStr);
if res = -1 then
begin
myList.Add(myStr);
end;
Вначале меня это устраивало, но когда мой список разрастается, а разрастается он довольно-таки быстро, иногда по 40 записей в секунду, то уже при нескольки тысяч записей прога начинает тормозить. В принципе оно и понятно что изза этого тормозного поиска.
Вот и хотел узнать может вы знаете самые быстрые алгоритмы поиска в таком списке, если можно приведите сырцы, огромное вам спасибо.
← →
Verg © (2004-09-11 10:35) [1]Сделай список сортированным (Sorted), тогда значительно быстрее будет искать.
← →
demidofff (2004-09-11 11:00) [2]к сожалению сортировка для меня губительна, мне важна именно последовательность строк в списке, мне главное чтобы одинаковых записей там не было не нарушая последовательность, вот такая вот задачка
← →
Verg © (2004-09-11 11:02) [3]Ну сделай два списка, один сортированный, а другой - нет.
Ищи в сортированном, и если не найдено, то добавляй в оба.
Жаль памяти? Примени вместо второго, сортированного списка hash
← →
Alx2 © (2004-09-11 12:16) [4]Сортировать. Но для восстановления нужного порядка, каждой строке привязать ее порядковый номер (его можно в objects хранить, если эти objects не используются, конечно). Когда понадобится возобновить оригинальный порядок - сортировать через соответствующим образом перекрытый customSort.
← →
Verg © (2004-09-11 12:20) [5]Можно промежуточный вариант предложить:
Построение индексов "на лету"
Что-то типа такого должно работать:TSortedStrings = class( TStringList )
public
Data : TStringList;
constructor Create;
destructor Destroy; override;
protected
function CompareStrings(const S1, S2: string): Integer; override;
function AddString( const S : string ) : boolean;
end;
implementation
constructor TSortedStrings.Create;
begin
inherited Create;
Data := TStringList.Create;
Sorted := true;
end;
destructor TSortedStrings.Destroy;
begin
Data.Free;
inherited;
end;
function TSortedStrings.CompareStrings(const S1, S2: string): Integer;
var I1, I2 : integer;
begin
I1 := StrToInt(S1);
I2 := StrToInt(S2);
Result := AnsiCompareStr( Data[I1], Data[I2])
end;
function TSortedStrings.AddString( const S : string) : boolean;
var I : integer;
Si : string;
begin
I := Data.Add( S );
Si := IntToStr( I );
Result := IndexOf( Si ) < 0;
if Result then
Add( Si )
else
Data.Delete(I)
end;
Т.о. Добавляем строку:
var Indexes : TSortedStrings;
Indexes.AddString(S);
Indexes.Data - тем не менее хранит все строки в порядке поступления, а поиск при добвлении идет двоичный.
← →
demidofff (2004-09-11 13:14) [6]ого, спасибо, интересное решение, буду пробовать!
← →
Verg © (2004-09-11 13:27) [7]
> [6] demidofff (11.09.04 13:14)
Пробуй. Только вот с двумя списками все равно расход памяти меньше. Оба списка в сущности хранят просто ссылки на физически одни и теже строки (блоки символов), так что "перерасход памяти" будет даже меньше, чем в [5] Verg © (11.09.04 12:20)TSortedStrings = class( TStringList )
public
Data : TStringList;
constructor Create;
destructor Destroy; override;
function AddString( const S : string ) : boolean;
end;
constructor TSortedStrings.Create;
begin
inherited Create;
Data := TStringList.Create;
Sorted := true;
end;
destructor TSortedStrings.Destroy;
begin
Data.Free;
inherited;
end;
function TSortedStrings.AddString( const S : string) : boolean;
var I : integer;
begin
Result := IndexOf(S) < 0;
if Result then
begin
Add(S);
Data.Add(S); // сдесь по-сути будет призведен shallow copy, т.е. просто
// инкремент счетчика ссылок у S, никакой лишней памяти
// выделено не будет
end;
end;
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2004.09.26;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.051 c
