Efficient Find and Replace

[Steven D'Aprano]

On Fri, 27 Jan 2006 16:34:53 -0800, Murali wrote:

> I did not actually run the code, so there may be syntax errors and so
> forth. But how is L[x] = Y an O(1) operation. Given x finding L[x]
> would require to traverse x nodes in the list. So finding L[x] requires
> O(x) time. Once you find L[x] setting it to Y is O(1) I agree.


You are assuming that Python lists are linked lists. They are not. They
are arrays. Accessing the entry at position x doesn't require traversing
the list at all.


> In Solution B: By L.index(X), I mean search for X and then replace it
> with Y. Here every time the search starts from the beginning of the
> list. Hence the inefficiency.

Yes, but the inefficient search code is done in C, which is so fast that
it really doesn't matter unless your list is HUGE. 



-- 
Steven.