How to speed up the search for name / value pairs in Delphi TStringList?

Question

I implemented a language translation in the application by putting all the lines at runtime in a TStringList using:

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; 

In any case, with this approach, it takes about 30 microseconds to find a record, is there a better way to achieve the same result?

UPDATE: for future reference, I am writing a new implementation here 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 runs 1000 times faster (on my 2000 samples), and then in the first version.

Answer 1

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

Answer 2

THashedStringList should be better, I think.

Answer 3

If THashedStringList works for you, that's great. His biggest weakness is that every time you change the contents of a list, the Hash table is rebuilt. This way, it will work for you as long as your list remains small or changes very often.

For more information on this, see the ThashedStringList weakness , which provides several alternatives.

If you have a large list that can be updated, you can try GpStringHash gabr , which should not re- compose the entire table with every change.

Answer 4

I think you are not using EnglishStringList (TStringList) correctly. This is a sorted list, you add elements (strings), sort them, but when you search, you do this with a partial string (only with the name IndexOfName ).

If you use IndexOfName in a sorted list, TStringList cannot use Dicotomic search. It uses sequential search.

(this is an 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 this is the reason for poor performance.
An alternative is to use 2 TStringList:
* The first (sorted) contains only the "Name" and a pointer to the second list containing the value; You can implement this pointer to the second list using the "pointer" of the Object property.
* The second (unsorted) list contains values.

When you search, you do this in the first list; In this case, you can use the Find method. when you find a name, a pointer (implemented using the Object property) gives you a position in the second list with a value.

In this case, the search method in the Sorted List is more efficient for the HashList (which must execute the function in order to get the position of the value).

Sincerely.

Pd: Sorry about my mistakes with English.

Answer 5

You can also use CLASS HELPER to reprogram 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 the TStrings streaming class if you don't like CLASS HELPERs or don't have them in your Delphi version).

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