It is currently Sat May 25, 2013 3:00 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 13 posts ] 
Author Message
 Post subject: How to use Map
PostPosted: Fri Aug 14, 2009 1:56 am 
Offline
Addict
Addict
User avatar

Joined: Mon May 26, 2003 3:07 pm
Posts: 1146
Location: Nantes
PB 4.40b1

Code:
NewMap PB_Versions.s()
PB_Versions("430")="PB 4.30"
PB_Versions("440")="PB 4.40b1"
Debug MapSize(PB_Versions())

FindMapElement(PB_Versions(),"430")
Debug "Result Found = "+PB_Versions()

Procedure TestMap(Map ThisMap.s())
   
   ResetMap(ThisMap())
   While NextMapElement(ThisMap())
      Debug MapKey(ThisMap())+ " => "+ThisMap()
   Wend
   
   ForEach ThisMap()
      Debug MapKey(ThisMap())+ " => "+ThisMap()
   Next
   
EndProcedure

TestMap(PB_Versions())
ClearMap(PB_Versions())

_________________
Image
XP x86 4.40b3 » ToolbarPlus | SplitterGadgetPlus | Requester Position | CustomTooltip


Top
 Profile  
 
 Post subject:
PostPosted: Fri Aug 28, 2009 7:05 pm 
Offline
Enthusiast
Enthusiast

Joined: Tue Apr 04, 2006 6:27 am
Posts: 308
Can someone please help me understand this?

Why would someone use maps instead of linklists and arrays? What are the advantages?


Top
 Profile  
 
 Post subject:
PostPosted: Fri Aug 28, 2009 7:11 pm 
Offline
PureBasic Expert
PureBasic Expert
User avatar

Joined: Sat May 17, 2003 11:31 am
Posts: 5808
http://www.xs4all.nl/~bluez/datatalk/pu ... _hash_maps

_________________
( PB5.11 Win7 x64 Dell XPS710 Raid 0 VelociRaptor Intel Q6600 nForce 5 NVidia GTS450 )
( You have two options: psychotherapy, or the PureBasic Survival Guide... )


Top
 Profile  
 
 Post subject:
PostPosted: Fri Aug 28, 2009 8:59 pm 
Offline
Always Here
Always Here
User avatar

Joined: Mon Sep 22, 2003 6:45 pm
Posts: 7304
Location: Norway
X wrote:
Can someone please help me understand this?

Why would someone use maps instead of linklists and arrays? What are the advantages?
Linked lists allows quick insertion but slow search.
Arrays allow quick search (provided they are sorted) but slow insertion (also provided they are sorted).

A hash list (map) allows both quick insertion and search (although not quite as fast as list insertion or sorted array search).

_________________
Woa, I set up a web server.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 29, 2009 12:51 am 
Offline
PureBasic Bullfrog
PureBasic Bullfrog
User avatar

Joined: Wed Jul 06, 2005 5:42 am
Posts: 6465
Quote:
although not quite as fast as list insertion or sorted array search

I agree with you on the list insertion, but I can't on the sorted array search. A hashmap employs a large array, much larger than the total number of expected elements, and chooses a slot in the array for a prospective element by computing a hash on the element's contents. So retrieval is as fast as ArrayName(Hash(<searchedvalue>)). This is about as fast as a search can get and speed doesn't degrade as the number of elements rises. Sorted array searches, on the other hand, require a binary search. If you have one million elements, up to 20 read/compares will be necessary to retrieve the searched element. As the number of elements rises, search times get slower.

_________________
Veni, vidi, vici.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 29, 2009 9:45 am 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 2488
Location: New Zealand
netmaestro wrote:
. So retrieval is as fast as ArrayName(Hash(<searchedvalue>)). This is about as fast as a search can get and speed doesn't degrade as the number of elements rises. Sorted array searches


That's not quite accurate, hash tables mostly have an O(1) look up but a loaded table or poorly hashed table will eventually degrade toward an O(N) linear search time in the absolute worst case.

In some circumstances a binary search of a sorted array or binary tree will out perform a hashtable, this in mostly dependent upon the size of the table, how loaded the table is and the hidden cost of calculating the hash. So for 10,000 elements a binary search is often faster but compared to 1,000,000 elements there's no comparison.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Aug 29, 2009 11:39 am 
Offline
PureBasic Expert
PureBasic Expert
User avatar

