Структура данных, подобная frozenset, которая поддерживает порядок вставки?

#python #set #immutability #standard-library

#python #установить #неизменность #стандартная библиотека

Вопрос:

Мне нужна структура данных, подобная набору, с этими свойствами:

хэшируемый
нет повторяющихся элементов
поддерживает порядок
неизменяемый
итеративный
часть стандартной библиотеки? хотите, чтобы это было просто

Что происходит:

 frozenset([3,1,2,2,3]) -> frozenset(1,2,3)

Что мне нужно:

 frozenset*([3,1,2,2,3]) -> frozenset*(3,1,2)

Я думал, что смогу использовать frozenset, но как наборы, так и frozensets
переупорядочивают элементы. Я предполагаю, что это для более быстрой проверки дубликатов?
Но в любом случае я не могу изменить порядок.

1. В стандартной библиотеке такой структуры данных нет.

2. Возможно, просто используйте кортежи и убедитесь, что у них нет повторяющихся элементов во время создания.

3. «оба набора и frozensets сортируют элементы» нет, они этого не делают. Обе эти структуры данных не имеют внутреннего порядка . Все, что вы видите, является деталью реализации в этом случае, большинство — но не все — целые числа просто хэшируются сами по себе, отсюда и очевидная сортировка

4. В любом случае, какие конкретные аспекты объектов set вам требуются? Является ли быстрый поиск важной частью? это основной вариант использования набора. Похоже, вы заботитесь только о том, чтобы не было дубликатов…

5. Например, на Python 3.7 вы могли бы просто использовать кортежи и использовать функцию для обеспечения отсутствия дубликатов и поддержания порядка (как уже упоминалось), поэтому просто: def no_dupe(data): return tuple(dict.fromkeys(data))

Ответ №1:

Начиная с Python 3.7, dicts больше не переупорядочивает элементы и вместо этого гарантирует сохранение порядка вставки. Вы могли бы использовать dict, где ключами являются ваши элементы набора, а значения игнорируются.

 >>> dict.fromkeys([3,1,2,2,3])
{3: None, 1: None, 2: None}

Dicts не замораживаются, поэтому, если это важно, вы можете сначала поместить все элементы в dict, а затем создать кортеж из ключей.

 >>> tuple(dict.fromkeys([3,1,2,2,3]).keys())
(3, 1, 2)

Это было бы довольно близко к a frozenset . Основное отличие заключается в том, что для проверки наличия элемента в кортеже потребуется O (n), а не O (1) время.

1. Нет необходимости вызывать .keys

2. Верно, это необязательно. Я предпочитаю быть здесь явным. (Я не поклонник того, как итерация по словарю повторяется по его ключам. Одна из редких ошибок Python.)

Ответ №2:

В стандартной библиотеке такой реализации нет