Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Общие вопросы > StringList

Автор: z-END 23.1.2005, 12:00

Вот тестовая прога, ничего умного она не делает=) просто засекает время выполнения двух вещей:
1. Добавление элементов в StringList
2. Получение индекса сторки из StringList
Вообщем я впал в ужас..

Код


program testCons;

{$APPTYPE CONSOLE}
uses
  SysUtils, Classes, Windows, Forms;
var
Found, Added, Steps, x, startIdx, finishIdx, startAdd, finishAdd: Integer;
List: TStringList;
begin
Randomize;
 Repeat
  Write ('Enter cycle steps (0 for exit): ');
  Readln (Steps);
   if Steps > 0 then
     begin
      Dec (Steps);
      Write ('Adding List...');
      List := TStringList.Create;
      Added := 0;
      StartAdd := GetTickCount;
       for x := 0 to Steps do
         begin
           List.Add (IntToStr( Random(MaxInt)));
            Application.ProcessMessages;
           Inc (added);
         end;
      finishAdd := GetTickCount;
      Writeln ('  complete.');
      Write ('Getting index...');
      Found := 0;
      StartIdx := GetTickCount;
      for x := 0 to Steps do
        begin
          Application.ProcessMessages;
           if List.IndexOf(IntToStr(x))=-1 then Continue;
          Inc(found);
        end;
      finishIdx := GetTickCount;
      Writeln ('  complete.');
      Writeln ('Result:');
      Writeln ('Adding time: ' + IntToStr (finishAdd - startAdd) + ' ms');
      Writeln ('Indexing time: ' + IntToStr (finishIdx - startIdx) + ' ms');
      Writeln ('Added: ' + IntToStr (Added));
      Writeln ('Matches: ' + IntToStr (Found));
      Writeln ('----------------------------------------------------');
      Freeandnil (List);
   end;
 Until Steps = 0
end.

Кому лень запускать привожу результаты работы:

Цитата

Enter cycle steps (0 for exit): 1000
Adding List... complete.
Getting index... complete.
Result:
Adding time: 0 ms
Indexing time: 734 ms
Added: 1000
Matches: 0
----------------------------------------------------
Enter cycle steps (0 for exit): 5000
Adding List... complete.
Getting index... complete.
Result:
Adding time: 16 ms
Indexing time: 18594 ms
Added: 5000
Matches: 0
----------------------------------------------------

Чуть про вопрос незабыл=)
возможно ли ускорить этот процесс? т.к. у меня в списке (запланировано) до 300 тыс. строк. smile

Да, индексирование я использую для определения наличия данной строки в списке, (все строки уникальны)
может есть более оптимальные варианты?

Автор: Alex 23.1.2005, 12:24

http://vingrad.ru/DELPHI-SRC-002243

Автор: z-END 23.1.2005, 12:36

Alex анд что?

Автор: Alex 23.1.2005, 12:38

Код


     Writeln ('  complete.');
     List.Sorted:= True;
     Write ('Getting index...');

Добавлено @ 12:39

Цитата(z @ 23.1.2005, 12:36)

Alex анд что?

Модуль дя более точного засекания времени
Добавлено @ 12:41

Цитата

Enter cycle steps (0 for exit): 65535
Adding List... complete.
Getting index... complete.
Result:
Adding time: 79 ms
Indexing time: 516 ms
Added: 65535
Matches: 3
----------------------------------------------------
Enter cycle steps (0 for exit):

Автор: z-END 23.1.2005, 12:42

Слона-то я и не заметил=)

Alex, очередное спасибо!

ЗЫ, да мне точно и ненадо было, так просто сравнить разницу..

Автор: Alex 23.1.2005, 12:47

Причину знаешь почему так произошло?

Автор: Петрович 23.1.2005, 12:52

Ну, тут как всегда. Очевидное решение не всегда самое эффективное. Давай, несколько модифицироуем твой приммер:

Код


program Project1;
{$APPTYPE CONSOLE}
uses
 SysUtils, Classes, Windows, Forms;
