Lazarus

Free Pascal => Beginners => Topic started by: Eugene Loza on January 30, 2018, 12:41:54 am

Title: [SOLVED] Generics.Collections TDictionary indexed access
Post by: Eugene Loza on January 30, 2018, 12:41:54 am
Hi all!
I'm using Generics.Collections from FPC3.1.1 (trunk) and I need to access a random item in a TObjectDictionary. What is the correct syntax to? EQ := AllData.Items[index] (like in TObjectList) raises error "Dictionary key does not exist".
And another question:
Are items in TObjectDictionary stored sorted by the key? E.g. that the i+1 value would have key > than that of i-th element. (Key is TDateTime).

Actually, using a sorted TObjectList in the code should work for me too, but TObjectDictionary is practically a bit better in my case.
Title: Re: Generics.Collections TDictionary indexed access
Post by: Thaddy on January 30, 2018, 08:12:44 am
A dictionary index is of type TKey, not of type integer.
You can use TObjectList<T> if you need access by ordinal index.
Title: Re: Generics.Collections TDictionary indexed access
Post by: marcov on January 30, 2018, 10:32:32 am
Dictionaries are not sorted, but you can iterate them, just do

for x in dict.values do
  ...

For ordered collections I use my own lightmap, which I later made somewhat compatible to tdictionary (basic methods and properties have the same name).

Though as principle it is more a generic tstringlist like map.

http://www.stack.nl/~marcov/lightcontainers.zip

Note that the demoes haven't been updated to use the Tdictionary like methods (like addobject and trygetvalue and .values etc), but use the older equivalent putpair and locate.

Title: Re: Generics.Collections TDictionary indexed access
Post by: Eugene Loza on January 31, 2018, 03:27:21 pm
Thanks a lot, Thaddy, marcov!
I'll stick with a sorted TObjectList then.
Title: Re: Generics.Collections TDictionary indexed access
Post by: piola on September 20, 2021, 07:34:16 pm
For ordered collections I use my own lightmap, which I later made somewhat compatible to tdictionary (basic methods and properties have the same name).

Hello @marcov,

I stumbled upon your genlight TLightMap by chance which seems to solve my problem of not being able to get a TDictionary in a sorted way. As far as I can understand, the iterator over keys or values returns those in sorted order in your implementation.

What'd be the best way to directly access the i-th key or i-th value (something like ValueOfIndex in TStringList)? I don't that creating an iterator and skipping the first i-1 keys or values would be the best choice. What do you recommend?
Title: Re: Generics.Collections TDictionary indexed access
Post by: marcov on September 20, 2021, 10:25:55 pm
What'd be the best way to directly access the i-th key or i-th value (something like ValueOfIndex in TStringList)? I don't that creating an iterator and skipping the first i-1 keys or values would be the best choice. What do you recommend?

Needing that abstraction eats speed, Lightmap is constructed to not worry about that.
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: piola on September 20, 2021, 11:37:18 pm
Yes, thanks for that point. But in my case, an indexed access is more important than a small decrease in speed. I do not expect you to do my work, but maybe you'd give me a hint on how to do it.

Currently I'm getting an iterator and throw the first i-1 elements away to get the i-th one. But I think there has to be a much more elegant solution, depending on how the data is managed internally. I already had a look into that but I'm not sure how to use it correctly.
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: marcov on September 21, 2021, 12:21:07 pm
Currently I'm getting an iterator and throw the first i-1 elements away to get the i-th one. But I think there has to be a much more elegant solution, depending on how the data is managed internally. I already had a look into that but I'm not sure how to use it correctly.

Keep in mind that the lightmap is basically an array of arrays, and the iterator only revisits the lightmap structures when it changes from array to array, not every element.  It stores how many elements left in the current array in the iterator.

The problem is that this kind of fast iteration requires state (current array, how many elements left in it etc), and a for loop has no state except the loopvar. Which is why the iterator works this way (and later, with FOR..IN support to simplify syntax)

Most clean loopvar solutions will have the same problem (and speed degradation) as the multiple iterator solution. I never saw an elegant solution. Moreover, indexes in a ordered collection are void anyway if a value is added.

Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: Zvoni on September 21, 2021, 12:38:50 pm
A more general Question:
If a List is sorted (whatever Object/Container used for it), wouldn't a binary search of the key be the fastest (if you don't have direct access via Index)?
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: Thaddy on September 21, 2021, 01:09:17 pm
The binary search is fastest on small to medium sized lookups, but it may be that other searches are faster on very small or very large content. What average size do you need?
Do you sort from memory or from storage?
E.g. on very large data a heapsort or treesort may be faster and on very small data ( < 10 or so) even a bubble sort may be faster. It always pays to have a sorting library available and to test the real world performance.
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: marcov on September 21, 2021, 01:15:07 pm
A more general Question:
If a List is sorted (whatever Object/Container used for it), wouldn't a binary search of the key be the fastest (if you don't have direct access via Index)?

