TStrings.IndexOfName / TStringList lazarus / 62-General ---------------------------------------------------------------------- marcodor · 2015-07-04 11:37 I think speed of IndexOfName function can be greatly improved in TStringList descendant if list is sorted. Instead doing a natural scan of all items we may go with a quick find in a sorted list. ---------------------------------------------------------------------- jc99 · 2015-07-04 13:02 Quote from: marcodor on July 04, 2015, 01:37:35 pmI think speed of IndexOfName function can be greatly improved in TStringList descendant if list is sorted. Instead doing a natural scan of all items we may go with a quick find in a sorted list. I think for this you could use other descendents of TStrings. Like ... ? (I think there was something like TSortedList or TBucketlist but I could'nt find any of these in the Wiki ) But I remember a Demo, comparing these three (Maybe it's something tied to Delphi) But each of this has it Up's and Down's (mem-usage, speed of specific activity e.G: inserting, rearranging, generating, reading, ...  ) The TStringList itself should be left alone. e.G: if you want to load some source-code into TStringlist, it's definitly NOT a good Idea to have this sorted. but using 'IndexOfName' is normaly no good option either on that. ---------------------------------------------------------------------- typo · 2015-07-04 13:22 If you need fast lookup without the need of a sorted list, have a look at TDictionaryStringList and see if it helps. http://wiki.lazarus.freepascal.org/LazUtils#TDictionaryStringList ---------------------------------------------------------------------- marcodor · 2015-07-04 14:07 JC99, Why TStringList.IndexOf perform a binary search while IndexOfName not? I asked this, because TStrings.Values[ internally uses IndexOfName. Reading a large config section with TIniFile.ReadSectionValues( and after that sorting it will speedup later access of Strings.Values['option'] I really see no problems implementing indexed search for IndexOfName in TStringList especially most code is already done for IndexOf. Also I suppose IndexOfName is used in many parts/projects (maybe Lazarus itself), so it should improve things. ---------------------------------------------------------------------- jc99 · 2015-07-04 14:34 Maybe someone could help me out, but if i remember correctly TStringList does NOT do a binary-search what it does, it goes through a hash-list which is nearly as effective (maybe even more) as a binary search. But this can only be done with a full string. So you need to use a class that does (also) a hashing of the KeyNames. And as typo suggested TDictionaryStringList might help you in this. ---------------------------------------------------------------------- marcodor · 2015-07-04 14:43 Jc99, I just analyzed sources, stringl.inc. In sourcecode comments there is // Use binary search List is divided in 2 segments, looks for bounds where searched string may be and "good" segment is divided again until find matched item. ---------------------------------------------------------------------- jc99 · 2015-07-05 00:07 Quote from: marcodor on July 04, 2015, 04:43:49 pmJc99, I just analyzed sources, stringl.inc. In sourcecode comments there is // Use binary search List is divided in 2 segments, looks for bounds where searched string may be and "good" segment is divided again until find matched item. The normal stringlist does this only If the List is sorted. With sorted=false it Calls the inherited function. Which does a linear search. But You are right, If the List is sorted a binary search for the keyname is theoretically posible. IndexOfName is passed to Tstrings which performs a linear search. ---------------------------------------------------------------------- marcodor · 2015-07-05 08:50 I'm ready to contribute with a patch if core-devs agree. ---------------------------------------------------------------------- JuhaManninen · 2015-07-05 13:17 Quote from: marcodor on July 05, 2015, 10:50:36 amI'm ready to contribute with a patch if core-devs agree. I personally think it is a good idea but I am not a FPC developer. You can open a ticket in bug tracker with a patch and see what happens. Search the existing tickets first. In any case this is NOT an important feature because TStringList is a wrong class for fast Key-Value lookups. THashedStringList (unit IniFiles) uses the same API but is fast. Then there is TStringToStringTree (LazUtils, unit AvgLvlTree). It is fast balanced tree and more memory efficient than a hash map. And there are more hash maps... There was wrong information about TDictionaryStringList given by "typo" which I find strange because he is the co-author of that component. It does not support fast Key-Value lookups, although I admit the class name is misleading. I realized it only afterwards. If somebody comes up with a better name, we can still change it. ---------------------------------------------------------------------- marcov · 2015-07-05 13:36 Quote from: marcodor on July 05, 2015, 10:50:36 amI'm ready to contribute with a patch if core-devs agree. Maybe it is smartest to first check how Delphi handles this. TStringlist is a complex beast because of compatibility. ---------------------------------------------------------------------- skalogryz · 2015-07-05 14:22 I actually had to modify TStrings for key-lookup purposes.  To make it act as associated array. However, I never implemented it to be dependent on the list being sorted by names. As well as it would work for "named" values as well as non-named values. So both "indexof" and "IndexofName" work the in same manner. Yes, two hash lists have to be maintained accurately in order for this to work, that does some impact on memory consumption. ---------------------------------------------------------------------- JuhaManninen · 2015-07-05 14:33 Quote from: skalogryz on July 05, 2015, 04:22:21 pmI actually had to modify TStrings for key-lookup purposes.  To make it act as associated array. THashedStringList in IniFiles already does that. ---------------------------------------------------------------------- skalogryz · 2015-07-05 15:10 indeed. What an improper place for THashedStringList [Edit] Actually, it's probably the class name that's not quite accurate. THashedStringList is based on the TFPHashList. FPHashList has a limitation of using shortstring as look-up key. Using only 256 ansi characters string is totally fine for .ini files (unless .ini file is machine-generated for whatever crazy tasks), but on the wide scope, one might need to lookup for values that are more than 256 characters. Especially with UTF8 used for LCL. ---------------------------------------------------------------------- jc99 · 2015-07-05 17:00 Quote from: skalogryz on July 05, 2015, 05:10:01 pmindeed. What an improper place for THashedStringList +1 At the moment I work with ValueListEditor. It uses a TStringlist- descendent named TValueListStrings which uses the TString.IndexOfName- method to derive the keynames and values. even GetItemProp uses the TString.IndexOfName. Making the TValueListStrings a  THashedStringList -descendent would be much better. But then the unit ValEdit would be a descendent of inifiles what is not a good thing and hardly understandable. I'd vote for an independent unit e.G: HashStrLst so that inifiles, valedit and any other component that needed this could descend from that. Quote from: skalogryz on July 05, 2015, 05:10:01 pm[Edit] Actually, it's probably the class name that's not quite accurate. THashedStringList is based on the TFPHashList. FPHashList has a limitation of using shortstring as look-up key. Using only 256 ansi characters string is totally fine for .ini files (unless .ini file is machine-generated for whatever crazy tasks), but on the wide scope, one might need to lookup for values that are more than 256 characters. Especially with UTF8 used for LCL. Using only the first 256 character to generate the hash would only be a problem if you have lot of keynames that have the same start and only differ after the 256 character. The only case i could think of that is if you want to hash the place of files in a full path, to give them some extra property. But in that case other components are much more appropriate. In the normal-ini-file-case i see  no need to change something. @marcov: I just looked in the Delphi-RTL, TStrings and TStringlist act quite like their Lazarus-siblings. TStrings does a linear search on both indexof and IndexOfName. TStringlist only does a binary-search in indexof via the find-method when the list is sorted. So it's delphi-compatibility vs. better code. ( I go for the better code )   So sorry about the wrong info. @marcodor: I think you try something like: Code: [Select]// classesh.inc (Line 757 ff)     function IndexOf(const S: string): Integer; override;     function IndexOfName(const S: string): Integer; override; // <----     procedure Insert(Index: Integer; const S: string); override; // stringl.inc (line 1336 ff new) Function TStringList.IndexOfName(const S: string): Integer; begin   If Not Sorted then     Result:=Inherited indexOfName(S)   else     // faster using binary search...     begin        Find (S,Result); // This should work since Find outputs the L-Value.        if (Result >= Count) or (Names[Result] <> S) then            Result:= -1;     end; end; ---------------------------------------------------------------------- jc99 · 2015-07-05 18:35 BTW, TStringList.find always does a binary search even in an unsorted list. Is this really supposed to be that way ? [Edit] Could someone verify this ? Code: [Select]procedure TryFind(const S: string; const sl: TStringList); var   no: integer; begin   Write('Test "' + S);   if sl.find(S, no) then     writeln('" found: ' + IntToStr(no))   else   if no < sl.Count then     writeln('" not found: ' + IntToStr(no) + ' --> ' + sl.Names[no])   else     writeln('" not found: ' + IntToStr(no) + ' --! XXX '); end; procedure Execute; var   sl: TStringList; begin   sl := TStringList.Create;   try     sl.add('1=Test1');     sl.add('3=Test3');     sl.add('2=Test2');     TryFind('2=Test2', sl); // !!! string is not found !!!     sl.Sorted := True;     TryFind('2=Test2', sl); // Now it's found     TryFind('2', sl);     TryFind('0', sl);     TryFind('1', sl);     TryFind('2', sl);     TryFind('3', sl);     TryFind('4', sl);  // Result in sl.count   finally     FreeAndNil(sl);   end;   readln; end; ---------------------------------------------------------------------- marcodor · 2015-07-05 19:17 JuhaManninen, thanks for THashedStringList  hint, just checked implementation, will go with this class. Marcov, it should not break any Delphi compatibility, if function runs faster it's about optimization, not compatibility. So less arrogance please. Jc99, thanks for code. Anyway, instead having this already in THashedStringList it can also be improved in TStringList. If items are sorted, why not use it? Just 5 lines of code optimizations. ---------------------------------------------------------------------- jc99 · 2015-07-05 20:36 Quote from: marcodor on July 05, 2015, 09:17:11 pm[...] Jc99, thanks for code. Anyway, instead having this already in THashedStringList it can also be improved in TStringList. If items are sorted, why not use it? Just 5 lines of code optimizations. +1 and hey You did it in 5 lines ? Cool, please share. Quote from: jc99 on July 05, 2015, 08:35:31 pmBTW, TStringList.find always does a binary search even in an unsorted list. Is this really supposed to be that way ? [Edit] Could someone verify this ? --> [...] <--- Plz have a look at this. you put three strings in a stringlist and find does not find the last one (somtimes, when unsorted) ---------------------------------------------------------------------- typo · 2015-07-05 21:40 Quote from: JuhaManninen on July 05, 2015, 03:17:26 pmI admit the class name is misleading. I realized it only afterwards. If somebody comes up with a better name, we can still change it. TMappedStringList. ---------------------------------------------------------------------- howardpc · 2015-07-05 21:48 TUnsortedLookupStringList ---------------------------------------------------------------------- jc99 · 2015-07-05 22:13 @JuhaManninen: Since you say in the wiki: It's a Quote[...] TStringList with a fast lookup feature. TFastLookupStringList ---------------------------------------------------------------------- typo · 2015-07-05 22:25 jc99, you could take a look at TStringToStringTree. TDictionaryStringList is the best solution possible to deduplicate an unsorted list of strings. But I think you could use TStringToStringTree directly instead of using a TStringList for IndexOfName. If you want to know the index in order to get the value, with a map you get the value directly and the index does not matter. ---------------------------------------------------------------------- jc99 · 2015-07-05 23:09 Quote from: typo on July 06, 2015, 12:25:59 amjc99, you could take a look at TStringToStringTree. Yes: http://wiki.lazarus.freepascal.org/AVL_Tree But what's your point ? An AVL-Tree is an automatic balanced binary tree. I learned about/implemented these in the early 90's. ---------------------------------------------------------------------- jc99 · 2015-07-05 23:52 Quote from: typo on July 06, 2015, 12:25:59 amTDictionaryStringList is the best solution possible to deduplicate an unsorted list of strings. But I think you could use TStringToStringTree directly instead of using a TStringList for IndexOfName. If you want to know the index in order to get the value, with a map you get the value directly and the index does not matter. That depends how the map(ping) is implemented. If it is an AVL-Tree, than you get to the Data-node in O(log(n)) that's exactly the same as a binary search through a sorted list. The sorting of the list is normaly done in O(n log (n)). But building the Tree also takes O(n log(n)). Much worse is that Valuelist-editor uses TStringlist -> TStrings linear search to get to the value. That's quite a showstopper, if you use larger lists. With the new code you only have to sort the list, and then you can access the values nearly optimal. Without changing the code of the VLE-component.   And the thing with the Index is only because TStrings is implemented that way. ---------------------------------------------------------------------- JuhaManninen · 2015-07-07 12:22 I finally renamed TDictionaryStringList  -> TLookupStringList. Thanks for the suggestions. Typo's TMappedStringList was good except that it raised a question "mapped to what?" at least in my head. The others were too long IMO. Typo, if you know people who use the class, you can advertise the name change. Patches for ValueListEditor are welcome. It belongs to a different project than TStringList, Bart or myself can commit changes for it. ---------------------------------------------------------------------- typo · 2015-07-07 14:54 Thanks. ---------------------------------------------------------------------- typo · 2015-07-07 19:13 Quote from: JuhaManninen on July 07, 2015, 02:22:59 pmPatches for ValueListEditor are welcome. It belongs to a different project than TStringList, Bart or myself can commit changes for it. Where is the source? ---------------------------------------------------------------------- jc99 · 2015-07-07 20:17 Quote from: typo on July 07, 2015, 09:13:59 pmWhere is the source? ! ? ---------------------------------------------------------------------- typo · 2015-07-07 20:44 What is the problem? ---------------------------------------------------------------------- jc99 · 2015-07-07 21:08 Quote from: typo on July 07, 2015, 10:44:29 pmWhat is the problem? Exactly !? What do you mean by where is the source ? In the trunk ?! In the repository ?! ??? So I was a little bit puzzled. -------- Dude, what's on my back ? - Sweet, what's on my back ? - DUDE, what's on my back ? - SWEET ...... ---------------------------------------------------------------------- typo · 2015-07-07 21:09 The question was not addressed to you. Take care of your life.