From: Brian H. <bh...@sp...> - 2004-05-28 18:02:24
|
I've implemented an extended/improved implementation of the Map standard library, which is (with one caveat, see below) drop-in replaceable for the standard library, and I'm wondering if people are interested. I'm not done commenting the code, and I haven't tested it at all (it compiles, though- which is a stronger statement in Ocaml than it is in other languages), which is why it's a request for comments and not an actual submission. The original version of this message had the code attached, but the list doesn't seem to like messages that large. The differences are: - I've moved OrderedType into it's own library, Type, and renamed it to be just Ordered. So it's Type.Ordered now, not Map.OrderedType. We have the same ordered type signature in Map and Set. Rather than duplicating this code, we should just have it in a common module. This is a cleanliness issue, not a performance issue. But this is the one user-visible change to the library. - The tree is now a red-black tree, not a height-balanced tree. The advantage here is that this form uses one less word per entry than height balanced does. The disadvantage is that it's a lot more code. Between this and the extra functionality, the map module now weighs in at about 48K on x86-32 Redhat 9.0 Ocaml 3.07. - Lots of new functions has been added. Some major areas of expansion are: - conversions to and from lists. This is especially usefull for loading up maps with constant values. - conversions to and from enums, to make it compatible with the rest of the library - fold_left and fold_right with the same semantics/calling structure as List.fold_left and List.fold_right - iters and folds on 2 maps- this is what got me started on the project. I want to do sparse vectors as (int, float) maps- and a lot of the BLAS functions want to do iters or folds on 2 maps. Which is why, although they are basically implemented with enums, I've included them. - a compare function. Unfortunately, this doesn't mean that the module, as it is written at the moment, qualifies for Type.Ordered. But it does make it easier to get there. If the response is positive, I'll finish documenting, do some testing, and submit it. I'm also considering the following other small projects: extSet: Set with similiar extensions and based on RB trees. funcarray: a functional array module. This is a tree-based structure that looks like an array- elements have positions 0 .. N-1, are accessed by position (this is different than sets), and are always densely packed (this is different than a map with ints as keys). Accessing any element, adding an element, overwritting an element, or removing an element are O(log N) operations and strictly applicative. Removing element i decrements the locations of all nodes i..N-1. Inserting an element at location i moves everything in i..N-1 to i+1..N, still in O(log N). quadtree- a 2D array of objects based on a quad-tree structure. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |
From: Nicolas C. <war...@fr...> - 2004-05-28 18:45:59
|
> I've implemented an extended/improved implementation of the Map standard > library, which is (with one caveat, see below) drop-in replaceable for the > standard library, and I'm wondering if people are interested. I'm not > done commenting the code, and I haven't tested it at all (it compiles, > though- which is a stronger statement in Ocaml than it is in other > languages), which is why it's a request for comments and not an actual > submission. The original version of this message had the code attached, > but the list doesn't seem to like messages that large. I would prefer your enhancements to be put into the PMap module. I personaly think that basic data structures such as Map and Set should not be functors, so I'm not sure providing more support for Map and Set is a good thing. Regards, Nicolas Cannasse |
From: Brian H. <bh...@sp...> - 2004-05-29 15:06:23
|
On Fri, 28 May 2004, Nicolas Cannasse wrote: > > I've implemented an extended/improved implementation of the Map standard > > library, which is (with one caveat, see below) drop-in replaceable for the > > standard library, and I'm wondering if people are interested. I'm not > > done commenting the code, and I haven't tested it at all (it compiles, > > though- which is a stronger statement in Ocaml than it is in other > > languages), which is why it's a request for comments and not an actual > > submission. The original version of this message had the code attached, > > but the list doesn't seem to like messages that large. > > I would prefer your enhancements to be put into the PMap module. > I personaly think that basic data structures such as Map and Set should not > be functors, so I'm not sure providing more support for Map and Set is a > good thing. > I disagree with this. We could argue wether modules are good or not til the cows come home, but in this case there is an operational reason to use modules. The -2 functions all implicitly assume that they're working with two data structures ordered the same way, allowing me to do the operations in O(N) and not O(N log N). -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian |