On Tuesday, Aug 13, 2002, at 01:00 US/Pacific, Oleg wrote:
>
> Has anyone implemented a doubly-linked list with O(1) push_back, 
> push_front,
> back, front, length operations?
>
> Thanks
> Oleg
>
> P.S. BTW, one could have identical interfaces for a) resizable arrays, 
> b)
> doubly-linked lists and c) deques, the only difference being the 
> efficiency
> of various operations. It could be convenient for a programmer, 
> because final
> data representation can be chosen after the program has been profiled 
> and
> without changing much code. Has anyone tackled this problem?

I have recently been working on a fully-persistent, catenable deque 
that uses explicit recursive slowdown , á la Kaplan and Tarjan, to 
achieve what seems to me to be O(1) amortized cost for all the 
traditional operations.  I think my design may be substantially simpler 
than algorithms I've seen published to date, but I'm not sure.  I'm 
certain it isn't O(1) for all operations, but I can push and shift 
millions of objects into and out of a deque without any noticeable 
degradation in performance over the size of a deque.  In other words, 
it looks to me to be good enough for government work.

When I've put the code through some more paces, I will publish it.  
Give me a few more weeks.


--james

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners