Algorithm help per favore

Steven Taschuk staschuk at
Thu Jun 19 01:54:24 CEST 2003

Quoth Bengt Richter:
> On Wed, 18 Jun 2003 10:41:23 -0600, Steven Taschuk <staschuk at> wrote:
> >If speed is the goal, removing elements from the existing list is
> >not indicated; that would take O(n**2) time, since each removal
> >has to shift all subsequent elements down one spot.
> You've probably posted and oops by now, [...]

Flattering!  No, I just didn't think of the compacting approach.
(Quite an alarming oversight.)

Your code is significantly faster than mine as is, without any
effort to optimize yours further.  With Python 2.3b1, using some
random 10,000-element lists of small integers in which consecutive
elements have probabilities 1/10 to 1/90 of being equal, it's
about twice as fast.  (It's obviously also more memory-spartan.)

Steven Taschuk                                                   w_w
staschuk at                                      ,-= U
                                                               1 1

More information about the Python-list mailing list