Recent

Author Topic: [SOLVED] Generics.Collections TDictionary indexed access  (Read 10641 times)

Eugene Loza

  • Hero Member
  • *****
  • Posts: 656
    • My games in Pascal
[SOLVED] Generics.Collections TDictionary indexed access
« 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.
« Last Edit: January 31, 2018, 03:27:33 pm by Eugene Loza »
My FOSS games in FreePascal&CastleGameEngine: https://decoherence.itch.io/ (Sources: https://gitlab.com/EugeneLoza)

Thaddy

  • Hero Member
  • *****
  • Posts: 14157
  • Probably until I exterminate Putin.
Re: Generics.Collections TDictionary indexed access
« Reply #1 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.
Specialize a type, not a var.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11351
  • FPC developer.
Re: Generics.Collections TDictionary indexed access
« Reply #2 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.


Eugene Loza

  • Hero Member
  • *****
  • Posts: 656
    • My games in Pascal
Re: Generics.Collections TDictionary indexed access
« Reply #3 on: January 31, 2018, 03:27:21 pm »
Thanks a lot, Thaddy, marcov!
I'll stick with a sorted TObjectList then.
My FOSS games in FreePascal&CastleGameEngine: https://decoherence.itch.io/ (Sources: https://gitlab.com/EugeneLoza)

piola

  • Full Member
  • ***
  • Posts: 118
  • Lazarus 2.2, 64bit on Windows 8.1 x64
Re: Generics.Collections TDictionary indexed access
« Reply #4 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?

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11351
  • FPC developer.
Re: Generics.Collections TDictionary indexed access
« Reply #5 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.

piola

  • Full Member
  • ***
  • Posts: 118
  • Lazarus 2.2, 64bit on Windows 8.1 x64
Re: [SOLVED] Generics.Collections TDictionary indexed access
« Reply #6 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.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11351
  • FPC developer.
Re: [SOLVED] Generics.Collections TDictionary indexed access
« Reply #7 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.


Zvoni

  • Hero Member
  • *****
  • Posts: 2300
Re: [SOLVED] Generics.Collections TDictionary indexed access
« Reply #8 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)?
One System to rule them all, One Code to find them,
One IDE to bring them all, and to the Framework bind them,
in the Land of Redmond, where the Windows lie
---------------------------------------------------------------------
Code is like a joke: If you have to explain it, it's bad

Thaddy

  • Hero Member
  • *****
  • Posts: 14157
  • Probably until I exterminate Putin.
Re: [SOLVED] Generics.Collections TDictionary indexed access
« Reply #9 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.
« Last Edit: September 21, 2021, 01:19:50 pm by Thaddy »
Specialize a type, not a var.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11351
  • FPC developer.
Re: [SOLVED] Generics.Collections TDictionary indexed access
« Reply #10 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).


marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11351
  • FPC developer.
Re: [SOLVED] Generics.Collections TDictionary indexed access
« Reply #11 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.

Thaddy

  • Hero Member
  • *****
  • Posts: 14157
  • Probably until I exterminate Putin.
Re: [SOLVED] Generics.Collections TDictionary indexed access
« Reply #12 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
« Last Edit: September 21, 2021, 01:24:29 pm by Thaddy »
Specialize a type, not a var.

Zvoni

  • Hero Member
  • *****
  • Posts: 2300
Re: [SOLVED] Generics.Collections TDictionary indexed access
« Reply #13 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
One System to rule them all, One Code to find them,
One IDE to bring them all, and to the Framework bind them,
in the Land of Redmond, where the Windows lie
---------------------------------------------------------------------
Code is like a joke: If you have to explain it, it's bad

piola

  • Full Member
  • ***
  • Posts: 118
  • Lazarus 2.2, 64bit on Windows 8.1 x64
Re: [SOLVED] Generics.Collections TDictionary indexed access
« Reply #14 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?

 

TinyPortal © 2005-2018