Fast Efficient way to transfer an object to another list

[Jimbo]

Hello I have a relatively simple thing to do; move an object from one
to list into another. But I think my solution maybe inefficient &
slow. Is there a faster better way to move my stock object from one
list to another? (IE, without having to use a dictionary instead of a
list or is that my only solution?)

class stock:

    code = "NULL"
    price = 0


stock_list1 = []
stock_list2 = []

def transfer_stock(stock_code, old_list, new_list):
    """ Transfer a stock from one list to another """
    # is there a more efficient & faster way to

    index = 0

    for stock in old_list:

        temp_stock = stock

        if temp_stock.code == stock_code:
            new_list.append(temp_stock)
            del old_list[index]
        index += 1

    return new_list

 

[Kushal Kumaran]

Hello I have a relatively simple thing to do; move an object from one
to list into another. But I think my solution maybe inefficient &
slow. Is there a faster better way to move my stock object from one
list to another? (IE, without having to use a dictionary instead of a
list or is that my only solution?)

class stock:

   code = "NULL"
   price = 0


stock_list1 = []
stock_list2 = []

def transfer_stock(stock_code, old_list, new_list):
   """ Transfer a stock from one list to another """
   # is there a more efficient & faster way to

   index = 0

   for stock in old_list:

       temp_stock = stock

       if temp_stock.code == stock_code:
           new_list.append(temp_stock)
           del old_list[index]
       index += 1

   return new_list

Does your code work correctly? Modifying old_list while iterating
over it will not work the way you expect, unless you're careful. And
what is the point of temp_stock?

 

[Steven D'Aprano]

Hello I have a relatively simple thing to do; move an object from one to
list into another. But I think my solution maybe inefficient & slow. Is
there a faster better way to move my stock object from one list to
another? (IE, without having to use a dictionary instead of a list or is
that my only solution?)

If you already know which object needs to be moved, it is easy:

fruits = ["apple", "banana", "carrot", "orange", "pear"]
vegetables = ["potato", "lettuce", "onion"]

# move carrot from fruits to vegetables ....
vegetables.append("carrot")
fruits.remove("carrot")

print fruits ['apple', 'banana', 'orange', 'pear']
print vegetables

['potato', 'lettuce', 'onion', 'carrot']


The only tricky thing is if you don't know which object needs to be
moved. The way to solve that depends on what you need to do -- is there
only one object that might need to be moved, or could there be more than
one? How do you recognise it? There are many solutions. Here's one:

even_numbers = []
odd_numbers = odd_numbers = [1, 9, 8, 6, 2, 7, 3, 0, 4, 5]
for i in range(len(odd_numbers)-1, -1, -1):

.... n = odd_numbers
.... if n % 2 == 0: # even?
.... even_numbers.append(n)
.... del odd_numbers
....

even_numbers [4, 0, 2, 6, 8]
odd_numbers

[1, 9, 7, 3, 5]


Can you see why I iterated over the list backwards? Why didn't I just do
this?

for i, n in enumerate(odd_numbers):
if n % 2 == 0: # even?
even_numbers.append(n)
del odd_numbers



You can re-write this more efficiently by using Python built-ins. First
you need to recognise what it is doing: first it searches for the item
with the stock code, then it appends it to the new list, then it deletes
it from the old list.

def transfer_stock(stock_code, old_list, new_list):
""" Transfer a stock from one list to another """
# is there a more efficient & faster way to
index = 0
for stock in old_list:
temp_stock = stock
if temp_stock.code == stock_code:
new_list.append(temp_stock)
del old_list[index]
index += 1
return new_list

If you know there is one, and only one, item with that stock code:


def transfer_stock(stock_code, old_list, new_list):
""" Transfer a stock from one list to another """
i = old_list.index(stock_code) # search
new_list.append(old_list) # copy
del old_list # delete
return new_list


However, this will fail to work correctly if you have more than one
identical stock codes that all need to be moved, or if there are none. So
here's a version that handles both cases:


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)
del old_list
return new_list

 

[Tim Chase]

If you know there is one, and only one, item with that stock code:

def transfer_stock(stock_code, old_list, new_list):
""" Transfer a stock from one list to another """
i = old_list.index(stock_code) # search
new_list.append(old_list) # copy
del old_list # delete
return new_list

This could be written as

def move(code, source, dest):
dest.append(source.pop(source.index(code)))
return dest

depending on how one thinks. I tend to prefer

lst.pop(idx)

over

tmp = lst[idx]
del lst[idx]

only using the latter if "idx" is a range/slice.

Though since the function mutates the arguments, I'd be tempted
to return None like list.sort() does for the same rationale.

If more than one item is in the source, it will move/remove the
first leaving the remainder; if no matching item is in the source
it will appropriately raise a ValueError.

-tkc

 

[MRAB]

If you know there is one, and only one, item with that stock code:

def transfer_stock(stock_code, old_list, new_list):
""" Transfer a stock from one list to another """
i = old_list.index(stock_code) # search
new_list.append(old_list) # copy
del old_list # delete
return new_list

This could be written as

