Re: Fast Efficient way to transfer an object to another list

[Bryan]

Gabriel Genellina wrote:
> 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]


--
--Bryan
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Fast Efficient way to transfer an object to another list

[Gabriel Genellina]

En Fri, 30 Apr 2010 23:16:04 -0300, Jimbo  escribió:


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?)

[code]
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[/code]


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

--
Gabriel Genellina

--
http://mail.python.org/mailman/listinfo/python-list

Re: 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
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Fast Efficient way to transfer an object to another list

[Hans Mulder]

Francesco Bochicchio wrote:


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



--
http://mail.python.org/mailman/listinfo/python-list

Re: 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 
> 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
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Fast Efficient way to transfer an object to another list

[Daniel Stutzbach]

On Fri, Apr 30, 2010 at 9:16 PM, Jimbo  wrote:

> 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.
>

Removing an item from a list is O(n) on average, so it's going to be a bit
slow any way you slice it (unless you only remove from the end of the list
which is O(1)).

Can you tell us more about why you're using a list?  If the order of the
items doesn't matter, you may be able to use a set().

If the order matters, how is the list ordered?  If we know how the list is
ordered, we may be able to help you come up with a clever way to remove an
item cheaply.
--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC 
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Fast Efficient way to transfer an object to another list

[Francesco Bochicchio]

On 1 Mag, 05:35, Steven D'Aprano  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.

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
---
FB
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Fast Efficient way to transfer an object to another list

[MRAB]

Tim Chase wrote:

On 04/30/2010 10:35 PM, Steven D'Aprano wrote:

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[i])  # copy
 del old_list[i]  # 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.
--
http://mail.python.org/mailman/listinfo/python-list

Re: Fast Efficient way to transfer an object to another list

[Tim Chase]

On 04/30/2010 10:35 PM, Steven D'Aprano wrote:

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[i])  # copy
 del old_list[i]  # 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




--
http://mail.python.org/mailman/listinfo/python-list

Re: Fast Efficient way to transfer an object to another list

[Steven D'Aprano]

On Fri, 30 Apr 2010 19:16:04 -0700, Jimbo wrote:

> 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[i]
... if n % 2 == 0:  # even?
... even_numbers.append(n)
... del odd_numbers[i]
...
>>> 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[i]



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[i])  # copy
del old_list[i]  # 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[i])
del old_list[i]
return new_list



-- 
Steven
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Fast Efficient way to transfer an object to another list

[Kushal Kumaran]

On Sat, May 1, 2010 at 7:46 AM, Jimbo  wrote:
> 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?)
>
> [code]
> 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[/code]

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?

-- 
regards,
kushal
-- 
http://mail.python.org/mailman/listinfo/python-list

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?)

[code]
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[/code]
-- 
http://mail.python.org/mailman/listinfo/python-list