Merging ordered lists

[etal]

On Jun 3, 1:22 am, Peter Otten <__pete... at web.de> wrote:
>
> Yes :)
>
> Seriously, you are using O(n) containers and O(n) lookup where mine uses
> O(1). For short lists it doesn't matter, but as the list length grows the
> difference gets huge:
>
> $ cat unique.py
> def unique(items):
>     u = set(items)
>     if len(u) == len(items):
>         return items
>     result = []
>     for item in items:
>         if item in u:
>             result.append(item)
>             u.remove(item)
>     return result
>

Yikes... and the list comprehension looked so innocent. I had resigned
myself to O(n) lookup, but you and Raymond appear to agree on the
basic concept for unique() -- check set membership, then generate the
final sequence and update the set based on that.