Fast Efficient way to transfer an object to another list

[Bryan]

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