Есть ли у Python упорядоченный набор?

Question

Python имеет упорядоченный словарь . А как насчет заказанного набора?

Answer 1

Существует рецепт упорядоченного набора (возможно новая ссылка ) для этого, который упоминается в документации Python 2 Это работает на Py2.6 или позже и 3.0 или позже без каких-либо изменений. Интерфейс почти такой же, как обычный набор, за исключением того, что инициализация должна быть сделана со списком.

OrderedSet([1, 2, 3])

Это MutableSet, поэтому подпись для .union не совпадает с сигнатурой набора, но, поскольку она включает __or__, можно легко добавить нечто подобное:

@staticmethod
def union(*sets):
    union = OrderedSet()
    union.union(*sets)
    return union

def union(self, *sets):
    for set in sets:
        self |= set

Answer 2

Упорядоченный набор является функционально частным случаем упорядоченного словаря.

Ключи словаря являются уникальными. Таким образом, если кто-то игнорирует значения в упорядоченном словаре (например, присваивая им None), то он, по сути, имеет упорядоченный набор.

Начиная с Python 3.1 существует collections.OrderedDict. Ниже приведен пример реализации OrderedSet. (Обратите внимание, что только несколько методов нужно определить или переопределить: collections.OrderedDict и collections.MutableSet выполняют тяжелую работу.)

import collections

class OrderedSet(collections.OrderedDict, collections.MutableSet):

    def update(self, *args, **kwargs):
        if kwargs:
            raise TypeError("update() takes no keyword arguments")

        for s in args:
            for e in s:
                 self.add(e)

    def add(self, elem):
        self[elem] = None

    def discard(self, elem):
        self.pop(elem, None)

    def __le__(self, other):
        return all(e in other for e in self)

    def __lt__(self, other):
        return self <= other and self != other

    def __ge__(self, other):
        return all(e in self for e in other)

    def __gt__(self, other):
        return self >= other and self != other

    def __repr__(self):
        return 'OrderedSet([%s])' % (', '.join(map(repr, self.keys())))

    def __str__(self):
        return '{%s}' % (', '.join(map(repr, self.keys())))

    difference = property(lambda self: self.__sub__)
    difference_update = property(lambda self: self.__isub__)
    intersection = property(lambda self: self.__and__)
    intersection_update = property(lambda self: self.__iand__)
    issubset = property(lambda self: self.__le__)
    issuperset = property(lambda self: self.__ge__)
    symmetric_difference = property(lambda self: self.__xor__)
    symmetric_difference_update = property(lambda self: self.__ixor__)
    union = property(lambda self: self.__or__)

Answer 3

Я могу сделать вас лучше, чем OrderedSet: boltons имеет чистый Python, 2/3-совместимый IndexedSet тип , который не только упорядоченный набор, но также поддерживает индексирование (как в случае с списки).

Просто pip install boltons (или скопируйте setutils.py в свою кодовую базу), импортируйте IndexedSet и:

>>> from boltons.setutils import IndexedSet
>>> x = IndexedSet(list(range(4)) + list(range(8)))
>>> x
IndexedSet([0, 1, 2, 3, 4, 5, 6, 7])
>>> x - set(range(2))
IndexedSet([2, 3, 4, 5, 6, 7])
>>> x[-1]
7
>>> fcr = IndexedSet('freecreditreport.com')
>>> ''.join(fcr[:fcr.index('.')])
'frecditpo'

Все уникально и сохранено в порядке. Полное раскрытие: я написал IndexedSet, но это также означает, что , вы можете вызвать меня, если возникнут какие-либо проблемы . :)

Answer 4

Реализации на PyPI

Хотя другие отмечают, что в Python нет встроенной реализации набора сохранения порядка вставки (пока), я чувствую, что в этом вопросе отсутствует ответ, в котором указано, что можно найти в PyPI .

Насколько мне известно, в настоящее время есть:

• упорядоченный-набор
• OSET

Обе реализации основаны на рецепте , опубликованном Раймондом Хеттингером в ActiveState , который также упоминается в других ответах здесь. Я проверил оба и опознал следующее

критические различия:

• заказанный набор (версия 1.1)
  • преимущество: O (1) для поиска по индексу (например, my_set[5])
  • недостаток: remove(item) не реализовано
• oset (версия 0.1.3)
  • преимущество: O (1) для remove(item)
  • недостаток: по-видимому, O (n) для поиска по индексу

Обе реализации имеют O (1) для add(item) и __contains__(item) (item in my_set).

