How can I search faster for name/value pairs in a Delphi TStringList?

Question

I implemented language translation in an application by putting all strings at runtime in a TStringList with:

procedure PopulateStringList;
begin  
  EnglishStringList.Append('CAN_T_FIND_FILE=It is not possible to find the file');
  EnglishStringList.Append('DUMMY=Just a dummy record');
  // total of 2000 record appended in the same way
  EnglishStringList.Sorted := True; // Updated comment: this is USELESS!
end;

Then I get the translation using:

function GetTranslation(ResStr:String):String;
var
  iIndex : Integer;
begin
  iIndex := -1;
  iIndex :=  EnglishStringList.IndexOfName(ResStr);
  if iIndex >= 0 then
  Result :=  EnglishStringList.ValueFromIndex[iIndex] else
  Result := ResStr + ' (Translation N/A)';
end;

Anyway with this approach it takes about 30 microseconds to locate a record, is there a better way to achieve the same result?

UPDATE: For future reference I write here the new implementation that uses TDictionary as suggested (works with Delphi 2009 and newer):

procedure PopulateStringList;
begin  
  EnglishDictionary := TDictionary<String, String>.Create;
  EnglishDictionary.Add('CAN_T_FIND_FILE','It is not possible to find the file');
  EnglishDictionary.Add('DUMMY','Just a dummy record');
  // total of 2000 record appended in the same way
end;


function GetTranslation(ResStr:String):String;
var
  ValueFound: Boolean;
begin
  ValueFound:=  EnglishDictionary.TryGetValue(ResStr, Result);
  if not ValueFound then Result := Result + '(Trans N/A)';
end;

The new GetTranslation function performs 1000 times faster (on my 2000 sample records) then the first version.

Answer 1

THashedStringList should be better, I think.

Answer 2

If THashedStringList works for you, that's great. Its biggest weakness is that every time you change the contents of the list, the Hash table is rebuilt. So it will work for you as long as your list remains small or doesn't change very often.

For more info on this, see: THashedStringList weakness, which gives a few alternatives.

If you have a big list that may be updated, you might want to try GpStringHash by gabr, that doesn't have to recompute the whole table at every change.

Answer 3

Hello.
I think that you don't use the EnglishStringList(TStringList) correctly. This is a sorted list, you add elements (strings), you sort it, but when you search, you do this by a partial string (only the name, with IndexOfName).

If you use IndexOfName in a sorted list, the TStringList can't use Dicotomic search. It use sequential search.

(this is the implementation of IndexOfName)

  for Result := 0 to GetCount - 1 do
  begin
    S := Get(Result);
    P := AnsiPos('=', S);
    if (P <> 0) and (CompareStrings(Copy(S, 1, P - 1), Name) = 0) then Exit;
  end;

I think that this is the reason of poor performance.
The alternative is use 2 TStringList:
* The first (sorted) only containts the "Name" and a pointer to the second list that contain the value; You can implement this pointer to the second list using the "pointer" of Object property.
* The second (not sorted) list containt the values.

When you search, you do it at first list; In this case you can use the Find method. when you find the name, the pointer (implemented with Object property) give you the position on second list with the value.

In this case, Find method on Sorted List is more efficient that HashList (that must execute a funcion to get the position of a value).

Regards.

Pd:Excuse-me for mistakes with english.

Answer 4

In Delphi 2009 or later I would use TDictionary< string,string > in Generics.Collections. Also note that there are free tools such as http://dxgettext.po.dk/ for translating applications.

Answer 5

You can also use a CLASS HELPER to re-program the "IndexOfName" function:

TYPE
  TStringsHelper = CLASS HELPER FOR TStrings
                     FUNCTION IndexOfName(CONST Name : STRING) : INTEGER;
                   END;

FUNCTION TStringsHelper.IndexOfName(CONST Name : STRING) : INTEGER;
  VAR
    SL  : TStringList ABSOLUTE Self;
    S,T : STRING;
    I   : INTEGER;

  BEGIN
    IF (Self IS TStringList) AND SL.Sorted THEN BEGIN
      S:=Name+NameValueSeparator;
      IF SL.Find(S,I) THEN
        Result:=I
      ELSE IF (I<0) OR (I>=Count) THEN
        Result:=-1
      ELSE BEGIN
        T:=SL[I];
        IF CompareStrings(COPY(T,1,LENGTH(S)),S)=0 THEN Result:=I ELSE Result:=-1
      END;
      EXIT
    END;
    Result:=INHERITED IndexOfName(Name)
  END;

(or implement it in a descendant TStrings class if you dislike CLASS HELPERs or don't have them in your Delphi version).

This will use a binary search on a sorted TStringList and a sequential search on other TStrings classes.