3 ms·

I think the "resizes" occurring in this scenario would be to same-size buffers, meaning that the very same buffer could actually be reused. Provided that's in f

I think the "resizes" occurring in this scenario would be to same-size buffers, meaning that the very same buffer could actually be reused. Provided that's in fact what is happening, then yes, this scenario would cause infinite resizes, all of which would be avoided by a ring buffer. But those resizes would still happen rarely enough to meet the amortised complexity claim, namely, 1 resize (copying of n elements) per n elements inserted. (I'm not at all certain that this is how it actually does work -- the README is light on details. But this is how it might work.)

kragen 2y ago
You don't want to always resize to same-size buffers in that situation; consider a size-1024 buffer containing 1023 elements and a free space on the right. Pushing another item on the left can be done in the very same buffer, but requires copying all 1023 items one space to the right. If you then pop another item off the right end you are back to the starting state, so by repeating the process you need 511.5 element copies (in general, O(N) copies) per push or pop. There are obvious ways to resolve problems like this, but there are tradeoffs among them, and I would like to know which way the author chose and what the resulting complexity is without having to analyze (and debug) 270 lines of C++. Hmm, there's a PDF at https://github.com/attilatorda/Shift-To-Middle_Array/blob/main/ShiftToMiddleArray.pdf https://github.com/attilatorda/Shift-To-Middle_Array/blob/ma...... but it also doesn't explain things like this. It makes assertions about big-O performance, but doesn't explain the algorithm in enough detail to know whether they are correct.
- senderista 2y ago
  I implemented the "2-level rotated array" structure a few years ago, which isn't designed to be used as a deque, but is at least less pathological than this (O(1) push_back/pop_back, O(sqrt(n) push_front/pop_front/insert/delete). https://github.com/senderista/rotated-vec https://github.com/senderista/rotated-vec
  - kragen 2y ago
    Oh, fantastic!

kragen 2y ago

You don't want to always resize to same-size buffers in that situation; consider a size-1024 buffer containing 1023 elements and a free space on the right. Pushing another item on the left can be done in the very same buffer, but requires copying all 1023 items one space to the right. If you then pop another item off the right end you are back to the starting state, so by repeating the process you need 511.5 element copies (in general, O(N) copies) per push or pop. There are obvious ways to resolve problems like this, but there are tradeoffs among them, and I would like to know which way the author chose and what the resulting complexity is without having to analyze (and debug) 270 lines of C++. Hmm, there's a PDF at https://github.com/attilatorda/Shift-To-Middle_Array/blob/main/ShiftToMiddleArray.pdf https://github.com/attilatorda/Shift-To-Middle_Array/blob/ma...... but it also doesn't explain things like this. It makes assertions about big-O performance, but doesn't explain the algorithm in enough detail to know whether they are correct.

senderista 2y ago
I implemented the "2-level rotated array" structure a few years ago, which isn't designed to be used as a deque, but is at least less pathological than this (O(1) push_back/pop_back, O(sqrt(n) push_front/pop_front/insert/delete). https://github.com/senderista/rotated-vec https://github.com/senderista/rotated-vec
- kragen 2y ago
  Oh, fantastic!