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
--
http://mail.python.org/mailman/listinfo/python-list
