Efficient Find and Replace

[Murali]

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

[Fredrik Lundh]

Re: Efficient Find and Replace

Murali wrote:
[color=blue]
> Now I dont want to create another list but just modify it in place.[/color]

Why does that matter? List copies are cheap.
[color=blue]
> SolutionA:
>
> for x in range(len(L)):
> if L[x] == X:
> L[x:x] = Y[/color]

Did you run this code ?
[color=blue]
> SolutionB:
>
> p = L.index(X)
> while p >= 0:
> L[p:p] = Y
> p = L.index(X)[/color]

Did you run this code ?
[color=blue]
> 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.[/color]

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>

[bearophileHUGS@lycos.com]

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:
[color=blue][color=green][color=darkred]
>>> from random import choice
>>> L = [choice("ab") for i in xrange(10)]
>>> L[/color][/color][/color]
['b', 'b', 'b', 'a', 'b', 'a', 'b', 'a', 'a', 'a'][color=blue][color=green][color=darkred]
>>> for x in xrange(len(L)):[/color][/color][/color]
.... if L[x] == "a": L[x] = "c"[color=blue][color=green][color=darkred]
>>> L[/color][/color][/color]
['b', 'b', 'b', 'c', 'b', 'c', 'b', 'c', 'c', 'c']

Bye,
bearophile

[Murali]

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

[bearophileHUGS@lycos.com]

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

[David Hirschfield]

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:
[color=blue]
>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
>
>
>[/color]

--
Presenting:
mediocre nebula.

[Fredrik Lundh]

Re: Efficient Find and Replace

Murali wrote:
[color=blue]
> 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.[/color]

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>

[Steven D'Aprano]

Re: Efficient Find and Replace

On Fri, 27 Jan 2006 16:34:53 -0800, Murali wrote:
[color=blue]
> 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.[/color]


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.

[color=blue]
> 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.[/color]

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.

[Steven D'Aprano]

Re: Efficient Find and Replace

On Fri, 27 Jan 2006 16:49:24 -0800, David Hirschfield wrote:
[color=blue]
> You aren't getting too many helpful responses.[/color]

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.

[Raymond Hettinger]

Re: Efficient Find and Replace

[David Hirschfield][color=blue]
> for i,v in enumerate(L):
> if v == X:
> L[i] = Y[/color]

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

[Fredrik Lundh]

Re: Efficient Find and Replace

Raymond Hettinger wrote:
[color=blue][color=green]
> > for i,v in enumerate(L):
> > if v == X:
> > L[i] = Y[/color]
>
> Here's an alternate solution using a replacement dictionary:
>
> M = {X:Y}
> for i, v in enumerate(L):
> L[i] = M.get(v, v)[/color]

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>

[Raymond Hettinger]

Re: Efficient Find and Replace

> > > for i,v in enumerate(L):[color=blue][color=green][color=darkred]
> > > if v == X:
> > > L[i] = Y[/color]
> >
> > Here's an alternate solution using a replacement dictionary:
> >
> > M = {X:Y}
> > for i, v in enumerate(L):
> > L[i] = M.get(v, v)[/color][/color]

[Fredrik Lundh][color=blue]
> 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" ...[/color]

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

[Scott David Daniels]

Re: Efficient Find and Replace


Murali wrote:[color=blue]
> Given: L = list of integers. X and Y are integers.
> Problem: find every occurrence of X and replace with Y[/color]
[color=blue]
> Problem with both solutions is the efficiency.[/color]

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
scott.daniels@a cm.org

[Murali]

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)