Re: Fast Efficient way to transfer an object to another list
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
En Fri, 30 Apr 2010 23:16:04 -0300, Jimbo nill...@yahoo.com 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
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 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
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
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
On 1 Mag, 05:35, Steven D'Aprano st...@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. 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
On Fri, Apr 30, 2010 at 9:16 PM, Jimbo nill...@yahoo.com 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://stutzbachenterprises.com -- http://mail.python.org/mailman/listinfo/python-list
Re: Fast Efficient way to transfer an object to another list
On Sat, 01 May 2010 08:11:45 -0700, Francesco Bochicchio wrote: On 1 Mag, 05:35, Steven D'Aprano st...@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 -- http://mail.python.org/mailman/listinfo/python-list
Fast Efficient way to transfer an object to another list
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
Re: Fast Efficient way to transfer an object to another list
On Sat, May 1, 2010 at 7:46 AM, Jimbo nill...@yahoo.com 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
Re: Fast Efficient way to transfer an object to another list
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
