Hacker News Reader

Comment by juliusmusseau | Hacker News Reader

I'd like to see the performance of growing the list (a common scenario):

    ArrayList list = new ArrayList();
    for (int i = 0; i < N; i++) {
      list.add(i);
    }

(Forgive me, Java is my mother tongue).

View on HN

I believe this case is very badly handled in this data structure implementation. It seems to be saying that you want to occasionally manually recreate the DS as it grows bigger, as the deqs won't automatically resize. So you'll just have linear behavior in that case, with extra constants because the deqs are useless logic.

I suspect an amortized data structure could automatically and internally do this rebalancing operation, but I'd have to work out the scheme and the analysis. At a guess, something like normal dynamic arrays do, where you multiply the max size by a constant when it fills up, would give you decent amortized bounds.

Correct. I need to add automatic restructuring. Currently structure sensitive and benefits a lot from using reserve() method

In C++ the std::vector type handles this by doubling the capacity when full. I think this approach also works for this data structure. When the capacity has been reached simply double the capacity and rebuild from scratch. Perhaps quadruple because then each double-ended queue would double in size, avoiding that pesky sqrt(2). The amortized time should be the same.

> In C++ the std::vector type handles this by doubling the capacity when full.

Of course, the growth factor is implementation-dependent and I believe some compilers use smaller growth factors to improve performance.

Th optimal growth factor is the golden ratio 1+sqrt(5) [1.618], but 2 is much faster to calculate.

Is calculating the new size really the bottleneck here?

Here’s an old article about the performance characteristics of Deques.

https://www.codeproject.com/Articles/5425/An-In-Depth-Study-...

> Forgive me, Java is my mother tongue

I hope your mother taught you the value of using generics ;)

Reply on news.ycombinator.com