Steven D'Aprano wrote:
> The simplest way to speed the above code up is not to start from the
> beginning each time. That requires two very small changes. And since
> deletions from the front of the list are slow, MRAB's suggestion is also
> a good idea.
Those two speed-ups provide worst-case linear run-time, but as MRAB
astutely noted, his optimization assumes that order is unimportant.
That's a bad assumption for a general extract-from-list function.
Where order does not matter, I'd suspect 'list' was a poor choice of
data type. Here's a general, order-preserving, linear-time version:
def extract(lst, predicate):
""" Return items of lst satisfying predicate, deleting them from
lst.
"""
result = []
j = 0
for i in range(len(lst)):
if predicate(lst[i]):
result.append(lst[i])
else:
lst[j] = lst[i]
j += 1
del lst[j:]
return result
# some testing:
for nitems in range(10):
for pred in [lambda x: True,
lambda x: False,
lambda x: x % 2 == 0,
lambda x: x % 2 == 1,
lambda x: x < nitems // 2,
lambda x: x >= nitems // 2]:
original = list(range(nitems))
source = original[:]
extracted = extract(source, pred)
assert len(source) + len(extracted) == nitems
assert sorted(source) == source
for n in source:
assert not pred(n)
assert n in original
assert sorted(extracted) == extracted
for n in extracted:
assert pred(n)
assert n in original
--
--Bryan
--
http://mail.python.org/mailman/listinfo/python-list
