Ordered Sets Python 2.7

Question

I have a list that I'm attempting to remove duplicate items from. I'm using python 2.7.1 so I can simply use the set() function. However, this reorders my list. Which for my particular case is unacceptable.

Below is a function I wrote; which does this. However I'm wondering if there's a better/faster way. Also any comments on it would be appreciated.

    def ordered_set(list_):

        newlist = []
        lastitem = None
        for item in list_:

            if item != lastitem:
                newlist.append(item)
                lastitem = item

        return newlist

The above function assumes that none of the items will be None, and that the items are in order (ie, ['a', 'a', 'a', 'b', 'b', 'c', 'd'])

The above function returns ['a', 'a', 'a', 'b', 'b', 'c', 'd'] as ['a', 'b', 'c', 'd'].

Answer 1

Another very fast method with set:

def remove_duplicates(lst):
    dset = set()
    # relies on the fact that dset.add() always returns None.
    return [item for item in lst
            if item not in dset and not dset.add(item)] 

Answer 2

Use an OrderedDict:

from collections import OrderedDict

l = ['a', 'a', 'a', 'b', 'b', 'c', 'd']
d = OrderedDict()

for x in l:
    d[x] = True

# prints a b c d
for x in d:
    print x,
print

Answer 3

Assuming the input sequence is unordered, here's O(N) solution (both in space and time). It produces a sequence with duplicates removed, while leaving unique items in the same relative order as they appeared in the input sequence.

>>> def remove_dups_stable(s):
...   seen = set()
...   for i in s:
...     if i not in seen:
...       yield i
...       seen.add(i)

>>> list(remove_dups_stable(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e']))
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']

Answer 4

I know this has already been answered, but here's a one-liner (plus import):

from collections import OrderedDict
def dedupe(_list):
    return OrderedDict((item,None) for item in _list).keys()

>>> dedupe(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e'])
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']

Answer 5

I think this is perfectly OK. You get O(n) performance which is the best you could hope for.

If the list were unordered, then you'd need a helper set to contain the items you've already visited, but in your case that's not necessary.

Answer 6

There is unique_everseen solution described in http://docs.python.org/2/library/itertools.html

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in ifilterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

Answer 7

if your list isn't sorted then your question doesn't make sense. e.g. [1,2,1] could become [1,2] or [2,1]

if your list is large you may want to write your result back into the same list using a SLICE to save on memory:

>>> x=['a', 'a', 'a', 'b', 'b', 'c', 'd']
>>> x[:]=[x[i] for i in range(len(x)) if i==0 or x[i]!=x[i-1]]
>>> x
['a', 'b', 'c', 'd']

for inline deleting see Remove items from a list while iterating or Remove items from a list while iterating without using extra memory in Python

one trick you can use is that if you know x is sorted, and you know x[i]=x[i+j] then you don't need to check anything between x[i] and x[i+j] (and if you don't need to delete these j values, you can just copy the values you want into a new list)

So while you can't beat n operations if everything in the set is unique i.e. len(set(x))=len(x) There is probably an algorithm that has n comparisons as its worst case but can have n/2 comparisons as its best case (or lower than n/2 as its best case if you know somehow know in advance that len(x)/len(set(x))>2 because of the data you've generated):

The optimal algorithm would probably use binary search to find maximum j for each minimum i in a divide and conquer type approach. Initial divisions would probably be of length len(x)/approximated(len(set(x))). Hopefully it could be carried out such that even if len(x)=len(set(x)) it still uses only n operations.

Answer 8

Looks ok to me. If you really want to use sets do something like this:

def ordered_set (_list) :
    result = set()
    lastitem = None
    for item in _list :
        if item != lastitem :
            result.add(item)
            lastitem = item
    return sorted(tuple(result))

I don't know what performance you will get, you should test it; probably the same because of method's overheat!

If you really are paranoid, just like me, read here:

http://wiki.python.org/moin/HowTo/Sorting/

http://wiki.python.org/moin/PythonSpeed/PerformanceTips

Just remembered this(it contains the answer):

http://www.peterbe.com/plog/uniqifiers-benchmark