4 ms·
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
by juliusmusseau 7y ago
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).
- kadoban 7y agoI 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.
- igushev 7y agoCorrect. I need to add automatic restructuring. Currently structure sensitive and benefits a lot from using reserve() method
- michaelrpeskin 7y agoHere’s an old article about the performance characteristics of Deques. https://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container https://www.codeproject.com/Articles/5425/An-In-Depth-Study-...
- kccqzy 7y agoIn 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.
- saagarjha 7y ago> 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.
- saagarjha 7y ago> Forgive me, Java is my mother tongue I hope your mother taught you the value of using generics ;)