11

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

4

3 回答 3

16

值得注意的是，如果您在谷歌上搜索它们，它们通常被称为 Judy Trees 或 Judy Tries。

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

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

我可以看到一些重大障碍（我的简短扫描可能错过了更多）

  • API 有一些相当反面向对象的方面（例如，空指针被视为空树），因此过于简单，将状态指针移动到 LHS 并使函数实例方法转换为 C++ 不起作用。
  • 我看到的子结构的实现大量使用了指针。我看不到这些被有效地翻译成托管语言的引用。
  • 实现是许多非常复杂的想法的提炼，这些想法掩盖了公共 api 的简单性。
  • 代码库大约有 20K 行（其中大部分很复杂），这对我来说并不是一个简单的移植。

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

于 2009-02-16T15:12:05.730 回答
12

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 位。

其他一些链接：

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

于 2009-02-18T18:37:11.430 回答
2

事实证明这比我想象的要棘手。PyJudy和Tie::Judy可能值得一看。Softpedia上有一些东西，还有一些Ruby-ish的东西。麻烦的是，这些都不是专门的.NET。

于 2009-02-15T07:23:01.980 回答