search

jbapple / deques

Automatically exported from code.google.com/p/deques
0 stars 0 forks source link

No concatenation #1

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
You include what you call Tarjan-Mihaesau deques, but apparently without 
concatenation! Since I believe the primary point of their implementation (as 
well as earlier, related implementations by Kaplan and Tarjan, Okasaki, and 
Kaplan, Okasaki, and Tarjan) is to support O(1) concatenation, it seems silly 
to use such a complex structure without getting the benefit.

Original issue reported on code.google.com by david.fe...@gmail.com on 9 Sep 2012 at 1:13

GoogleCodeExporter commented 9 years ago 
If you read their short description 
(http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Notes%20on%20
Catenable%20Deques.doc), you will see that the deque without concatenation is 
much simpler.

The one without concatenation has some interesting properties:

1. As far as I know, it's the simplest tree-based worst-case purely functional 
deque. Being tree-like gives it certain structure that allows attaching 
monoid-like accumulators to internal nodes like is common with Hize-Patterson 
finger trees.

2. It allows O(lg min(i, n-i)) lookup of the ith element, when annotated with 
tree sizes.

3. It allows O(1) approximate split, in which a deque can be split into left 
and right parts that differ in size by no more than a constant ratio.

The T-M concatenable deque is very interesting, but I just haven't gotten to it 
yet. In the meantime, the one that isn't concatenable in O(1) time has some 
nice properties of its own.

Original comment by s...@jbapple.com on 9 Sep 2012 at 2:25