# Algorithm help per favore

Bengt Richter 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:

>Quoth Larry:
>> 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):
...     i=0
...     for item in thelist:
...         if item==thelist[i]: continue
...         i+=1
...         thelist[i]=item
...     del thelist[i+1:]
...
>>> alist = [6,3,3,3,5,7,6,3,4,4,3]
>>> listuniq(alist)
>>> alist
[6, 3, 5, 7, 6, 3, 4, 3]

Regards,
Bengt Richter

```