Fast Efficient way to transfer an object to another list

[Steven D'Aprano]

On Sat, 01 May 2010 08:11:45 -0700, Francesco Bochicchio wrote:

> On 1 Mag, 05:35, Steven D'Aprano <st... at REMOVE-THIS- cybersource.com.au>
> wrote:
> 
> 
>> def transfer_stock(stock_code, old_list, new_list):
>>     """ Transfer a stock from one list to another """ while True:  #
>>     loop forever
>>         try:
>>             i = old_list.index(stock_code)
>>         except ValueError:
>>             # not found, so we're done
>>             break
>>         new_list.append(old_list[i])
>>         del old_list[i]
>>     return new_list
>>
>> --
>> Steven
> 
> I think this could be slower than doing like the OP, since  'index'
> rescan the whole list every time
> while doing an explicit loop you only scan the list once.

If the list is sufficiently big enough, yes, you are correct. But since 
list.index is fast C code, and a while loop is slow Python code, it would 
need to be fairly big, and probably much bigger than you think!

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. This requires another very small change. Putting them 
together:

# Untested.
def transfer_stock(stock_code, old_list, new_list):
    """ Transfer a stock from one list to another """
    i = 0
    while True:  # loop forever
        try:
            i = old_list.index(stock_code, i)
        except ValueError:
            # not found, so we're done
            break
        new_list.append(old_list[i])
        old_list[i] = old_list[-1]
        del old_list[-1]
    return new_list

This should be very much faster, for hardly any extra complexity.



> Anyway i think that list.extract( old_list, predicate ) -> new_list
> would be a nice addition to the standard library (possibly a C faster
> version of what one could implement in python) ... and since the library
> is not under moratorium maybe we will have it ...  

But since it is a method on a built-in (list), and not a library 
function, it does fall under the moratorium.



-- 
Steven