Efficient Find and Replace
Fredrik Lundh
fredrik at pythonware.com
Fri Jan 27 19:20:28 EST 2006
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>
More information about the Python-list
mailing list