Clojure looks quite intriguing to me, I wish day had at least 48 hours so that I can go over all the things I want:)
Have you considered quick and dirty port of the Finger Trees using ClojureScript? Actually I've noticed quite a lot JDK dependencies in that code, so not sure.. >From a quick scan of a relevant paper on Finger Trees (http:// www.soi.city.ac.uk/~ross/papers/FingerTree.pdf): "As search trees, finger trees seem to be 3 to 5 times slower than the best balanced binary tree implementations. Nevertheless, they may be competitive when a wider set of operations is required." That said, they look very interesting, considering all the reasons you stated. Also, the paper is from 2006, I'm sure optimizations are constantly being added. Pls let me know when you port it over so I can add you to the nodejsdb.com page. Also, given the current V8 object limits (I've seen it choke on ~40m objs), do you consider this as a limitation for you implementation? Are you considering to make it a native module later perhaps? Or is this something that could be implemented on top of the ordered map API I'm pondering here? On Feb 22, 10:14 pm, Dean Landolt <[email protected]> wrote: > On Wed, Feb 22, 2012 at 2:37 PM, Juraj Vitko <[email protected]> wrote: > > The problem with tree (ordered) maps is that they usually take more > > space and are slower than hash maps. So that's why I proposed a > > separate Map and OrderedMap. > > > Plus, often times one needs to store a sequential structure, e.g. to > > implement a Queue, or Stack, etc. It's possible to implement a list on > > top of ordered map though, but one has to generate unique keys. > > > Doubly linked list takes up too much memory, and Array is terrible for > > insertion, but C++ STL's Deque solves this by providing a list > > consisting of multiple Array chunks. > > Yes, deques are great, but you'll probably also want fast indexed access. > Then you'll find you may need (sublinear) concat, slice, splice, reverse, > etc. Finger trees are a general purpose data structure that let you compose > collections that do all of things quite easily. Oh, and it has this other > advantage of being persistent (read: immutable), so you also get some other > neat advantages (everything's a snapshot -- it can't mutate on you even if > you dip into the event loop). Using structural sharing it's able to offer > all of the above handy operations while returning you what appears to be a > completely new list, and very quickly. > > And this immutability has another neat benefit: you could pass these > immutable objects around between "worker" threads within the same process > freely. It's a shame node-core had to punt on threaded workers but that > doesn't mean this can't be done from a module. It's possible libuv may > never be threadsafe, but no bother -- being able to safely share certain > types of objects between threads means the worker environment could be > limited to pure compute. Thus, you could theoretically build a kickass > fibanocci benchmark, and all would finally be right with the world. > > > HOWEVER - the paper that I noticed today (http://goo.gl/71aFc) - seems > > to offer a cool ordered Map structure that also happens to be faster > > than any Hash Map currently in use. It also does this in SMP way, so > > multiple Node instances in local Node Cluster could even use such DB > > together. Let's hope they don't slap a patent on it. > > This looks really cool. Although it's important to remember that there are > a number of ways to accomplish this. I haven't looked closely at this paper > yet but I bet clojure's shallow tries have similar qualities and ought to > port to javascript pretty cleanly. > > But yeah, there's a ton of interesting data structure goodness out there > the javascript community needs to start stealing :) > > > Re: the CouchDB - I'd imagine this is already a higher level > > functionality - something that people should be able to implement and > > evolve on top of the basic primitive operations, > > like .put(k,v), .get(k), .range(k1, k2). > > Much of what couch does is commodity, yes, but there is something > particularly unique about their b+tree implementation. It will cache > calculated reduction values in its interior nodes so they don't have to be > run over and over. This can be really handy but it's not without its > problems. Interestingly, fingertrees let you do the same thing in a more > flexible yet correct manner (composable "meters" that measure and persist > any data you want about children..."monoids" FTW). This feature is what > allows you to do all the things I mentioned above. > > > I'm looking for a good paper or book pondering complex schema design > > on key/value stores, but haven't had much time to do a proper googling > > for it yet. > > If you find anything I'd be really interested in hearing about it. -- Job Board: http://jobs.nodejs.org/ Posting guidelines: https://github.com/joyent/node/wiki/Mailing-List-Posting-Guidelines You received this message because you are subscribed to the Google Groups "nodejs" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/nodejs?hl=en?hl=en
