Question/Proposal about/for TStringList lazarus / 62-General ---------------------------------------------------------------------- Zvoni · 2022-03-03 12:52 Hi Folks, if this topic is more for FPC-Development, then move it there. As a mental excersize i went a bit through the Sourcecode of TStringList/TStrings (Non-Generic), and noticed: If the StringList is sorted, a binary search is used (Find/IndexOf et al). If it's not sorted you can't even call Find directly, IndexOf et al use linear search. I was thinking about this, and had the following idea: If the StringList has to be unsorted (for whatever reason), would it make sense to keep an internal SORTED Array/StringList, which in its own TStringListItem stores the String and in its Object the Index/Position of the unsorted "Parent"? If we then use the searching functions (Find, IndexOf et al) on the unsorted List, it would just be a Check for its Sorted-Property, If True use the "original" List, if False do a Binary search on the internal List (which it would default to, since the internal Sorted- Property is always set to True) and return the Index from the Object- Member Thoughts? Opinions? I'm aware that in case of an unsorted List, Memory-usage would be "doubled", but would any performance-gains offset double Memory? ---------------------------------------------------------------------- Zvoni · 2022-03-03 15:37 Quote from: jamie on March 03, 2022, 03:36:59 pmIt needs indexoffirst and indexofnext to be added. I've already subclassed a stringlist that does that. Jamie, very nice. Something else i noticed: When you create a StringList, Duplicates is per Default set to dupIgnore. If the SL is not sorted it still allows Duplicates to be Added. That's IMO inconsistent behaviour ---------------------------------------------------------------------- Thaddy · 2022-03-03 15:40 Quote from: Zvoni on March 03, 2022, 01:52:14 pmI'm aware that in case of an unsorted List, Memory-usage would be "doubled", but would any performance-gains offset double Memory? Then you are not very aware. Memory usage is the same. The difference is between a sequential search (unsorted, O(N)) and a binary search(sorted, O(logN)) ---------------------------------------------------------------------- Zvoni · 2022-03-03 16:36 Quote from: Thaddy on March 03, 2022, 04:40:54 pmQuote from: Zvoni on March 03, 2022, 01:52:14 pmI'm aware that in case of an unsorted List, Memory-usage would be "doubled", but would any performance-gains offset double Memory? Then you are not very aware. Memory usage is the same. The difference is between a sequential search (unsorted, O(N)) and a binary search(sorted, O(logN)) Thaddy, I meant „double“ memory for the internal sorted list, since we would have all data twice, more or less ---------------------------------------------------------------------- marcov · 2022-03-03 20:28 You solve one problem (fast search), you however also propagate a problem of a sorted tstringlist to the unsorted one, which would break peoples programs. That problem is that the sorted tstringlist has horrible insertion performance for higher counts (noticable starting from 100k lines) ---------------------------------------------------------------------- Thaddy · 2022-03-03 20:45 Quote from: Zvoni on March 03, 2022, 05:36:58 pmI meant „double“ memory for the internal sorted list, since we would have all data twice, more or less That is not the case. Memory is the same. ---------------------------------------------------------------------- Zvoni · 2022-03-04 08:05 Quote from: Thaddy on March 03, 2022, 09:45:11 pmQuote from: Zvoni on March 03, 2022, 05:36:58 pmI meant „double“ memory for the internal sorted list, since we would have all data twice, more or less That is not the case. Memory is the same. Thaddy, you'll have to explain that one. If i have a "custom" unsorted StringList with 100K Entries, and i have an internal SORTED List (as a Field) with the same 100K Entries, how is that not "double" memory? Quote from: marcovYou solve one problem (fast search), you however also propagate a problem of a sorted tstringlist to the unsorted one, which would break peoples programs. That problem is that the sorted tstringlist has horrible insertion performance for higher counts (noticable starting from 100k lines) How do you figure that? I was under the impression, that Inserts in a sorted StringList calls the Find-Method which uses Binary search to return the Index at which to perform the Insert ---------------------------------------------------------------------- Zvoni · 2022-03-04 08:09 Something else (which i posted in Post 3): IMO, it's inconsistent behaviour for unsorted StringList with Duplicates set to dupIgnore, that it still allows Duplicates. dupIgnore only works on sorted StringList, which doesn't make sense to me. As far as i could see dupAccept is never used I would even propose an addition of a "dupReplace" (especially for Key/Values) Thoughts? ---------------------------------------------------------------------- Thaddy · 2022-03-04 08:16 Quote from: Zvoni on March 04, 2022, 09:09:55 amSomething else (which i posted in Post 3): IMO, it's inconsistent behaviour for unsorted StringList with Duplicates set to dupIgnore, that it still allows Duplicates. dupIgnore only works on sorted StringList, which doesn't make sense to me. As far as i could see dupAccept is never used I would even propose an addition of a "dupReplace" (especially for Key/Values) Thoughts? Ignore means it is allowed.... That is consistent. Accept means it should be processed, not skipped, even if.. And we have already addorreplace... (I think, Have to look that up. At least the rtl-generics handle that) ---------------------------------------------------------------------- PascalDragon · 2022-03-04 08:30 Quote from: Zvoni on March 04, 2022, 09:09:55 amSomething else (which i posted in Post 3): IMO, it's inconsistent behaviour for unsorted StringList with Duplicates set to dupIgnore, that it still allows Duplicates. dupIgnore only works on sorted StringList, which doesn't make sense to me. As far as i could see dupAccept is never used This is documented behavior. And dupAccept is handled implicitly through TStringList.Find. Quote from: Zvoni on March 04, 2022, 09:09:55 amI would even propose an addition of a "dupReplace" (especially for Key/Values) The Duplicates property works on the whole entry, but a dupReplace would only work on the name, thus this would be a completely different behaviour and for that case you can already use SomeString.Values['FooBar'] := 'Blubb'. Quote from: Thaddy on March 03, 2022, 09:45:11 pmQuote from: Zvoni on March 03, 2022, 05:36:58 pmI meant „double“ memory for the internal sorted list, since we would have all data twice, more or less That is not the case. Memory is the same. Zvoni suggested to use an additional array that contains indices. So yes, memory usage would be larger in that case. ---------------------------------------------------------------------- Zvoni · 2022-03-04 08:38 Quote from: PascalDragon on March 04, 2022, 09:30:16 amThis is documented behavior. And dupAccept is handled implicitly through TStringList.Find.PD, thank you. I missed the last line on that page. So, basically, if i want to allow Duplicates in a sorted StringList, i explicitly have to set it to dupAccept? Quote from: PascalDragonQuote from: Zvoni on March 04, 2022, 09:09:55 amI would even propose an addition of a "dupReplace" (especially for Key/Values) The Duplicates property works on the whole entry, but a dupReplace would only work on the name, thus this would be a completely different behaviour and for that case you can already use SomeString.Values['FooBar'] := 'Blubb'.My "dupReplace" was more for the AddPair et al Methods. Think of a sorted StringList with Key/Values being added with AddPair (or whatever other Method), and some calls later, the same key is used again (for whatever reason), but this time with a different value. Currently, this entry is ignored, while the user might think it will replace the old value. In case of simple strings (No Key/Values) it would be more or less a no-op But i'll admit it's just something that struck me, and it's not really a bone of contention for me ---------------------------------------------------------------------- PascalDragon · 2022-03-04 09:27 Quote from: Zvoni on March 04, 2022, 09:38:03 amQuote from: PascalDragon on March 04, 2022, 09:30:16 amThis is documented behavior. And dupAccept is handled implicitly through TStringList.Find.PD, thank you. I missed the last line on that page. So, basically, if i want to allow Duplicates in a sorted StringList, i explicitly have to set it to dupAccept? Correct. Quote from: Zvoni on March 04, 2022, 09:38:03 amQuote from: PascalDragonQuote from: Zvoni on March 04, 2022, 09:09:55 amI would even propose an addition of a "dupReplace" (especially for Key/Values) The Duplicates property works on the whole entry, but a dupReplace would only work on the name, thus this would be a completely different behaviour and for that case you can already use SomeString.Values['FooBar'] := 'Blubb'.My "dupReplace" was more for the AddPair et al Methods. And Duplicates is for Add.