Какова цель сортированных наборов?

Question

Clojure имеет функцию sorted-set, которая создает объект PersistentTreeSet. Как следует из названия, sorted-set создает сортированную коллекцию уникальных объектов.

Когда сортируются наборы полезны? Когда лучше использовать sorted-set, чем sort и distinct?

=> (apply sorted-set [2 2 1 1 3 3]) 
#{1 2 3} 
=> (sort (distinct [2 2 1 1 3 3])) 
(1 2 3) 

Answer 1

Отсортированные наборы полезны, когда вам нужно набор семантику - быстрый contains?, conj и disj (= элемент абсорбция), как пояснялось Леоном - и обходов в хорошо определенном порядке. В случае встроенных отсортированных наборов (и карт) возможны упорядоченные обходы по всему набору (seq, rseq) и любой «поддиапазон» (subseq, rsubseq) между двумя ключами включительно или эксклюзивно.

Если вы хотите связаться со своими коллекциями, библиотека Contribute data.avl (из которых я являюсь автором и сопровождающим) предлагает аромат отсортированных наборов и карт с дополнительной функциональностью - nth для доступа к множеству элементы по рангу, rank-of для обнаружения ранга элемента в наборе, запросы ближайшего соседа и операции «поддиапазона» и разделения, которые возвращают полностью функциональные подмножества входной коллекции (думаю, subseq возвращает полностью функциональное подмножество оригинал, а не только seq, не удерживая ни одного элемента оригинала, отсутствующего в подмножестве для целей GC). Все они работают в наихудшем случае времени O (log n), как и стандартные операции сортированного набора.

Если вам нужны только contains? + conj + disj, вы, скорее всего, захотите использовать хеш-таблицы, так как они, как правило, обеспечивают лучшую производительность для этих операций. Стоит отметить, однако, что если вы откажетесь добавить входы с потенциально злонамеренного внешнего источника на свои наборы, вы можете пойти с отсортированными наборами, даже если вам не нужен порядок. Это связано с тем, что производительность хеш-наборов ухудшается до O (n) при наличии хеш-коллизий (которые противник мог бы заставить, используемая хэш-функция была детерминированной и фиксированной заранее), тогда как отсортированные наборы O (log n) являются твердый гарантия.

Если вам нужно отсортировать коллекцию входных данных один раз, а затем переправить его целиком или различные префиксы/суффиксы, повторите попытку, тогда создание сортированного вектора уникальных предметов действительно может быть лучшим вариантом.Сортированный набор может по-прежнему быть предпочтительным даже для рабочей нагрузки только для обхода, хотя, если вам нужна функция subseq/rsubseq, начинающаяся с произвольного элемента коллекции ((subseq a-set >= 5) = seq над этими элементами a-set, которые составляют = = 5 с учетом к заказу a-set).

Answer 2

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

Время, в течение которого я использовал бы сортировку и выделение, если бы у меня была какая-либо другая структура данных, такая как список, который я хочу заказать и удалить дубликаты.

В принципе, применение набора дает вам новый объект с уникальными элементами, в то время как отдельные действия действуют в одной и той же ссылке на список.

Answer 3

Разница между сортированным набором и результатом вызова sort и distinct заключается в том, что результирующий тип представляет собой набор.

Это дает O (журнал N) производительность (думаю, бинарный поиск), чтобы проверить, является ли элемент в коллекции (contains?) или добавить одну (conj), в то время как в списке, возвращаемой sort и distinct вы» d получить худшие характеристики для достижения такого же поведения по умолчанию.