Joined: Wed Oct 29, 2003 4:35 pm
Posts: 9870
Location: Beyond the pale...
Yes a hash table need not utilise a large array at all (though most will!), but what it does need to do is employ some mechanism for handling 'collisions' - those instances whereby two or more elements generate the same hash. In PB's map case, a linear search is employed through those elements which generated the hash in question. In the case of my own library, for example, a binary search is employed etc. though at the cost of having to use more memory. All swings and roundabouts! :)

A hash table is usually an excellent solution in situations where data is being indexed on a text based key etc.

_________________
I may look like a mule, but I'm not a complete ass.

eScript
Arctic Reports
nxSoftware


Top
 Profile  
 
 Post subject:
PostPosted: Sun Aug 30, 2009 10:22 am 
Offline
PureBasic Team
PureBasic Team
User avatar

Joined: Fri Apr 25, 2003 6:14 pm
Posts: 912
Location: Germany (Saxony, Deutscheinsiedel)
Is it possible to sort a NewMap / hasmap?

If not, is this by design (= standard) or is it "just" missing commands in PB?

I ask this, because I can imagine to use the new HashMaps instead of linked lists, but I need the possibility to sort it by its structured elements....

Thanks!

_________________
Bye,
...André
(PureBasicTeam::Docs & Support - PureArea.net | Order:: PureBasic | PureVisionXP)


Top
 Profile  
 
 Post subject:
PostPosted: Sun Aug 30, 2009 10:48 am 
Offline
Administrator
Administrator

Joined: Fri May 17, 2002 4:39 pm
Posts: 8876
Location: France
Yes, it is by design, you can't sort an hashmap (at least not the one used by PureBasic). For temporary sort, if time is not critical, you can create a list from the hashmap and then sort it.


Top
 Profile  
 
 Post subject:
PostPosted: Sun Aug 30, 2009 10:49 am 
Offline
PureBasic Expert
PureBasic Expert
User avatar

Joined: Wed Oct 29, 2003 4:35 pm
Posts: 9870
Location: Beyond the pale...
I would say that physically sorting a hash map is out of the question because the hash really defines the ordering of the elements. Start moving elements around and the hash will no longer allow you to look up individual elements.

The internal ordering of the elements will usually bear no relation to the order that you actually added the elements etc.

If you need a separate ordering then you should probably keep a separate list of the keys and order them or keep a list of pointers etc.

**EDIT : too slow! :)

_________________
I may look like a mule, but I'm not a complete ass.

eScript
Arctic Reports
nxSoftware


Top
 Profile  
 
 Post subject:
PostPosted: Sun Aug 30, 2009 9:53 pm 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 2488
Location: New Zealand
I haven't had time to look at the new map functions yet.

If it returns the key on insertion then that would make it easy enough to maintain a sorted list.

keyIndex = additem(MyMap(),item)

Though for more flexibility if you could supply your own hash function in a callback that could really help

size = CreateMap(@cbHashFunc(),number of items)

I think the addition of hash tables is a great feature though you generally need the ability to specify the hash function and table size to get any efficiency out of them.


Top
 Profile  
 
 Post subject:
PostPosted: Mon Aug 31, 2009 10:26 am 
Offline
Always Here
Always Here
User avatar

Joined: Mon Sep 22, 2003 6:45 pm
Posts: 7304
Location: Norway
It is possible to merge a hash map and a linked list (not PB native) by making sure that the structured variable that you place in the hash map has a linked list header (*prev and *next pointers). You must manage these pointers manually. But that way, you can look up values either in order (by the list) or by key (with the hash map) without storing the values twice.

_________________
Woa, I set up a web server.


Top
 Profile  
 
 Post subject:
PostPosted: Mon Aug 31, 2009 11:59 am 
Offline
Always Here
Always Here
User avatar

Joined: Mon Sep 22, 2003 6:45 pm
Posts: 7304
Location: Norway
idle and netmaestro, I posted an answer to your posts in a new topic: http://www.purebasic.fr/english/viewtop ... 990#297990

_________________
Woa, I set up a web server.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye