Мне нужно представлять набор, и я начинаю работать с Data.Set. Я вижу, что делать нечего - singleton
, union
, intersection
и т.д. Все. Мне это нравится. Я могу выразить "что", а не "как". Но моему внутреннему программисту С очень неудобно. Есть много способов реализовать набор (двоичное дерево, хеш, логический массив и т.д.). Могу ли я действительно доверять Data.Set, чтобы выбрать лучший? Могу ли я каким-то образом его руководить или просто сдаюсь его (я признаю, возможно, превосходящему) суждение?
Data.Set: всегда ли это известно?
Ответ 1
Data.Set
не имеет внутреннего интеллекта (просто посмотрите источник!). Это просто сбалансированное дерево или упорядоченные элементы. Вы можете оглядываться на хакеры для многих других наборов и наборов с различными характеристиками производительности. Например, см. unordered-containers (HashSet), HashTables и bloomfilter.
Ответ 2
В общем Data.Set
используется сбалансированное двоичное дерево. Если у вас есть целые числа или битовые векторы, вам понадобится Data.IntSet
, который использует попытки Патрисии.
Обе версии были отточены через годы конкуренции, чтобы получить наилучшую производительность с Haskell.
Сдается Дороти!