6 ms·
You 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)
by lliiffee 10y ago
You 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.