[Jeremy Fincher, on
<http://tinyurl.com/9x6d>
]
> That's definitely an inadequate test. First,if I read correctly,
> the test function doesn't test the plain list or array.array('i') as
> fifos, it tests them as a lifos (using simple .append(elt) and .pop()).
That's right, alas. Mr. Delaney was implementing stacks there, and just
calling them fifos.
> Second, it never allows the fifo to have a size greater than 1, which
> completely negates the O(N) disadvantage of simple list-based
> implementations.
Yup.
> ...
> <http://www.cis.ohio-state.edu/~fincher/fifo_comparison.py>.
> ...
> (The O1ListSubclassFifo uses the standard (at least standard in
> functional programming :)) implementation technique of using two
> singly-linked lists, one for the front of the queue and another for the
> back of the queue.)
The Dark Force has seduced you there:
class O1ListSubclassFifo(list):
__slots__ = ('back',)
def __init__(self):
self.back = []
def enqueue(self, elt):
self.back.append(elt)
def dequeue(self):
if self:
return self.pop()
else:
self.back.reverse()
self[:] = self.back
self.back = []
return self.pop()
That is, you're subclassing merely to reuse implementation, not because you
want to claim that O1ListSubclassFifo is-a list. It's better not to
subclass list, and use two lists via has-a instead, say self.front and
self.back. Then the O(N)
self[:] = self.back
can be replaced by the O(1) (for example)
self.front = self.back
Of course, this is Python <wink>, so it may not actually be faster that way:
you save some C-speed list copies, but at the cost of more-expensive
Python-speed dereferencing ("self.pop" vs "self.front.pop"). But even if
it's slower, it's better not to pretend this flavor of FIFO is-a list (e.g.,
someone doing len(), pop(), append() on one of these instances is going to
get a bizarre result).
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