Я прочитал немного о следующих структурах данных:
- Бэгвелла идеальные попытки хэша
- Динамические хеш-таблицы Ларсона
- Красно-черные деревья
- Патриция деревья
... и я уверен, что есть много других. Я очень мало видел в том, для чего каждый из них лучше подходит, или почему я бы выбрал одно из другого. Итак, вот несколько вопросов по этим направлениям:
- Какие функциональные словарные структуры данных важно знать?
- Каковы плюсы и минусы этих подходов?
- Когда имеет смысл использовать более императивную структуру данных?
Числа 2 и 3 являются более важными, хотя. :-)
Ответы:
Я не могу ответить № 2, не потерявшись (слишком много измерений, по которым вы можете сравнить эти структуры), но для № 3 ответ довольно прост.
Используйте императивную структуру данных, если: (а) псевдонимы абсолютно отсутствуют или (б) вам действительно нужно использовать псевдонимы для эффективной трансляции.
Если в вашей структуре данных нет псевдонимов, вы не пользуетесь тем, что функциональные структуры данных являются постоянными. Так что нет причин платить за их стоимость. Есть два предостережения к этому совету. Во-первых, вы можете предпочесть простоту реализации функциональной структуры данных: реализация удаления для функционального красно-черного дерева заставит вас ругаться, но реализация удаления в императивном красно-черном дереве с родительскими указателями оставит вас в ожидании самоубийства. Во-вторых, назначение может быть более дорогим, чем вы ожидаете в gc'd языке, поскольку записи могут вывести структуры данных из молодого поколения. У нас действительно нет хорошей теории эффектов кеша и gc, поэтому у вас нет выбора, кроме как сделать бенчмаркинг.
Во-вторых, если вам нужен канал вещания, то общая структура данных - отличный способ сделать это. Благодаря постоянному обновлению вы можете произвольно сказать многим другим людям, что значение изменилось. (Вот почему union-find представляет собой такую замечательную структуру данных.) С чисто функциональной настройкой вам нужно либо изменить всех этих людей, либо дать им абстрактные указатели в состояние, которое вы кодируете вручную (что является своего рода тупым вещь которую нужно сделать).
Если вы не хотите рассуждать о псевдонимах и владении объектами или если вам нужно несколько версий одной и той же структуры данных (скажем, вам нужна как новая, так и старая версия), просто используйте функциональную структуру данных.
Самое трудное место, где я следую этому совету, - это графовые алгоритмы. Существует множество действительно элегантных алгоритмов императивных графов, но часто (например, при написании компиляторов) вам также требуется постоянство. Люди, как правило, пытаются разделить разницу и используют крутой императивный алгоритм, но стараются отбросить версии в сторону, чтобы получить постоянство. Это, как правило, довольно ужасно, полно ошибок и может потерять преимущество в производительности императивного алгоритма.
источник
Сбалансированные по высоте бинарные деревья и их попытки являются хорошим всесторонним компромиссом. Также:
Бинарные деревья с сбалансированной высотой и их попытки являются хорошим универсальным компромиссом для атомарных ключей. Попытки одинаковы для ключей, которые являются последовательностями, например строковые ключи.
Деревья Патриции могут быть в несколько раз быстрее, но разрешать только целочисленные ключи.
Попытки хеширования могут быть в несколько раз быстрее, чем сбалансированные двоичные деревья, особенно если хеширование дешевле, чем сравнение, и полиморфизм имеет накладные расходы (например, строки в .NET), а запись указателей в кучу выполняется быстро (например, виртуальные машины, такие как JVM и CLR, которые были оптимизирован для императивных языков, а не функциональных языков). Попытки хэширования также позволяют использовать мутацию для оптимизации.
Красно-черные деревья менее важны, потому что они не имеют каких-либо существенных преимуществ по сравнению с деревьями с сбалансированной высотой, но имеют существенный недостаток, заключающийся в том, что они не допускают эффективного объединения, пересечения и различия.
Точно так же пальчики не намного лучше на практике.
Когда ваш словарь заполняется один раз, а затем используется только для поиска, то есть заморожен.
Когда вам нужна производительность (приличная хеш-таблица, такая как .NET,
Dictionaryкак правило, в 10-40 раз быстрее любого обычного чисто функционального словаря).Когда нужен слабый словарь, потому что нет известного чисто функционального слабого словаря.
источник