It is currently Wed Jun 19, 2019 1:05 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: Dynamic growth of Map
PostPosted: Fri Jun 15, 2018 2:18 pm 
Offline
Always Here
Always Here

Joined: Mon Sep 22, 2003 6:45 pm
Posts: 7439
Location: Norway
Dynamic map growth
-----------------------------

To have to choose the number of slots beforehand is a big limitation with maps. So I suggest an improvement, which will allow seamless growth of maps. Instead of allowing just a single map, PB maps should create more and bigger maps behind the scenes, when the current map is full, according to the following algorithm:

NewMap creates a list of "blocks", where each block is just a hashmap. Initially, this list has exactly one element with the number of slots specified in the creation (or the default number of slots).

Insertion:
Code:
Get the first block in the list.
If the block is less than 75% (not sure of optimal fullness) full
    insert the item as normal.
else
    add a new block as the first element of the list
    this new block should be bigger than the previous, according to the following growth curve:
    128 -> 256 -> 512 -> 1024 -> 2048 -> 4096 -> ... (the powers of two), until a point where the new blocks no longer grows so fast (it makes no sense to allocate a 2 GB block, if your current is 1 GB, a limit of 1 000 000 or something should be enforced.
    Insert the item in this new block.


Lookup:
Code:
Starting before the start of the list:
repeat
    Get the next block in the list
    check if the key can be located, if yes, return it
    if no:
until past_end_of_list
return: element not found


Top
 Profile  
Reply with quote  
 Post subject: Re: Dynamic growth of Map
PostPosted: Fri Jun 15, 2018 4:48 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 300
Location: Côtes d'Azur, France
Image

Clustered hastable ?

_________________
There are 2 methods to program bugless.
But only the third works fine.

Win10, Pb x86 5.70 LTS


Top
 Profile  
Reply with quote  
 Post subject: Re: Dynamic growth of Map
PostPosted: Fri Jun 15, 2018 10:49 pm 
Offline
Addict
Addict
User avatar

Joined: Sat Jun 30, 2007 8:04 pm
Posts: 3237
What you're asking for is a complete replacement of PureBasic's map library to fit a niche requirement. There is no one solution and there are already other issues such as keys being limited to strings.

I think the current implementation is good for most use cases. If you want something to solve a specific problem then you can always write one yourself. Since we don't have a form of generics, PureBasic native containers are pretty limiting anyways.

What problem are you encountering that you need to optimize PureBasic's map?

_________________
Image


Top
 Profile  
Reply with quote  
 Post subject: Re: Dynamic growth of Map
PostPosted: Sat Jun 16, 2018 9:42 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Jun 22, 2003 7:43 pm
Posts: 371
Location: Germany, Saarbrücken
When you change the number of blocks you normally have to rehash all the data in the map again because it can move to a different position as before.

_________________
Electronics, Crazy & Interesting Stuff, all that with text, image and sound? Click here!

The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.


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

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 5 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