def move(code, source, dest):
dest.append(source.pop(source.index(code)))
return dest

depending on how one thinks. I tend to prefer

lst.pop(idx)

over

tmp = lst[idx]
del lst[idx]

only using the latter if "idx" is a range/slice.

Though since the function mutates the arguments, I'd be tempted to
return None like list.sort() does for the same rationale.

If more than one item is in the source, it will move/remove the first
leaving the remainder; if no matching item is in the source it will
appropriately raise a ValueError.

It would be more efficient if instead of deleting or popping the item
you moved the last one into its place:

if idx == len(source) - 1:
item = source.pop()
else:
item = source[idx]
source[idx] = source.pop()

assuming that the order of the items in the list doesn't matter.

 

[Francesco Bochicchio]

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)
        del old_list
    return new_list

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.

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 ... the semantic could be like th OP asked:

--- code begins

class ListE(list):
def extract(self, predicate):
res = []
for idx, el in enumerate(self):
if predicate(el):
res.append( self.pop(idx) )
return res

class Stock(object):
def __init__(self, code):
self.code = code
def __repr__(self): return "Stock: code=%d" % self.code

l = ListE( Stock(n) for n in range(19) )

subl = l.extract( lambda x: x.code in (1,4, 9) )

print " l = ", l
print "subl = ", subl

--- code ends
--- results

l = [Stock: code=0, Stock: code=2, Stock: code=3, Stock: code=5,
Stock: code=6, Stock: code=7, Stock: code=8, Stock: code=10, Stock:
code=11, Stock: code=12, Stock: code=13, Stock: code=14, Stock:
code=15, Stock: code=16, Stock: code=17, Stock: code=18]
subl = [Stock: code=1, Stock: code=4, Stock: code=9]




Ciao

 

[Steven D'Aprano]

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)
        del old_list
    return new_list

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)
        old_list = 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.

 

[Hans Mulder]

Anyway i think that list.extract( old_list, predicate ) -> new_list
would be a nice addition to the standard library

You could use filter( predicate, old_list ) -> new_list

-- HansM

 

[Bryan]

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):
result.append(lst)
else:
lst[j] = lst
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

 

[Gabriel Genellina]

Hello I have a relatively simple thing to do; move an object from one
to list into another. But I think my solution maybe inefficient &
slow. Is there a faster better way to move my stock object from one
list to another? (IE, without having to use a dictionary instead of a
list or is that my only solution?)

class stock:

code = "NULL"
price = 0


stock_list1 = []
stock_list2 = []

def transfer_stock(stock_code, old_list, new_list):
""" Transfer a stock from one list to another """
# is there a more efficient & faster way to

index = 0

for stock in old_list:

temp_stock = stock

if temp_stock.code == stock_code:
new_list.append(temp_stock)
del old_list[index]
index += 1

return new_list

I'd do that in two steps:

def transfer_stock(stock_code, old_list, new_list):
# find the indexes to transfer
indexes = [i for i,stock in enumerate(old_list)
if stock.code==stock_code]
# actually transfer them
for index in reversed(indexes):
stock = old_list[index]
new_list.append(stock)
del old_list[index]
# I would not return anything

 

[Bryan]

I'd do that in two steps:

def transfer_stock(stock_code, old_list, new_list):
   # find the indexes to transfer
   indexes = [i for i,stock in enumerate(old_list)
              if stock.code==stock_code]
   # actually transfer them
   for index in reversed(indexes):
     stock = old_list[index]
     new_list.append(stock)
     del old_list[index]
   # I would not return anything

The first step -- finding the items -- looks great. The step of adding
items to new_list is just a bit squirly in that it reverse the order
they had in old_list. The last step -- deleting them from old_list --
is a sluggish order n**2 run-time; it can be done in order n. (That's
worst-case; your solution is linear time if either very few elements
get transferred or very few do not get transferred.)

Inspired by your use of list comprehension, and noting the simplicity
of the condition for transferring an item, I suggest the following
compact, order-preserving, linear-time solution:


def transfer_stock(stock_code, old_list, new_list):
new_list.extend(s for s in old_list if s.code==stock_code)
old_list[:] = [s for s in old_list if s.code!=stock_code]



#
# Even obviously-correct code deserves testing:
#

from random import choice

class Blurf:
def __init__(self, code):
self.code = code

for nitems in range(10):
for _ in range(17):
nl_prefix = choice(range(13))
new_list = [Blurf(3) for _ in range(nl_prefix)]
old_list = [Blurf(choice([3, 9])) for _ in range(nitems)]
nitems = len(new_list) + len(old_list)
original_new_list = new_list[:]
original_old_list = old_list[:]

transfer_stock(3, old_list, new_list)

assert len(old_list) + len(new_list) == nitems
for n in new_list:
assert n.code == 3
assert n in original_new_list or n in original_old_list
source = original_new_list + original_old_list
assert new_list == [s for s in source if s in new_list]
for n in old_list:
assert n.code != 3
assert n in original_new_list or n in original_old_list
assert old_list == [s for s in original_old_list
if s in old_list]