Thanks for the replies. I always thought that Python lists were
actually lists under the hood. If they are implemented as arrays of
pointers things should be a lot more efficient. In particular what I
thought was a Linear-time operation is actually an O(1) operation.
Since python allows you to rep
Murali wrote:
> Given: L = list of integers. X and Y are integers.
> Problem: find every occurrence of X and replace with Y
> Problem with both solutions is the efficiency.
As everyone else says, you are hallucinating efficiency problems
probably brought on by an overdose of Lisp or ML. Here
> > > for i,v in enumerate(L):
> > > if v == X:
> > > L[i] = Y
> >
> > Here's an alternate solution using a replacement dictionary:
> >
> > M = {X:Y}
> > for i, v in enumerate(L):
> > L[i] = M.get(v, v)
[Fredrik Lundh]
> but that's 2-3 times slower than the OP's corrected cod
Raymond Hettinger wrote:
> > for i,v in enumerate(L):
> > if v == X:
> > L[i] = Y
>
> Here's an alternate solution using a replacement dictionary:
>
> M = {X:Y}
> for i, v in enumerate(L):
> L[i] = M.get(v, v)
but that's 2-3 times slower than the OP's corrected code for his
[David Hirschfield]
> for i,v in enumerate(L):
> if v == X:
> L[i] = Y
Here's an alternate solution using a replacement dictionary:
M = {X:Y}
for i, v in enumerate(L):
L[i] = M.get(v, v)
The replacement dictionary directly supports generalization to multiple
substitution pa
On Fri, 27 Jan 2006 16:49:24 -0800, David Hirschfield wrote:
> You aren't getting too many helpful responses.
Surely pointing out the poster's incorrect assumptions is helpful?
If I said, "I want to add two integers together, but Python's + only does
string concatenation, so I wrote this functio
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] s
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.
no, L[x] is an O(1) operation in both Python and C.
th
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
>But how is L[x] = Y an O(1) operation. Given x finding L[x] would require to
>traverse x nodes in the list.
Python list is a deceptive name, because they are 1D arrays of
pointers. Maybe they are called lists because array(...) is shorter
than list(...).
Bye,
bearophile
--
http://mail.python.
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.
In Solution B: By L.index(
>Because L.index() and L[x:x] both take O(N) time in the worst case.
Why do you think L[x:x] can be O(N)?
This looks O-linear enough to me:
>>> from random import choice
>>> L = [choice("ab") for i in xrange(10)]
>>> L
['b', 'b', 'b', 'a', 'b', 'a', 'b', 'a', 'a', 'a']
>>> for x in xrange(len(L)
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]
13 matches
Mail list logo
