Efficient Find and Replace
David Hirschfield
davidh at ilm.com
Fri Jan 27 19:49:24 EST 2006
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.
More information about the Python-list
mailing list