Algorithm help per favore
bokr at oz.net
Wed Jun 18 20:29:29 CEST 2003
On Wed, 18 Jun 2003 10:41:23 -0600, Steven Taschuk <staschuk at telusplanet.net> wrote:
>> I need to take a list (probably 20k to 40k elements) of numbers and
>> remove consecutive duplicates. Non consecutive duplicates are ok.
>> Example: [6,3,3,3,5,7,6,3,4,4,3] => [6,3,5,7,6,3,4,3]
>> The 3 and 6 can appear more than once in the result set because
>> they're separated by another value. Obviously this is trivial to
>> accomplish by walking thru the list and building a new one (or yanking
>> elements out of the existing one) but I'm curious if anyone knows of a
>> more clever way, with speed being a goal more than memory usage.
>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, but I don't think that has to take O(n**2) ;-)
(Untested beyond what you see here, so I could have an oops coming ;-)
>>> def listuniq(thelist):
... for item in thelist:
... if item==thelist[i]: continue
... del thelist[i+1:]
>>> alist = [6,3,3,3,5,7,6,3,4,4,3]
[6, 3, 5, 7, 6, 3, 4, 3]
More information about the Python-list