Efficient Find and Replace

[David Hirschfield]

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.