Efficient Find and Replace

[Fredrik Lundh]

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>