Page 1 of 1
Sort a map by keys
Posted: Fri Jan 20, 2017 4:19 pm
by 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
Re: Sort a map by keys
Posted: Fri Jan 20, 2017 5:25 pm
by 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
Re: Sort a map by keys
Posted: Fri Jan 20, 2017 5:42 pm
by 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
Re: Sort a map by keys
Posted: Fri Jan 20, 2017 5:47 pm
by 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....
Re: Sort a map by keys
Posted: Fri Jan 20, 2017 9:01 pm
by 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.
Re: Sort a map by keys
Posted: Fri Jan 20, 2017 9:27 pm
by uwekel
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):
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
Re: Sort a map by keys
Posted: Fri Jan 20, 2017 10:54 pm
by 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
Re: Sort a map by keys
Posted: Sat Jan 21, 2017 12:08 am
by Demivec
uwekel wrote: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:
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.
Re: Sort a map by keys
Posted: Sat Jan 21, 2017 8:06 am
by uwekel
infratec wrote: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.
Demivec wrote: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
Re: Sort a map by keys
Posted: Sat Jan 21, 2017 8:52 am
by 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)
Pb's Helpfile wrote:
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
Re: Sort a map by keys
Posted: Sat Jan 21, 2017 9:09 am
by idle
The difference is no doubt the structure used, take a look at a Trie
Re: Sort a map by keys
Posted: Sat Jan 21, 2017 11:31 am
by Lord
Fig wrote: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
Re: Sort a map by keys
Posted: Sat Jan 21, 2017 3:11 pm
by 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
Re: Sort a map by keys
Posted: Sat Jan 21, 2017 5:21 pm
by 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.