托管语言的 Judy 数组

Question

朱迪阵列 是快速数据结构，可以表示稀疏数组或一组值。是否有针对 C# 等托管语言的实现？谢谢

Answer 1

值得注意的是，如果您在谷歌上搜索它们，它们通常被称为“朱迪树”或“朱迪尝试”。

我还寻找了 .Net 实现，但一无所获。另外值得注意的是：

该实现是围绕高效缓存使用而大量设计的，因为此类实现细节可能高度依赖于子结构内使用的某些构造的大小。.Net 管理的实现在这方面可能有所不同。

我可以看到一些重大障碍（而且我的简短扫描可能遗漏了更多障碍）

• 该 API 有一些相当反 OO 的方面（例如，空指针被视为空树），因此过于简单化，将状态指针移至 LHS 并将函数实例方法转换为 C++ 是行不通的。
• 我研究的子结构的实现大量使用了指针。我无法看到这些内容被有效地转换为托管语言的引用。
• 该实现是许多非常复杂的想法的升华，掩盖了公共 API 的简单性。
• 代码库大约有 20K 行（其中大部分都很复杂），这对我来说并不是一个简单的移植。

您可以使用该库并将 C 代码包装在 C++/CLI 中（可能只是在内部保存一个指针，即 c api trie，并使所有 c 调用都指向该指针）。这将提供一个简单的实现，但本机实现的链接库可能有问题（内存分配也可能存在问题）。您可能还需要在转换时将 .Net 字符串转换为普通的旧字节*（或者直接使用字节）

Answer 2

Judy 确实不太适合托管语言。我认为您无法使用 SWIG 之类的东西来自动完成第一层。

我编写了 PyJudy，最终不得不进行一些重要的 API 更改才能很好地适应 Python。例如我在文档中写道：

JudyL 数组将机器字映射到 机器词。在实践中，这些话 存储无符号整数或指针。PyJudy 支持所有四种映射 不同的类。

• 皮朱迪。JudyLIntInt - 地图无符号 无符号整数的整数键 值
• 皮朱迪。JudyLIntObj - 地图无符号 Python 对象值的整数键
• 皮朱迪。JudyLObjInt - 地图Python 无符号整数的对象键 值
• pyjudy.judylobjobj-地图python对象键到python对象值

我已经好几年没有看过代码了，所以我对它的记忆非常模糊。这是我的第一个 Python 扩展库，我记得我编写了一种用于代码生成的模板系统。现在我会使用像 genshi 这样的东西。

我无法指出 Judy 的替代品 - 这就是我搜索 Stackoverflow 的原因之一。

编辑：有人告诉我，文档中的计时数字与 Judy 的文档建议的不符，因为 Judy 是为 64 位缓存线开发的，而我的 PowerBook 只有 32 位。

其他一些链接：

• 帕特里夏尝试（http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/ )
• 双数组尝试 (http://linux.thai.net/~thep/datrie/datrie.html)
• HAT-trie (http://members.optusnet.com.au/~askitisn/index.html)

最后一个是不同高性能 trie 实现的比较数字。

Answer 3

这被证明比我想棘手。 PyJudy 可能是值得一试，因为会的铁::朱迪。有什么东西在 Softpedia 和东西的红宝石肥胖型。麻烦的是，这些都不是专门.NET。