MapIndex() and SelectMapElement()

[blueznl]

These two commands exist for linked lists, but not for maps.

Typically, these would allow things like this:

1. look up a map element
2. x = mapindex()
3. look up another element in the same hashtable
4. get some data
5. return to the first map element using SelectMapElement()

[Trond]

SelectMapElement() = FindMapElement()

MapIndex() = MapKey(). Maps don't have indexes, since they aren't ordered. The key functions as the index.

[blueznl]

Maps are ordered, otherwise the functions NextMapElement() and ResetMap() would not exist.

The two commands I request would allow storing a position of an element in a map, do another lookup in the map (note: a lookup, not a change or add, so the table will not change), then return to the position I was.

The reason why I ask this is that I suspect it's faster to temporary store current element position and later return to it, than it is to do another lookup. (As for a lookup first the string has to be hashed, then the table has to be searched).

See also my example above. If you ask who would abuse a map this way, well, I would

[Fred]

Well, trond is right, accessing a map element is quite fast.

[DarkDragon]

Maps are ordered, otherwise the functions NextMapElement() and ResetMap() would not exist.

Read some books about hashing please, before writing such sentences.
Btw.: NextMapElement and ResetMap doesn't guarantee to have an ordered output. Its just iterating over all. But usually you don't need this when using hashtables.

[srod]

Once you have a pointer to a map element (e.g. from FindMapElement()) then you have a pointer to a structure. Do what you want with it. Store it and you can return to it at any time without making reference to the map at all. This is generally how I make use of the map library, i.e. minimize the number of lookups etc. The fact that PB maps have 'current elements' is, to my mind, somewhat of a 'distraction' and I will rarely make use of that.

[blueznl]

Once you have a pointer to a map element (e.g. from FindMapElement())...

Doh! That might just do it, though I admit it's probably not a big speed increase all little bits just might help

I was just looking at ways to decrease the number of lookups, just as you did, but keeping my With / Endwith's intact and not resorting to pointers and structures.

(I just like these things to be part of the standard purebasic command set, yeah, I admit, I'm an *n*l r*t*nt*v* completists Oh, and all the addtional typing isn't appealing much either )

[Trond]

The reason why I ask this is that I suspect it's faster to temporary store current element position and later return to it, than it is to do another lookup. (As for a lookup first the string has to be hashed, then the table has to be searched).

If you want performance, SelectElement() is definetely the wrong way to go, with both lists and maps. Doing a new lookup will very likely be faster. Because to get to a certain item number in the hash table you have to loop through all elements from the start every time, unless some cache mecanism was used, and even then you'd have to look up the position in the cache instead of looking up the actual value, so it would be a waste.

[blueznl]

Trond, I already know the position (as I was already there) so I do not have to walk through the list, I can just jump there Perhaps I did not explain myself well enough.

[Trond]

Trond, I already know the position (as I was already there) so I do not have to walk through the list, I can just jump there Perhaps I did not explain myself well enough.

So how, exactly, do you jump to a position within a hash table? With SelectMapElement()? How, exactly, would that function be implemented?

Don't you know how linked lists/hash tables work? They are not laid out in order, so you cannot jump there.

It's even documented:

SelectElement() manual:
This is very useful if you want to jump to a specific position in the list without using an own loop for this.

As linked lists don't use an index, it will jump compulsory to every element until the target position is reached. If a faster method is needed, ChangeCurrentElement() should be used.

[blueznl]

Well, I *could* expect the system to keep a buffer internally, to speed up lookups when doing a selectelement() but hell, i've got no clue, which makes me a great source of new ideas no matter how brainless they might be. (I've not yet reached the lofty status of some participants, but hey, I'm working on it!)

[Trond]

I guess what you really want is ChangeCurrentElement(). But then again, if you have the pointer, you don't need the element.

[netmaestro]

Read some books about hashing please, before writing such sentences.
Btw.: NextMapElement and ResetMap doesn't guarantee to have an ordered output. Its just iterating over all. But usually you don't need this when using hashtables.

Truly, I can't say it better.

[blueznl]

Doing a new lookup will very likely be faster. Because to get to a certain item number in the hash table you have to loop through all elements from the start every time, unless some cache mecanism was used, and even then you'd have to look up the position in the cache instead of looking up the actual value, so it would be a waste.

I was musing a little over this, but it actually would surprise me if the devs would have chosen to walk through the whole list.

Think about SelectElement() with a linked list. Let's assume the list is 1000 items long. Each section of the list has a fixed length, so to go to element number 500 you would'n have to go to 1, then 2 etcetera, you could just jump to number 500*field length.

As long as you do not change the order of the list, such a pointer stays perfectly valid.

Now, searching a hash table is probalby rocket lightning fast, but it is probably just like the regular list a whole bunch of fields of all the same length. (Hey, only the devs can tell us.) So, jumping to a specific field by its field number is ALWAYS going to be faster than doing a hash lookup.

Although, admittedly, perhaps not by much

[Trond]

blueznl, have you not yet learned the fundamental structure of programming? It goes like this:
1. Ask question of forum.
2. Trond chimes in.
3. Big flamewar
4. The answer was in Trond's first post?
(Just a joke)

I answered as though I thought you knew something you don't, so my answers probably didn't help you. But this answer is practically guaranteed to make you understand. I'll try to explain everything.

First things first: An array is big chunk of continous memory that is accessed in the form of uniformly sized blocks (defined by the arrays data type). To get the pointer to an item we do PtrToStartOfMemory+Index*SizeOfBlocksInBytes.

Second things second: A linked list is uniformly sized blocks separately allocated at random locations in memory. At the start of each block is a pointer to the previous and a pointer to the next block. The "list pointer" is a pointer to the first block.

Let's visualize it:

The blue, continous memory is an array.
The pink is a linked list. The "list pointer" is 131, this is the first element of the list.

If you want to go to a certain element of an array, you just compute the address. But if you want to go to list element 3, then you first have to go to the element at 131 (because that's the only place you've got a pointer to), follow the pointer to 173, and then follow the pointer to 102.
The only feasible optimization is to keep track of a current element pointer and which number this element has, and travel relative to that element. So if the current element was 5 and you wanted to get to element 3, you'd go two steps back instead of three forward, one step saved.

I hope you understand the nature of linked lists by now, and why they don't allow "random access" (access any element with the same ease), if not read a book about it. I can particularly recommend this one: http://www.amazon.com/Structures-Proble ... 080531217X

Last things last: A hash table is an array of linked lists. You can jump directly to a certain element in the array, but you do not know which position this is in the hash table, because you don't know how many elements there are in the linked lists associated with earlier array positions.

Code: Select all

Array:	Associated linked list element count:
1	2
2	0
3	0
4	8
5	1
6	4
7	3

When you go to array position 5, but it's useless if you want to go to a certain position in the hash table. Because in this case, the element at position 5 is (2+0+0+8) = element 10, but if you add two elements at array position 3, then the element at position 5 will be 13. So you have to loop through all linked lists and count the elements until you get to the position you want to go.

I hope you get it now.