On: Itsy Bitsy Data Structures – Simplified examples o...

[lliiffee]

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 → lliiffee]

You 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 :)

[andrepd → marvy]

Easier 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.

[marvy → andrepd]

Asooka: 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.

[lliiffee → marvy]

I definitely see your point! I guess there is a place for algorithms at any point on the easy/good trade-off.