К сожалению, ни одна из реализаций не имеет операций с множествами на основе методов, таких как set1.union(set2) -> Вместо этого вы должны использовать форму на основе операторов, такую ​​как set1 | set2. См. документацию Python по объектам Set для полного списка методов операций над множествами и их эквивалентов на основе операторов.

Сначала я использовал заказанный набор, пока не использовал remove(item) в первый раз, когда мой сценарий разбился с NotImplementedError. Поскольку я никогда не использовал поиск по индексу, я тем временем переключился на oset.

Если вы знаете о других реализациях PyPI, дайте мне знать в комментариях.

Answer 5

Ответ - нет, но вы можете использовать collections.OrderedDict из стандартной библиотеки Python, используя только ключи (и значения как None) для той же цели.

Обновление : Начиная с Python 3.7 (и CPython 3.6), стандарт dict равен , гарантированно сохраняет порядок и более производительный, чем OrderedDict. (Однако для переносимости и читабельности вы можете продолжить использовать OrderedDict.)

Вот пример того, как использовать dict в качестве упорядоченного набора для фильтрации дублирующихся элементов при сохранении порядка, тем самым эмулируя упорядоченный набор. Используйте dict метод класса fromkeys(), чтобы создать диктовку, затем просто попросите keys() back.

>>> keywords = ['foo', 'bar', 'bar', 'foo', 'baz', 'foo']

>>> list(dict.fromkeys(keywords).keys())
['foo', 'bar', 'baz']

Answer 6

Если вы используете упорядоченный набор для поддержания отсортированного порядка, рассмотрите возможность использования реализации отсортированного набора из PyPI. Модуль sortedcontainers предоставляет SortedSet именно для этой цели. Некоторые преимущества: чистый Python, реализация fast-as-C, 100% охват модульных тестов, часы стресс-тестирования.

Установка из PyPI легко с pip:

pip install sortedcontainers

Обратите внимание, что если вы не можете pip install, просто извлеките файлы sortedlist.py и sortedset.py из репозитория с открытым исходным кодом .

После установки вы можете просто:

from sortedcontainers import SortedSet
help(SortedSet)

Модуль sortedcontainers также поддерживает сравнение производительности с несколькими альтернативными реализациями.

Для комментария, в котором спрашивается о типе данных пакета Python, существует альтернативный тип данных SortedList , который можно использовать для эффективной реализации пакета.

Answer 7

Если вы уже используете панды в своем коде, его объект Index ведет себя почти как упорядоченный набор, как показано в этой статье .

Answer 8

В официальной библиотеке нет OrderedSet. Я делаю исчерпывающую таблицу всех структур данных для вашей справки.

DataStructure = {
    'Collections': {
        'Map': [
            ('dict', 'OrderDict', 'defaultdict'),
            ('chainmap', 'types.MappingProxyType')
        ],
        'Set': [('set', 'frozenset'), {'multiset': 'collection.Counter'}]
    },
    'Sequence': {
        'Basic': ['list', 'tuple', 'iterator']
    },
    'Algorithm': {
        'Priority': ['heapq', 'queue.PriorityQueue'],
        'Queue': ['queue.Queue', 'multiprocessing.Queue'],
        'Stack': ['collection.deque', 'queue.LifeQueue']
        },
    'text_sequence': ['str', 'byte', 'bytearray']
}

Answer 9

Немного опоздал к игре, но я написал класс setlist как часть collections-extended, который полностью реализует Sequence и Set

>>> from collections_extended import setlist
>>> sl = setlist('abracadabra')
>>> sl
setlist(('a', 'b', 'r', 'c', 'd'))
>>> sl[3]
'c'
>>> sl[-1]
'd'
>>> 'r' in sl  # testing for inclusion is fast
True
>>> sl.index('d')  # so is finding the index of an element
4
>>> sl.insert(1, 'd')  # inserting an element already in raises a ValueError
ValueError
>>> sl.index('d')
4

GitHub: https://github.com/mlenzen/collections-extended

Документация: http://collections -extended.lenzm.net / ru / latest /

PyPI: https://pypi.python.org/pypi/collections-extended

Answer 10

Для многих целей достаточно просто отсортировать вызовы. Например

>>> s = set([0, 1, 2, 99, 4, 40, 3, 20, 24, 100, 60])
>>> sorted(s)
[0, 1, 2, 3, 4, 20, 24, 40, 60, 99, 100]

Если вы собираетесь использовать это несколько раз, при вызове отсортированной функции возникнут дополнительные затраты, поэтому вы можете захотеть сохранить результирующий список, пока вы закончите изменять набор. Если вам нужно сохранить уникальные элементы и отсортировать их, я согласен с предложением использовать OrderedDict из коллекций с произвольным значением, например None.