|
|
| Author |
Message |
|
| rvirding |
 Posted: Sun Jun 15, 2008 10:49 am |
 |
|
|
User
Joined: 30 Aug 2006
Posts: 452
Location: Stockholm, Sweden
|
I have just released rbdict, a dictionary as a Red-Black tree.
This is a dict compatible dictionary based on Red-Black trees. It supports the full dict interface and is drop-in compatible with both dict and orddict. Documentation is included.
There is also an alternate implementation, in rbdict1, which is a little slower but is included as another example of working on red-black trees. These are tricky little bastards so it is helpful to see other implementations.
It is down-loadable from trapext.org:
http://forum.trapexit.org/viewtopic.php?p=43948#43948
It would be good to see how it fares under the same unit tests as dict, and orddict. Hint, hint!
Post received from mailinglist |
|
|
| Back to top |
   
|
| Guest |
| Posted: Mon Jun 16, 2008 4:14 pm |
|
|
|
Guest
|
I ran the following code thru fprof using N=1000 for Mod=dict and Mod=rbdict. The basic results were that rbdict was ~10-20ms slower than dict for both store and fetch.
store(Mod, N) ->
|
|
|
| Back to top |
|
| rvirding |
| Posted: Mon Jun 16, 2008 7:46 pm |
|
|
|
User
Joined: 30 Aug 2006
Posts: 452
Location: Stockholm, Sweden
|
2008/6/16 Jacob Perkins <japerk@gmail.com (japerk@gmail.com)>:
Quote: I ran the following code thru fprof using N=1000 for Mod=dict and Mod=rbdict. The basic results were that rbdict was ~10-20ms slower than dict for both store and fetch.
store(Mod, N) ->
|
|
|
| Back to top |
|
| rvirding |
| Posted: Mon Jun 16, 2008 8:54 pm |
|
|
|
User
Joined: 30 Aug 2006
Posts: 452
Location: Stockholm, Sweden
|
2008/6/16 Robert Virding <rvirding@gmail.com (rvirding@gmail.com)>:
Quote:
This is expected, rb-trees are O(n lg n) but dict is based on a hashing algorithm as is almost O(1).
I made a mistake here as Fuad pointed out to me, rb-trees are of course O(lg n).
Robert
Post received from mailinglist |
|
|
| Back to top |
|
|
|
All times are GMT
|
|
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
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
