TStringList vs. THashedStringList vs. TDictionary

 Пет-проект это называется или просто делать нечего, но надо мне список слов хранить, чтобы проверить слово новое - не значится ли там. Конечно, я слыхал, что THashedStringList ищет вхождение на много быстрее, чем простой TStringList. Но насколько? А ещё, говорят, TDictionary - очень быстрая штука и модная (стильная, молодёжная..). Надо посмотреть.

Взял два списка. В первый список положу слова, которые искать буду во втором. 

procedure TformMain.btnGenerateClick(Sender: TObject);
//
  procedure FillList( AStr: TStrings );
  begin
    AStr.Clear;
    AStr.BeginUpdate;
    try
      var R := Word('Я') - Word( 'А' );
      for var N := 1 to 20000 do begin
        var W := '1234567';
        for var I := 1 to 7 do W[I] := Char( Word( WideChar( 'А' ) ) + Random( R ) );
        AStr.Add( W )
      end;
    finally AStr.EndUpdate;
    end;
  end;
//
begin
  FillList( ListBox1.Items );
  FillList( ListBox2.Items );
end;

Мне, так уж складывается, 7 букв в слове достаточно.

Число 20000 подобрал опытным путём. Теперь буду каждое слово помечать "=Yes|No" в зависимости от того найдётся ли оно, и засекать время. Разные способы - разные кнопки:

Прошу прощения, что не использую модные TStopwatch.

procedure TformMain.btnIndexOfClick(Sender: TObject);
//
  procedure ClearMarks( AStr: TStrings );
  begin
    AStr.BeginUpdate;
    try
      for var I := 0 to AStr.Count-1 do begin
        var S := AStr[I];
        var P := Pos( '=', S );
        if P > 0 then
          AStr[I] := Copy( S, 1, P-1 );
      end;
    finally AStr.EndUpdate;
    end;
  end;
//
  procedure Mark1In2( AStr1, AStr2: TStrings );...
//
  procedure Mark1In2Hashed( AStr1, AStr2: TStrings );...
//
  procedure Mark1In2Sorted( AStr1, AStr2: TStrings );...
//
  procedure Mark1In2Dictio( AStr1, AStr2: TStrings );...
//
begin  //  TForm16.btnIndexOfClick(Sender: TObject);
  Screen.Cursor := crHourGlass;
  try
    ClearMarks( ListBox1.Items );
    var dt := Now;
    case TControl( Sender ).Tag of
      1: Mark1In2Hashed( ListBox1.Items, ListBox2.Items );
      2: Mark1In2Sorted( ListBox1.Items, ListBox2.Items );
      3: Mark1In2Dictio( ListBox1.Items, ListBox2.Items );
      else Mark1In2    ( ListBox1.Items, ListBox2.Items )
    end;
    dt := Now - dt;
    Caption := FormatDateTime( 'hh:nn:ss.zzz', dt );
  finally Screen.Cursor := crDefault;
  end;
end;

Начнём с простого (тут подходит поговорка "Простота - хуже воровства") Mark1In2:

  procedure Mark1In2( AStr1, AStr2: TStrings );
  begin
    AStr1.BeginUpdate;
    try
      for var I := 0 to AStr1.Count-1 do begin
        var S := AStr1[I];
        AStr1[I] := S + '=' + IfThen( AStr2.IndexOf( S ) >= 0, 'Yes', 'No' );
      end;
    finally AStr1.EndUpdate;
    end;
  end;

Остальные методы размножаются копипастой с некоторыми изменениями и дополнениями.

Мой фаворит Mark1In2Hashed достанет из System.IniFiles старый (Delphi 6, если не ошибаюсь) добрый THashedStringList:

  procedure Mark1In2Hashed( AStr1, AStr2: TStrings );
  begin
    AStr1.BeginUpdate;
    try
      var HSL := THashedStringList.Create;
      try
        HSL.AddStrings( AStr2 );
        for var I := 0 to AStr1.Count-1 do begin
          var S := AStr1[I];
          AStr1[I] := S + '=' + IfThen( HSL.IndexOf( S ) >= 0, 'Yes', 'No' );
        end;
      finally HSL.Free;
      end;
    finally AStr1.EndUpdate;
    end;
  end;