Yes. And that is what it does. (searchblock and binsearch methods for resp the first and second level array).

Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: marcov on September 21, 2021, 01:18:51 pm

E.g. on very large data a heapsort may be faster

Binary search is O(log(n)).   heapsort is O(n*log(n))  So that is not logical.

Maybe insertion sort vs heapsort you have a point, but I generally persist the data sorted, and appending to the collection is then not related to ordering.
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: Thaddy on September 21, 2021, 01:21:14 pm
The reason I mentioned heapsort sort is the likeliness of worst case occurance in large data.
Hence I will always try several algorithms to test my data unless I know what kind of sort is best fit for my data. Over the past decades I have found some surprises, you probably did too, Marco  :D
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: Zvoni on September 21, 2021, 02:37:09 pm
The binary search is fastest on small to medium sized lookups, but it may be that other searches are faster on very small or very large content. What average size do you need?
Do you sort from memory or from storage?
E.g. on very large data a heapsort or treesort may be faster and on very small data ( < 10 or so) even a bubble sort may be faster. It always pays to have a sorting library available and to test the real world performance.
I didn't ask for myself. More as food for thought for the OP, since i read it that he is "just" looping through the list from one end to the other until he hits

EDIT: errr.... second OP.... piola
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: piola on September 21, 2021, 06:39:18 pm
Keep in mind that the lightmap is basically an array of arrays, and the iterator only revisits the lightmap structures when it changes from array to array, not every element.  It stores how many elements left in the current array in the iterator.

This a very helpful hint, thank you. And I may assume that the arrays are filled in sorted order?
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: avk on September 21, 2021, 06:51:31 pm
Quote from: Posted by: piola on: September 20, 2021, 11:37:18 pm
Yes, thanks for that point. But in my case, an indexed access is more important than a small decrease in speed. I do not expect you to do my work, but maybe you'd give me a hint on how to do it.

Currently I'm getting an iterator and throw the first i-1 elements away to get the i-th one. But I think there has to be a much more elegant solution, depending on how the data is managed internally. I already had a look into that but I'm not sure how to use it correctly.
Isn't this (https://github.com/avk959/LGenerics/blob/3b3340008f6affd03611869e0c1f175389b9a78d/lgenerics/lgtreap.pas#L103) the approach you asked?
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: piola on September 21, 2021, 07:10:11 pm
Isn't this (https://github.com/avk959/LGenerics/blob/3b3340008f6affd03611869e0c1f175389b9a78d/lgenerics/lgtreap.pas#L103) the approach you asked?

Hmm... didn't know about LGenerics, thank you. The problem is that there are dozens (or even hundreds) of TDictionary, THashMap,... implementations and probably none of them can handle everythin  ;D
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: piola on September 21, 2021, 07:11:35 pm
Meanwhile I have come to the following code:

Code: Pascal  [Select][+][-]
  1. function TLightDictionary<tkey, tvalue>.getItems(Index: integer): TKey;
  2. var blknr   : integer;
  3. begin
  4.   blknr:=0;
  5.   if nrblocks=0 then Raise EListError.CreateFmt('No name=value pair at position %d.',[Index]);
  6.   while (blknr<=nrblocks) and (Index>blks[0].Entries) do begin
  7.     dec(Index,blks[0].Entries);
  8.     inc(blknr);
  9.     if blknr=nrblocks then Raise EListError.CreateFmt('No name=value pair at position %d.',[Index]);
  10.   end;
  11.   if Index>blks[blknr].Entries then Raise EListError.CreateFmt('No name=value pair at position %d.',[Index]);
  12.   result:=blks[blknr].keys[Index];
  13. end;
  14.  

Maybe marcov could confirm that it is compatible with the way GenLight works  O:-)
Title: Re: [SOLVED] Generics.Collections TDictionary indexed access
Post by: marcov on September 21, 2021, 08:46:34 pm
This a very helpful hint, thank you. And I may assume that the arrays are filled in sorted order?

Yes.
TinyPortal © 2005-2018