Fast accessing maps

[jacdelad]

Hi #PB_All,
due to a currently ongoing discussion about maps I decided to take a look at the help, which raised two questions:
Firstly, the help states

Once an element as been accessed or created, it becomes the current element of the map, and further access to this element can be done without specify the key. This is useful when using structured map, as no more element lookup is needed to access different structure field.

Does this mean that

Code: Select all

Cars("Ferrari F40")\Weight = 1000
  Cars()\Speed = 320
  Cars()\Price = 500000

is faster than

Code: Select all

Cars("Ferrari F40")\Weight = 1000
  Cars("Ferrari F40")\Speed = 320
  Cars("Ferrari F40")\Price = 500000

?

Secondly, I can define how many slots are preoccupied/predefined on creation. Can I change that afterwards, like redimming an array? I know that I simply can add as many elements as I want to, but from how I understand it, it should be faster to preoccupy more slots beforehand, if that's possible.

[wilbert]

Does this mean that ... is faster than ... ?

Yes, the first approach is a lot faster.

Secondly, I can define how many slots are preoccupied/predefined on creation. Can I change that afterwards, like redimming an array?

No, you can't change that.
A map uses a (hash) function on the key you pass to find out in what slot it has to be placed.
Changing the amount of slots afterwards would require every existing key inside the map to be processed again to find out to what new slot it should be moved.

[AZJIO]

We had a discussion about what a slot is. The number of slots does not limit the number of card elements. Is this some kind of cache with which a preliminary search is done? For example, we take every tenth or every hundredth element and its position, and when searching, we find a slot whose hash is greater than the one we are looking for, and the previous one is less, and then we search inside a certain area?

[Demivec]

We had a discussion about what a slot is. The number of slots does not limit the number of card elements. Is this some kind of cache with which a preliminary search is done? For example, we take every tenth or every hundredth element and its position, and when searching, we find a slot whose hash is greater than the one we are looking for, and the previous one is less, and then we search inside a certain area?

A 'slot' is a distinct result of a hash function. The default of 512 slots means that only 512 distinct values will result from hashing any value (only strings are currently possible as map keys).

If more than one element is added to the map and they have different keys that result in the same hash then they will form an effective linked list at that hash slot value. This means that when the map is searched to see if a key is present that the key is first hashed to see which slot to look in and then each value in the list at that slot is checked for a matching key.

Fewer slots will result in longer lists at each slot. This will result in more interations through elements at each slot each time elements are searched, added or deleted.

A rough estimation of the memory space needed for the structure of a map is a list element structure consisting of three pointers (*mapElement, *previousSlotEListlement, nextSlotListElement) for each slot plus an identical structure for each element linked into the same slot. ElementsCount * (ElementSize + SlotListElementSize) with no less than (SlotsCount * SlotListElementSize) being used regardless of ElementsCount.

I haven't done any empiracle memory tests to see how close these estimates correspond with reality but I am confident they are reasonably close. I will test them when I am able to. I believe others have done similar estimations in the forum before.

[benubi]

I would expect the first version to be faster, because in the second approach the hash-value will be calculated 3x, when in the first it is 1x and then the current element is used 2x as a shortcut (without comparing hash values or calculating it).

[NicTheQuick]

I would expect the first version to be faster, because in the second approach the hash-value will be calculated 3x, when in the first it is 1x and then the current element is used 2x as a shortcut (without comparing hash values or calculating it).

Exactly. And that's what the help page talks about.

Of course this method only works either with only one single thread using the map at all times or when protecting the map with mutexes.

[jacdelad]

Oh, that's some light on the topic. I would expect the first approach to be faster too, or at least not slower. I'll have to change some of my programs, I never thought about that.

[wilbert]

Oh, that's some light on the topic. I would expect the first approach to be faster too, or at least not slower. I'll have to change some of my programs, I never thought about that.

You are all right.
I answered the question with yes but made a mistake in typing second instead of first.
Of course the FIRST approach is the faster one.

[jacdelad]

Ah ok. Thanks for clearing up.