管理语言的Judy数组

Question

Judy数组是快速数据结构,可以表示稀疏数组或一组值.是否有针对C#等托管语言的实现？谢谢

Answer 1

值得注意的是,如果你正在谷歌搜索它们,这些通常被称为Judy Trees或Judy Tries.

我也寻找.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支持所有四个映射作为不同的类.

• pyjudy.JudyLIntInt - 将无符号整数键映射到无符号整数值
• pyjudy.JudyLIntObj - 将无符号整数键映射到Python对象值
• pyjudy.JudyLObjInt - 将Python对象键映射到无符号整数值
• pyjudy.JudyLObjObj - 将Python对象键映射到Python对象值

几年来我没有看过代码,所以我对它的记忆非常朦胧.这是我的第一个Python扩展库,我记得我将一种用于代码生成的模板系统整合在一起.现在我会用像genshi这样的东西.

我不能指出Judy的替代品 - 这就是我搜索Stackoverflow的原因之一.

编辑:我被告知我的文档中的时序编号与Judy的文档建议不同,因为Judy是为64位缓存行开发的,而我的PowerBook只有32位.

其他一些链接:

• Patricia尝试(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实现的比较数字.