Но не будем забывать, что и простой TStringList не лыком шит, имеет в рукаве кое-что:

если его упорядочить, то можно использовать метод половинного деления, а не простой перебор.

И это уже совсем другая история.

  procedure Mark1In2Sorted( AStr1, AStr2: TStrings );
  begin
    AStr1.BeginUpdate;
    try
      var SL := TStringList.Create( dupIgnore, True, False );
      try
        SL.AddStrings( AStr2 );
        for var I := 0 to AStr1.Count-1 do begin
          var S := AStr1[I];
          AStr1[I] := S + '=' + IfThen( SL.IndexOf( S ) >= 0, 'Yes', 'No' );
        end;
      finally SL.Free;
      end;
    finally AStr1.EndUpdate;
    end;
  end;

И напоследок рассмотрим данный нам в Generics.Collections список TDictionary.

  procedure Mark1In2Dictio( AStr1, AStr2: TStrings );
  begin
    AStr1.BeginUpdate;
    try
      var D := TDictionary<string,TObject>.Create;
      try
        for var I := 0 to AStr2.Count-1 do
          D.TryAdd( AStr2[I], nil );
        for var I := 0 to AStr1.Count-1 do begin
          var S := AStr1[I];
          AStr1[I] := S + '=' + IfThen( D.ContainsKey( S ), 'Yes', 'No' );
        end;
      finally D.Free;
      end;
    finally AStr1.EndUpdate;
    end;
  end;

Для тестирования я использовал Embarcadero® Delphi 11 Version 28.0.46481.1287. 

Компьютер у меня не новый, но хороший:

Прежде, чем перейти к результатам тестирования, должен рассказать, что про замечательную

скорость словаря я прочитал в

https://blog.dummzeuch.de/2020/02/16/tstringlist-vs-thashedstringlist-vs-tdictionary/

Программа немецкого товарища, скачанная с его сайта, у меня показывает такие результаты:

TStringList

676: Add: 00:00:08.0883633

676: IndexOf: 00:00:08.0856404

THashedStringList

676: Add: 00:00:08.0273955

676: IndexOf: 00:00:01.6376979

TDictionary

676: Add: 00:00:00.9561740

676: IndexOf: 00:00:00.9005278

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

Я запускал на трёх генерациях списков конкурирующие процедуры  Mark1In2Hashed, Mark1In2Sorted и Mark1In2Dictio одну за одной по три раза, чтобы, не смотря на изменчивую вычислительную среду, видны были чёткие тенденции. 

Замер времени поиска в списке										Среднее
THashedStringList	3,158	3,151	3,168	3,219	3,083	3,167	3,176	3,081	3,142	3,149444444
TStringList	3,341	3,225	3,294	3,338	3,28	3,275	3,214	3,308	3,291	3,285111111
TDictionary	3,239	3,26	3,277	3,3	3,25	3,33	3,384	3,267	3,308	3,290555556

Как видно, использование всех трёх компонентов приводит к результату от трёх до трёх с половиной секунд. И сверхбыстрый THashedStringList выигрывает у TStringList менее 5%. Хвалёный же TDictionary оказался последним, а не первым. Вот и верь после этого людям!

Но что с "простым" методом Mark1In2? Он работал почти минуту - 58,335 секунд! Я, понятно, не стал его включать в серию испытаний. Но какая это прекрасная иллюстрация  беззаботности - почти минута вместо 3 с хвостиком секунд - разница почти в 20 раз!

Что же из этого следует?

Во-первых, громкое название не говорит о громкой победе: хэш-лист едва-едва выиграл у простого списка, а словарь вообще проиграл. Во-вторых, стоит помнить, что результаты сравнения драматически (вычитал такое слово) зависят от методики испытаний. И сюда же, но всё-таки в-третьих - непонятно, как это у "сумрачного гения" получается так подтасовывать карты?