6 ms·
Most languages have a built in type for a dynamic array, but many of them lack a built-in queue. I have a favorite trick for a quick-and dirty queue in those l
by marvy 10y ago
Most languages have a built in type for a dynamic array, but many of them lack a built-in queue. I have a favorite trick for a quick-and dirty queue in those languages. You need an array (initially empty) and an integer (initially zero). To add to the queue, add to the array. To get the front of the queue, just do array[int]. And finally, to remove from the queue, simply increment the integer. The advantages of this approach are simplicity and speed: each operation takes amortized constant time. The obvious disadvantage is that it's potentially a major memory leak. For instance, if you try to do breadth-first search of a tree using this queue, your memory usage will be proportional to the size of the tree. How much worse than optimal is this? It depends on the tree. If it's a complete binary tree, you've doubled your memory usage, which might not be too bad. But if the tree is a path, then you use linear memory, whereas a proper queue would only use O(1) memory.
- lliiffee 10y agoYou could periodically delete the wasted space. I think that if you, say, delete the wasted space when it is equal to the used space, you still still have O(1) amortized time.
- marvy 10y agoYou could, but then it's not quite so quick-and-dirty anymore :) The de-queue method goes from "self.i += 1" (Python syntax) to self.i +=1 if self.i > len(self.a)/2: self.a[:self.i] = [] self.i = 0 I didn't test the above code, and I am only 50% sure it is bug-free. I'm 99% sure the leaky version is bug-free. Memory leaks are not a bug if I document them, right? ;) But yes, periodically deleting the wasted space is still easier than trying to do the usual thing with circular buffers and stuff :)
- lliiffee 10y agoI definitely see your point! I guess there is a place for algorithms at any point on the easy/good trade-off.
- andrepd 10y agoEasier and a major performance disaster. You shouldn't ever do this ever. If you are a programmer, it's your job to implement this correctly.
- Asooka 10y agoI'm not sure about being a performance disaster, memmove is a really fast operation and a circular buffer has its own problems regarding cache use. If you can, measure. If you can't, use the simpler algorithm.
- marvy 10y agoAsooka: a lot of your comments are showing up as dead. I have no clue why, they seem fine to me. I can't reply directly to the one you made in this thread: it's dead too.
- munificent 10y agoYou can avoid the memory leak without adding too much complexity by just making it a circular buffer: https://en.wikipedia.org/wiki/Circular_buffer https://en.wikipedia.org/wiki/Circular_buffer
- pkd 10y agoI wouldn't call this a trick. This is a staple in the data structures books when they teach how to implement queues using arrays. The same approach can be extended to implementing circular and double ended queues as well.