var
Found, Added, Steps, x, startIdx, finishIdx, startAdd, finishAdd: Integer;
List: TStringList;
S :String;
begin
Randomize;
Repeat
 Write ('Enter cycle steps (0 for exit): ');
 Readln (Steps);
  if Steps > 0 then
    begin
     Dec (Steps);
     Write ('Adding List...');
     List := TStringList.Create;
     Added := 0;
     StartAdd := GetTickCount;
      for x := 0 to Steps do
        begin
          List.Add (IntToStr( Random(MaxInt)));
           Application.ProcessMessages;
          Inc (added);
        end;
     finishAdd := GetTickCount;
     Writeln ('  complete.');
     Write ('Getting index...');

     s := ^M^J+List.Text;
     Found := 0;
     StartIdx := GetTickCount;
     for x := 0 to Steps do
       begin
         Application.ProcessMessages;
         if Pos(^M^J+IntToStr(x)+^M^J,s)=0 then Continue;
         Inc(found);
       end;
     finishIdx := GetTickCount;


     Writeln ('  complete.');
     Writeln ('Result:');
     Writeln ('Adding time: ' + IntToStr (finishAdd - startAdd) + ' ms');
     Writeln ('Indexing time: ' + IntToStr (finishIdx - startIdx) + ' ms');
     Writeln ('Added: ' + IntToStr (Added));
     Writeln ('Matches: ' + IntToStr (Found));
     Writeln ('----------------------------------------------------');
     Freeandnil (List);
  end;
Until Steps = 0
end.

Теперь сравним результаты:
До модификации:

Цитата

Enter cycle steps (0 for exit): 5000
Adding List... complete.
Getting index... complete.
Result:
Adding time: 0 ms
Indexing time: 15343 ms
Added: 5000
Matches: 0

После:

Цитата

Enter cycle steps (0 for exit): 5000
Adding List... complete.
Getting index... complete.
Result:
Adding time: 0 ms
Indexing time: 2125 ms
Added: 5000
Matches: 0

А еще:
1. Application.ProcessMessages в консольных приложениях - это лишнее.
2. Нужно выносить действия инвариантные к циклу, за его пределы.
Но это ты уже сам smile

Автор: z-END 23.1.2005, 13:06

Alex чесно говоря несовсем=)
так-что c радостью готов услышать!

Петрович ProccessMessages я использовал только для того чтобы приблизить результаты к другой софтине, которая совершенно не консольная=) (кстати в ней то-же код работает намного медленней)
а вот про второй пункт я несовсем понял smile

ЗЫ а вот результат сортировонного списка:

Цитата

Enter cycle steps (0 for exit): 5000
Adding List... complete.
Getting index... complete.
Result:
Adding time: 16 ms
Indexing time: 32 ms
Added: 5000
Matches: 0
----------------------------------------------------

Автор: Alex 23.1.2005, 13:18

1 Ссылка на модуль для замера времени исполнения теперь http://vingrad.ru/DELPHI-SRC-002244

Автор: Петрович 23.1.2005, 13:18

Цитата(z @ 23.1.2005, 14:06)

ЗЫ а вот результат сортировонного списка

Ну да, в отсортированном конечно поиск быстрее. Всетаки используется алгоритм QuickSearch smile

Цитата(z @ 23.1.2005, 14:06)

а вот про второй пункт я несовсем понял

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

Автор: Alex 23.1.2005, 13:28

Цитата(z @ 23.1.2005, 13:06)

Alex чесно говоря несовсем=)
так-что c радостью готов услышать!

Дело в том, что если посмотреть на реализацию метода IndexOf, то можно увидеть, что в нем по-разному происходит поиск в отсортированном и не отсортированном списке

Код


function TStringList.IndexOf(const S: string): Integer;
begin
  if not Sorted then Result := inherited IndexOf(S) else
    if not Find(S, Result) then Result := -1;
end;

Если список, не отсортированный, то дергается базовый метод типа TStrings

Код


function TStrings.IndexOf(const S: string): Integer;
begin
  for Result := 0 to GetCount - 1 do
    if CompareStrings(Get(Result), S) = 0 then Exit;
  Result := -1;
end;

Он не эффективен по той причине, что постоянно идет перебор всех элементов списка.

Если же сортировка включена, то выборку можно осуществить гораздо быстрее по методу деления по полам. Это когда весь ОТСОРТИРОВАННЫЙ массив бьется на 2 и определяется, к какой части относится элемент, который ищут. Дальше эту уже часть опять делят на 2 и так далее пока не найдут нужный элемент.

Код


function TStringList.Find(const S: string; var Index: Integer): Boolean;
var
  L, H, I, C: Integer;
begin
  Result := False;
  L := 0;
  H := FCount - 1;
  while L <= H do
  begin
    I := (L + H) shr 1;
    C := CompareStrings(FList^[I].FString, S);
    if C < 0 then L := I + 1 else
    begin
      H := I - 1;
      if C = 0 then
      begin
        Result := True;
        if Duplicates <> dupAccept then L := I;
      end;
    end;
  end;
  Index := L;
end;