Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Ordered Sets Python 2.7

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'].

like image 319
rectangletangle Avatar asked Jun 01 '11 07:06

rectangletangle


People also ask

Is there any ordered set in Python?

Python's Ordered Set ClassThe simplest way to create an ordered set in Python is to use the OrderedSet class. Note that this class is not included by default. You first need to make sure you have the ordered-set package installed. This will enable you to use the OrderedSet class.

Does Python list keep order?

You will use these extensively in your Python programming. One of the chief characteristics of a list is that it is ordered. The order of the elements in a list is an intrinsic property of that list and does not change, unless the list itself is modified.

Does Python set preserve insertion order?

Sets use a different algorithm that isn't as amendable to retaining insertion order. Set-to-set operations lose their flexibility and optimizations if order is required. Set mathematics are defined in terms of unordered sets. In short, set ordering isn't in the immediate future.


2 Answers

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.

like image 160
Tim Pietzcker Avatar answered Oct 20 '22 19:10

Tim Pietzcker


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']
like image 29
sunetos Avatar answered Oct 20 '22 20:10

sunetos