On Sat, Feb 19, 2011 at 9:14 AM, Sebastian Fischer <[email protected]>wrote:
> On Sat, Feb 19, 2011 at 2:05 AM, John Lato <[email protected]> wrote: > >> On Fri, Feb 18, 2011 at 1:14 AM, Sebastian Fischer <[email protected]>wrote: >> >>> Maybe one of the simpler structures presented there (like random access >>> lists) provides faster indexing. >>> >> >> I believe the difficulty with random access lists is in dropping >> references to old data. I don't see how to do so efficiently. >> > > Instead of shifting all elements through the buffer you could store an > index to the oldest element and increase it (modulo size) when overwriting. > Then the only operations you need internally are reading and writing at > arbitrary positions, for which IntMap also seems like a good candidate. You > could also try the new hash maps: > http://blog.johantibell.com/2011/02/new-faster-containers-library.htmlalthough > I don't see a reason why they should be faster than IntMaps. > This was the first thing I tried, with vectors. It seems that writing to arbitrary positions is not necessarily fast though. With vectors the entire vector needs to be copied. With IntMaps, writing is O(min(n,W)), and ends up being significantly slower than cons'ing onto a finger tree. Lookups are also much slower, somewhat to my surprise. I think random access lists would also require a lot of data copying with this approach. I've been following Johan's announcements as well, but at least for now they aren't quite as performant as IntMaps (according to his tests). One thing which might be better is a set of cascaded real-time queues, for which several implementations exist. The implementation gets a little complicated though, and I expect it would be equivalent (or worse than) using a finger tree directly. John
_______________________________________________ haskell-art mailing list [email protected] http://lists.lurk.org/mailman/listinfo/haskell-art
