5 ms·
Correct me if I am wrong, but I think the insertion/deletion time complexity is incorrect. It should be O(N). If each DEQ is implemented using array instead of
by panda88888 7y ago
Correct me if I am wrong, but I think the insertion/deletion time complexity is incorrect. It should be O(N). If each DEQ is implemented using array instead of list, wouldn’t the insert/delete operation of IgushArray still take linear time? Since popping or pushing (pick one) of DEQ implementation with array still take linear time, that means, let’s say insertion is at position N/2, then N/2 ... N-1 elements still need to be moved to the right by one? Popping/pushing is only linear if the DEQ is implemented with linked list, but that would mean linear access time instead of constant.
Update: answer is to implement DEQ with circular buffer for O(1) pop/push.
- igushev 7y agoInsertion and deletion from DEQ indeed is linear, but in all of DEQs in the structure only one (!) needs insertion, the rest are just popping/pushing front/back.
- panda88888 7y agoMy question is that each move is a set of push/pop. DEQ based on fixed array has linear complexity for either push (left aligned) or pop (right aligned). One way to have constant push AND pop is to allow for the left and right element to not be aligned to the initial fixed array memory allocation. For example, for a full DEQ, in order to perform a push, I would have to: 1. Pop the last element 2. Move all element to the right by 1 3. Push the item into position 0 This would be a linear operation. Unless the address of the starting and ending element can change, I don’t think it’s possible to get both push and pop to less than linear time. Edit: I was wrong--key is circular buffer
- kadoban 7y agoYou've answered your own question implicitly. The address of the starting and ending element can change. You just define yourself where in the backing array the start/end are, and let them wrap around (use modular arithmetic for the indexes).
- panda88888 7y agoThanks! DEQ implementation with circular buffer. :) Edit: should have thought of that. Brain fart—-long day at work.
- kadoban 7y agoExactly! I really like this stuff, little clever ways to skip effort. Data structures and algos don't get enough love :)
- igushev 7y agoDEQ has floating starting index. When you push or pop, you just changing this index. The implementation in the repository also have custom implementation of DEQs which is even more optimized for this structure.
- flafla2 7y ago> the rest are just popping/pushing front/back. Sure, but this step would require a right shift for (in the worst case) every element in the structure. Suppose you have the following DEQ: [R0] -> [0, 1, 2] [R1] -> [3, 4, 5] [R2] -> [6, 7, 8] And you want to remove 4. From my understanding of your README, the structure will look like this after the operation: [R0] -> [0, 1, 2] [R1] -> [3, 5, 6] [R2] -> [7, 8, _] This was not and O(sqrt(n)) operation, because you had to move elements 5, 6, 7, and 8 (not just 5 as suggested by your figures). So in general you still need to move O(n) elements upon any insertion or deletion. EDIT: Just read some of the other comments and realized that this can be done with a circular buffer with a bit more memory than the subarrays themselves. Makes sense + clever! @OP, I really think you should clarify on this important implementation detail in your writeup.
- juliusmusseau 7y agoI think the data-structure is careful to make sure the main array is at most SQRT(N) and all linked queues also SQRT(N). It's a neat restructuring of the vector into a SQRT(N) * SQRT(N) arrangement.
- igushev 7y agoI also need to add automatic restructuring when it expands or shrinks significantly.
- kadoban 7y agoYou can implement push/pull on both ends of an array-back deq in O(1) time for all. Store the backing array (know the size as well) and then store two indexes, the front of the deq and the back of the deq. You update the front/back the obvious way on push/pop except you do modular arithmetic if it would take you out of bounds. You have a limited size of the deq of course, but here that's fine, it's actually constant size for all of them except the final possibly smaller one. So now, what work do you have to do on insert? For the destination deq, you need to do one pop, one copy-in and up to n^1/2 moves. For every deq after that, up to about n^1/2 of them, you need to do one pop and one push, each of which costs O(1).