Algorithm help per favore

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


Quoth Bengt Richter:
> On Wed, 18 Jun 2003 10:41:23 -0600, Steven Taschuk <staschuk at telusplanet.net> 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 telusplanet.net                                      ,-= U
                                                               1 1





More information about the Python-list mailing list