Re: Efficient Find and Replace
for i,v in enumerate(L):
if v == X:
L[i] = Y
Here's an alternate solution using a replacement dictionary:
M = {X:Y}
for i, v in enumerate(L):
L[i] = M.get(v, v)
[Fredrik Lundh]
but that's 2-3 times slower than the OP's corrected code for his use
case, so I'm not sure it qualifies as more efficient...
The alternate wasn't presented for efficiency. Its virtue is that with
no additional effort, it generalizes to substituting multiple
find/replace pairs in a single pass.
Raymond
--
http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
Murali wrote: Given: L = list of integers. X and Y are integers. Problem: find every occurrence of X and replace with Y Problem with both solutions is the efficiency. As everyone else says, you are hallucinating efficiency problems probably brought on by an overdose of Lisp or ML. Here is another way to get to what you want that will go even faster than the not-a-problem speed you have from simple compare and replace. lst = range(50) * 10 try: position = lst.index(X) while True: lst[position] = Y position = lst.index(X, position + 1) except ValueError: pass # finally could not find X I mention this only because people always seem to forget than index allows you to specify a start (and/or stop) position w/in the list. --Scott David Daniels [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
Thanks for the replies. I always thought that Python lists were actually lists under the hood. If they are implemented as arrays of pointers things should be a lot more efficient. In particular what I thought was a Linear-time operation is actually an O(1) operation. Since python allows you to replace single items with lists e.g. L[x:x+1]= [a,b,c], It has to be a little more clever. But with good data structure design I beleive that this overhead can be amortized to O(1). The optional argument to lst.index also makes that an linear time code. Thanks for all the help. - Murali PS: Slowly python is becoming my more favourite language than even C (except in cases you just cannot use anything but C, e.g. writing a boot loader) -- http://mail.python.org/mailman/listinfo/python-list
Efficient Find and Replace
Given: L = list of integers. X and Y are integers.
Problem: find every occurence of X and replace with Y
Solution1:
def check(s):
if s==X:
return Y
else return s
newL = [ check(s) for s in L]
Now I dont want to create another list but just modify it in place.
SolutionA:
for x in range(len(L)):
if L[x] == X:
L[x:x] = Y
SolutionB:
p = L.index(X)
while p = 0:
L[p:p] = Y
p = L.index(X)
Problem with both solutions is the efficiency. Both methods require
time O(N^2) in the worst case, where N is the length of the list.
Because L.index() and L[x:x] both take O(N) time in the worst case. But
clearly one should be able to do it in time O(N). Atleast there is a C
solution which does it in O(N) time.
p = head(L)
while (p) {
if (p-data == X) p-data = Y;
}
Is there a python equivalent of this? using iterators or something
which will allow me efficient serial access to the list elements.
- Murali
--
http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
Murali wrote: Now I dont want to create another list but just modify it in place. Why does that matter? List copies are cheap. SolutionA: for x in range(len(L)): if L[x] == X: L[x:x] = Y Did you run this code ? SolutionB: p = L.index(X) while p = 0: L[p:p] = Y p = L.index(X) Did you run this code ? Problem with both solutions is the efficiency. Both methods require time O(N^2) in the worst case, where N is the length of the list. Because L.index() and L[x:x] both take O(N) time in the worst case. Assigning a single item to L[x:x] doesn't work. Assigning M items to a slice of length M is an O(M) operation, so if you do L[x:x+1] = [Y], you get your O(1) operation. But that's just a silly way to write L[x] = Y, which I assume was what you meant. L[x] = Y is also an O(1) operation, of course. /F -- http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
Because L.index() and L[x:x] both take O(N) time in the worst case. Why do you think L[x:x] can be O(N)? This looks O-linear enough to me: from random import choice L = [choice(ab) for i in xrange(10)] L ['b', 'b', 'b', 'a', 'b', 'a', 'b', 'a', 'a', 'a'] for x in xrange(len(L)): ... if L[x] == a: L[x] = c L ['b', 'b', 'b', 'c', 'b', 'c', 'b', 'c', 'c', 'c'] Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
I did not actually run the code, so there may be syntax errors and so forth. But how is L[x] = Y an O(1) operation. Given x finding L[x] would require to traverse x nodes in the list. So finding L[x] requires O(x) time. Once you find L[x] setting it to Y is O(1) I agree. In Solution B: By L.index(X), I mean search for X and then replace it with Y. Here every time the search starts from the beginning of the list. Hence the inefficiency. - Murali -- http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
But how is L[x] = Y an O(1) operation. Given x finding L[x] would require to traverse x nodes in the list. Python list is a deceptive name, because they are 1D arrays of pointers. Maybe they are called lists because array(...) is shorter than list(...). Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
You aren't getting too many helpful responses. Hope this one helps:
The closest python equivalent to:
p = head(L)
while (p) {
if (p-data == X) p-data = Y;
}
would be:
for i,v in enumerate(L):
if v == X:
L[i] = Y
modifies the list in place.
There's nothing wrong with just doing your solution A, the amount of
time wasted by creating the new list isn't very significant.
-Dave
Murali wrote:
Given: L = list of integers. X and Y are integers.
Problem: find every occurence of X and replace with Y
Solution1:
def check(s):
if s==X:
return Y
else return s
newL = [ check(s) for s in L]
Now I dont want to create another list but just modify it in place.
SolutionA:
for x in range(len(L)):
if L[x] == X:
L[x:x] = Y
SolutionB:
p = L.index(X)
while p = 0:
L[p:p] = Y
p = L.index(X)
Problem with both solutions is the efficiency. Both methods require
time O(N^2) in the worst case, where N is the length of the list.
Because L.index() and L[x:x] both take O(N) time in the worst case. But
clearly one should be able to do it in time O(N). Atleast there is a C
solution which does it in O(N) time.
p = head(L)
while (p) {
if (p-data == X) p-data = Y;
}
Is there a python equivalent of this? using iterators or something
which will allow me efficient serial access to the list elements.
- Murali
--
Presenting:
mediocre nebula.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
Murali wrote: I did not actually run the code, so there may be syntax errors and so forth. But how is L[x] = Y an O(1) operation. Given x finding L[x] would require to traverse x nodes in the list. So finding L[x] requires O(x) time. no, L[x] is an O(1) operation in both Python and C. the list type uses an internal array, using over-allocation to make L.append(x) amortized O(1). /F -- http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
On Fri, 27 Jan 2006 16:34:53 -0800, Murali wrote: I did not actually run the code, so there may be syntax errors and so forth. But how is L[x] = Y an O(1) operation. Given x finding L[x] would require to traverse x nodes in the list. So finding L[x] requires O(x) time. Once you find L[x] setting it to Y is O(1) I agree. You are assuming that Python lists are linked lists. They are not. They are arrays. Accessing the entry at position x doesn't require traversing the list at all. In Solution B: By L.index(X), I mean search for X and then replace it with Y. Here every time the search starts from the beginning of the list. Hence the inefficiency. Yes, but the inefficient search code is done in C, which is so fast that it really doesn't matter unless your list is HUGE. -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
On Fri, 27 Jan 2006 16:49:24 -0800, David Hirschfield wrote: You aren't getting too many helpful responses. Surely pointing out the poster's incorrect assumptions is helpful? If I said, I want to add two integers together, but Python's + only does string concatenation, so I wrote this function to add two ints using bit manipulation. How do I make it go faster? would it be better to optimize the bit manipulation code, or to just tell me that + also does integer addition? -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
[David Hirschfield]
for i,v in enumerate(L):
if v == X:
L[i] = Y
Here's an alternate solution using a replacement dictionary:
M = {X:Y}
for i, v in enumerate(L):
L[i] = M.get(v, v)
The replacement dictionary directly supports generalization to multiple
substitution pairs without needing additional passes over the input.
Also, if you feel the need for speed, the method lookup can be bound
outside of the loop:
# Find/Replace multiple pairs in a single pass using a bound method
M = {X1:Y1, X2:Y2, X3:Y3}
Mget = M.get
for i, v in enumerate(L):
L[i] = Mget(v, v)
Raymond
--
http://mail.python.org/mailman/listinfo/python-list
Re: Efficient Find and Replace
Raymond Hettinger wrote:
for i,v in enumerate(L):
if v == X:
L[i] = Y
Here's an alternate solution using a replacement dictionary:
M = {X:Y}
for i, v in enumerate(L):
L[i] = M.get(v, v)
but that's 2-3 times slower than the OP's corrected code for his use
case, so I'm not sure it qualifies as more efficient...
/F
--
http://mail.python.org/mailman/listinfo/python-list
