| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

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

Самый быстрый алгоритм поиска в TStringList [D7, Win2k, WinXP]

demidofff ©   (2004-09-11 10:31:00) 

Добрый день уважаемые,
я понимаю что этот вопрос может раз сто звучал, но чтото именно то что мне надо я не нашел. У меня есть следующее:
..
myList : TStringList;
..
res := myList.IndexOf(myStr);
if res = -1 then
begin
 myList.Add(myStr);
end;
Вначале меня это устраивало, но когда мой список разрастается, а разрастается он довольно-таки быстро, иногда по 40 записей в секунду, то уже при нескольки тысяч записей прога начинает тормозить. В принципе оно и понятно что изза этого тормозного поиска.
Вот и хотел узнать может вы знаете самые быстрые алгоритмы поиска в таком списке, если можно приведите сырцы, огромное вам спасибо.

---

Verg   (2004-09-11 13:27:00) [1]

> [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;

---

demidofff   (2004-09-11 13:14:00) [2]

ого, спасибо, интересное решение, буду пробовать!

---

Verg   (2004-09-11 12:20:00) [3]

Можно промежуточный вариант предложить:
Построение индексов "на лету"
Что-то типа такого должно работать:

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 - тем не менее хранит все строки в порядке поступления, а поиск при добвлении идет двоичный.

---

Alx2   (2004-09-11 12:16:00) [4]

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

---

Verg   (2004-09-11 11:02:00) [5]

Ну сделай два списка, один сортированный, а другой - нет.
Ищи в сортированном, и если не найдено, то добавляй в оба.

Жаль памяти? Примени вместо второго, сортированного списка hash

---

demidofff   (2004-09-11 11:00:00) [6]

к сожалению сортировка для меня губительна, мне важна именно последовательность строк в списке, мне главное чтобы одинаковых записей там не было не нарушая последовательность, вот такая вот задачка

---

Verg   (2004-09-11 10:35:00) [7]

Сделай список сортированным (Sorted), тогда значительно быстрее будет искать.

---

Наверх