> If all the problem is about performance of pop(0) operations when the > queues grow a lot, why not implement a queue as a list of lists > (sublists), and all the magic will be to select an appropriate maximum > size for the sublists? Wouldn't this be actually a simulation of the > "extra space at the left side of the list" algorithm without touching > the C list implementation? *pulls out algorithm analysis hat* If your maximum size of the sublist is k, then any pop is at least O(k). If you have a total of n items in the queue, then every k items incurrs an O(n/k) penalty for the outer list shuft, or O(n/k^2) per item, or overall O(k + n/k^2) per pop for a total queue size of n, and a maximum sublist size of k. for k > n^(1/3), this is O(k) per pop operation for k < n^(1/3), this is O(n/k^2) per pop operation, which is always greater than k As k approaches 1, pops are horrible, but as long as k is greater than the cube root of n, the operations are reasonable. If one knows the maximal size of the queue beforehand, setting up a properly sized k would result in reasonable behavior using lists of lists. However, using knuth's method, a dictionary fifo, or [val, [val, []]] all result in O(1) puts and gets, on either end (the [val, [val, []]] would require a previous pointer). > Another idea, for a single list solution where most of the times there > are lots of puts and then mostly lots of gets, perhaps this would be > fast: > > An attribute of the instance stores the last operation (put or get) > If the current operation is not the same as the last, first reverse the > underlying list, then do append() or pop(). > > But that is not practical for very large queues. It would be perfectly reasonable for a streamed puts/gets, but I don't know how common such behavior is necessary. - Josiah
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4