Algorithm help per favore

[Bengt Richter]

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