Массив Джуди для управляемых языков

StackOverflow https://stackoverflow.com/questions/550204

Вопрос

Массив Джуди — это быстрая структура данных, которая может представлять собой разреженный массив или набор значений.Существует ли его реализация для управляемых языков, таких как C#?Спасибо

Это было полезно?

Решение

Стоит отметить, что их часто называют «Judy Trees» или «Judy Tries», если вы ищете их в Google.

Я также искал реализацию .Net, но ничего не нашел.Также стоит отметить, что:

Реализация в значительной степени ориентирована на эффективное использование кэша, поскольку особенности такой реализации могут сильно зависеть от размера определенных конструкций, используемых в подструктурах.В этом отношении управляемая реализация .Net может несколько отличаться.

Я вижу на этом пути некоторые существенные препятствия (и, вероятно, есть еще несколько, которые я пропустил при кратком сканировании).

  • В API есть некоторые довольно анти-OO-аспекты (например, нулевой указатель рассматривается как пустое дерево), поэтому в упрощенном виде перемещение указателя состояния в LHS и преобразование методов экземпляра функций в C++ не будет работать.
  • Реализация подструктур, которые я рассмотрел, интенсивно использовала указатели.Я не вижу, чтобы они эффективно переводились в ссылки на управляемых языках.
  • Реализация представляет собой квинтэссенцию множества очень сложных идей, которые противоречат простоте общедоступного API.
  • База кода составляет около 20 тыс. строк (большинство из них сложны), и мне не кажется, что это простой порт.

Вы можете взять библиотеку и обернуть код C в C++/CLI (вероятно, просто удерживая внутри указатель, который является API-интерфейсом, и все вызовы c указывают на него).Это обеспечит упрощенную реализацию, но связанные библиотеки для собственной реализации могут быть проблематичными (как и распределение памяти).Вам также, вероятно, придется иметь дело с преобразованием строк .Net в простой старый байт * при переходе (или просто работать с байтами напрямую).

Другие советы

Джуди действительно не очень хорошо сочетается с управляемыми языками.Я не думаю, что вы сможете использовать что-то вроде SWIG и автоматически выполнить первый слой.

Я написал PyJudy, и в итоге мне пришлось внести некоторые нетривиальные изменения в API, чтобы он хорошо вписывался в Python.Например, я написал в документации:

Judyl Charrys Map Machine слова для машинных слов.На практике слова хранят без знака целых числа или указатели.Pyjudy поддерживает все четыре сопоставления в качестве отдельных классов.

  • pyjudy.judylintint - карта без знака INTEGER KEYS для беспигенных целочисленных значений
  • pyjudy.judylintobj - карта без знака целочисленных ключей к значениям объекта Python
  • pyjudy.judylobjint - Map Python Object Keys для не знаменитых целочисленных значений
  • pyjudy.judylobjobj - карта ключи объекта Python к значениям объекта Python

Я не просматривал код уже несколько лет, поэтому мои воспоминания о нем довольно смутны.Это была моя первая библиотека расширений Python, и я помню, что создал своего рода систему шаблонов для генерации кода.Сейчас я бы использовал что-то вроде генши.

Я не могу указать альтернативы Джуди — это одна из причин, по которой я ищу Stackoverflow.

Редактировать:Мне сказали, что мои значения времени в документации не соответствуют тем, что предлагает документация Джуди, потому что Джуди разработана для 64-битных строк кэша, а мой PowerBook был только 32-битным.

Некоторые другие ссылки:

Последний содержит сравнительные цифры для различных высокопроизводительных реализаций дерева.

Это оказывается сложнее, чем я думал. ПиДжуди возможно, стоит посмотреть, как и Галстук::Джуди.Есть что-то на Софтпедия, и что-то Рубиновый.Проблема в том, что ни один из них не относится конкретно к .NET.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top