Есть ли у 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

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

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

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

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys(keywords).keys())
['foo', 'bar', 'baz']

Answer 3

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

Ключи словаря являются уникальными. Таким образом, если игнорировать значения в упорядоченном словаре (например, назначая их 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 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

Я могу сделать вас лучше, чем 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 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

Как упоминается в других ответах, что касается python 3.7+, dict упорядочивается по определению. Вместо подклассаOrderedDict мы можем создать подкласс abc.collections.MutableSet или typing.MutableSet используя ключи dict для хранения наших значений.

class OrderedSet(typing.MutableSet[T]):
    """A set that preserves insertion order by internally using a dict."""

    def __init__(self, iterable: t.Iterator[T]):
        self._d = dict.fromkeys(iterable)

    def add(self, x: T) -> None:
        self._d[x] = None

    def discard(self, x: T) -> None:
        self._d.pop(x)

    def __contains__(self, x: object) -> bool:
        return self._d.__contains__(x)

    def __len__(self) -> int:
        return self._d.__len__()

    def __iter__(self) -> t.Iterator[T]:
        return self._d.__iter__()

Тогда просто:

x = OrderedSet([1, 2, -1, "bar"])
x.add(0)
assert list(x) == [1, 2, -1, "bar", 0]

Я поместил этот код в небольшую библиотеку, чтобы каждый мог простоpip install Это.

Answer 8

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

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/en/latest/

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

Answer 10

Нет никаких 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 11

Как говорили другие, OrderedDictявляется расширенным набором упорядоченного набора с точки зрения функциональности, но если вам нужен набор для взаимодействия с API и не нужно, чтобы он был изменяемым,OrderedDict.keys() на самом деле реализация abc.collections.Set:

import random
from collections import OrderedDict, abc

a = list(range(0, 100))
random.shuffle(a)

# True
a == list(OrderedDict((i, 0) for i in a).keys())

# True
isinstance(OrderedDict().keys(), abc.Set)   

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

Answer 12

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

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

Answer 13

Пакет ParallelRegression предоставляет класс упорядоченного набора setList(), который является более полным методом, чем параметры, основанные на рецепте ActiveState. Он поддерживает все методы, доступные для списков, и большинство, если не все, методы, доступные для множеств.

Answer 14

Примечание: расширение ответа jrc, поскольку в этот ответ не включено использование OrderDict.

Хорошее объяснение с подходящим примером, объясненным в

У нас есть два способа для этого - (1) collections.OrderedDict и (2) dict

Первый используется для python до 3.7, а затем используется для python 3.7 и выше.

Создайте упорядоченный набор в python 3.7 и выше, как показано ниже —

      keywords = ['hello', 'aurav', 'hello', 'narendra', 'foo', 'foo']
sampleList = list(dict.fromkeys(keywords))

print(type(sampleList))

for item in sampleList:
    print(item)

Когда вышеуказанная программа запускается, вывод -

      <class 'list'>
hello
aurav
narendra
foo

Ознакомьтесь с тем , как Create OrderedSet в Python 3.7 и ранее.создать OrderedSet с помощью OrderDict из коллекций.

Answer 15

Существует библиотека pip , которая делает это:

      pip install ordered-set

Затем вы можете использовать его:

      from ordered_set import OrderedSet

Answer 16

Просто используйтеpd.uniqueотpandas- делает именно то, что вам нужно!

      >>> import pandas as pd
>>> pd.unique([3, 1, 4, 5, 2, 2])
array([3, 1, 4, 5, 2])

Answer 17

Таким образом, у меня также был небольшой список, в котором у меня была возможность ввести неуникальные значения.

Я искал наличие какого-то уникального списка, но потом понял, что тестирование существования элемента перед его добавлением работает просто отлично.

if(not new_element in my_list):
    my_list.append(new_element)

Я не знаю, есть ли предостережения к этому простому подходу, но он решает мою проблему.

Answer 18

Я верю, что есть четыре вида заказов:

1. Заказано по ключу
2. Упорядочено по значению (хотя я не слышал, чтобы кто-нибудь просил об этом)
3. Упорядочено по времени модификации
4. Заказ по времени сложения

Я считаю, что collection.OrderedDict получает вас #4. Или вы можете удалить ключ и повторно добавить его, для #3.

Для #1 вы, вероятно, должны проверить красно-черное дерево или трепу:

• http://pypi.python.org/pypi/bintrees/0.3.0
• http://pypi.python.org/pypi/rbtree/
• http://stromberg.dnsalias.org/~dstromberg/treap/

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

Обе они являются установленными структурами данных с реализациями на многих языках.

Answer 19

>>> a = {3, 4, 2, 6, 1, 7}
>>> type(a)
<class 'set'>
>>> sorted(a, reverse=True)
[7, 6, 4, 3, 2, 1]
>>> sorted(a)
[1, 2, 3, 4, 6, 7]