Sort a map by keys

[Lebostein]

How I loop over a map with sorted keys?

My solution is at the moment:

1. create an empty String List
2. loop over the Map and collect the keys in this String List
3. sort the String List
4. loop over the sorted String List and search for the current key in the Map to get the value
5. delete the String List

other solution possible?

In Python I would write the simple:

Code: Select all

for key, value in sorted(mymap.items()):
    print value

[infratec]

Hi, hi,

if you name your procedure sorted() than you have the same as in Python

Maybe it is a bit faster when you store also the address of each map element in the list.
Then you don't need to 'find' the element. But this depends on the rest of your code.

Bernd

[mk-soft]

Perhaps over the help list...

Code: Select all

Structure udtData
  iVal.i
  sVal.s
EndStructure

Macro SortedMap(HelpList, TheMap)
  MapSize(TheMap)
  ClearList(HelpList)
  ForEach TheMap
    AddElement(HelpList)
    HelpList = MapKey(TheMap)
  Next
  SortList(HelpList, #PB_Sort_Ascending | #PB_Sort_NoCase)
EndMacro

NewMap MyMap.udtData()
MyMap("US")\iVal = 100
MyMap("GE")\iVal = 200
MyMap("EN")\iVal = 300

; Help Key List
NewList Keys.s()

count = SortedMap(Keys(), MyMap())
ForEach Keys()
  Debug MyMap(Keys())\iVal
Next

[Fig]

Each time you add an element to your map you add an element to your list.
You will not have to loop in your entire map to get all keys that way.

I bet python's maps are slower than pb's ones....

[Mistrel]

PureBasic's implementation of maps is unsorted as it is a hash map unlike other implementations where insertion is sorted using a tree structure such as Java's TreeMap or C++'s Map.

The only way to sort it would be to copy all of the keys to a list and sort it there.

[uwekel]

I bet python's maps are slower than pb's ones....

No, Python is more than 10x faster. Here is the code i have used (includes sorting):

Purebasic without debugger need around 2500ms:

Code: Select all

e = ElapsedMilliseconds()
NewMap Items()
For i = 1 To 100000
  Items(Str(i)) = i
Next
NewList SortedItems.s()
ForEach Items()
  AddElement(SortedItems())
  SortedItems() = MapKey(Items())
Next
SortList(SortedItems(), #PB_Sort_Ascending)
ForEach SortedItems()
  i = Items(SortedItems())
Next
MessageRequester("", Str(ElapsedMilliseconds() - e))

Python takes 200ms:

Code: Select all

from time import time

t = time()
items = {}
for i in range(100000):
    items[str(i)] = i
for i in sorted(items):
    pass
print(time() - t)

Regards
Uwe

[infratec]

Hm....

have you disabled the debugger?
Because on my slow PC the PB code takes at max. 800ms

But if I include the list operation inside the first loop it takes around 1200ms.

Bernd

[Demivec]

Fig wrote:
I bet python's maps are slower than pb's ones....


No, Python is more than 10x faster. Here is the code i have used (includes sorting):

You've made an unequal example in your comparison code.

In PureBasic you use this code:

Code: Select all

ForEach SortedItems()
  i = Items(SortedItems())
Next

While in Python you use:

Code: Select all

for i in sorted(items):
    pass

The loops contents differ in function. Python's loop executes nothing ('pass'), while PureBasic's loop executes an assignment referencing both an array and a list.

PureBasic's time would at least be halved if the last loop was the same as Python and contained nothing.

I'm not sure where that places the two contestants but it is at least more accurate.

[uwekel]

have you disabled the debugger?
Because on my slow PC the PB code takes at max. 800ms
But if I include the list operation inside the first loop it takes around 1200ms.

Yes, the debugger was disabled. I dont know why, but today morning after a fresh boot the purebasic time was 1200ms, and the python needed 130ms.

The loops contents differ in function. Python's loop executes nothing ('pass')

This is wrong. The assignment has already been done in the loop. You can simple replace the pass by a "j = i" or so, but the time keeps the same.

Btw, my CPU is a Intel® Core™ i5-6200U CPU @ 2.30GHz × 4 and i have 8GB memory.

Regards Uwe

[Fig]

uwekel > I bet (one more time) that you forgot to change the number of slot assign to pb's map.
That's one other reason it's so slow.
How many slots does Python's map have by default ?
In Pb you stack 100 000 elements on 512 slots only...
First point.
And second point, of course, Pb's map are not already sorted, i bet pb's map vs python's map without sorting, of course. (Python probably use Judy's hashtable)

NewMap name.<type>([Slots])
The optional 'Slots' parameter defines how much slots the map will have have to store its elements. The more slots is has, the faster it will be to access an element, but the more memory it will use. It's a tradeoff depending of how many elements the map will ultimately contains and how fast the random access should be. The default value is 512. This parameter has no impact about the number of elements a map can contain

[idle]

The difference is no doubt the structure used, take a look at a Trie

[Lord]

uwekel > I bet (one more time) that you forgot to change the number of slot assign to pb's map.
...

I made a short test:

Code: Select all

slots		time [ms]
default		715
   1000		185
  10000		 85
 100000		 63
1000000		 61

Tested with Intel® Core™ i5-760 CPU @ 2.80GHz, 16GB memory

[said]

Hi,

I have developed a simple sorted 'map' here: http://www.purebasic.fr/english/viewtop ... 12&t=67529

Would love to see benchmarks against python (i dont know python it is on my learning schedule though ) i guess this implementation should be faster in similar cases to the above (simple non-typed maps) which probably represents over 90% of map usage (at least for me)

Said

[Mistrel]

The most performance solution would be to use some form of self-balancing tree ruch as a Red-Black or AVL tree as the map will be correctly sorted upon and insertion. But there would be no point in pursuing this unless you actually needed it. Copying to a list and sorting it there will most likely be fast enough; depending on the side of the list.