PHP前缀树实现与关联数组的比较

Question

更新：我已将原始问题转移到https://codereview.stackexchange.com/questions/127055/building-tree-graph-from-dictionary-performance-issues

以下是简短的版本，没有代码。

我试图从字典中构建前缀树。所以，使用以下字典'and'，'anna'，'ape'，'apple'，图应该看起来像这样： 我尝试了两种方法：使用关联数组和使用自编写的树/节点类。

注意：原始字典大约有8 MB，并包含> 600000个单词。

问题：有没有一种好（快/高效）的方法来完成这项工作？

到目前为止，我已经尝试过：

• php关联数组（它们对于将来在此图上的工作不太灵活）。

• 自编写的Tree / Node类（性能问题 - 执行时间最多增加7倍，即使没有实现除“插入”函数之外的任何内容，内存使用量也增加了2倍）。

示例代码可在codereview上找到（问题中的第一个链接）。

- haldagan

---

这个问题更适合于code review。 - nickb

@Sergiu Paraschiv - 我会调查一下。 - haldagan

@nickb，我并不是要求你审查我的代码，我基本上是在问“为什么基于类的树实现比基于数组的实现慢得多？”。这段代码是为了说明问题而给出的。我原本期望的速度下降大约是2倍左右。8倍以上的速度下降让我感到震惊。 - haldagan

@Matt 我明白你的意思，但我在将问题转移到codereview后立即修改了我的初始问题，所以它不再是一个重复的问题。简而言之，当前的问题是“有哪些已知的解决问题的方法？”而在codereview上的问题是“为什么我的解决方案如此缓慢？”（你可以查看codereview上的问题并看到其中的区别）。 - haldagan

@haldagan：啊，抱歉。但是以目前的形式，这个问题不适合在Stack Overflow上发布。“有没有好的（快速/高效）方法来做这件事”主要基于个人意见（好！？），并且太过宽泛（有很多种方法可以做到）。 - Matt

Answer 1

只要我已经转换到 C++ 并在 codereview 上得到了一个好的答案，我就在这里回答我的问题。有一种更加高效的方法可以通过增加内存使用量（与“array of arrays of arrays ...”方法相比，它的增加不是很大）。这种方法称为“双数组字典树”，您可以在here上阅读此主题的信息，并阅读 codereview 上的上述答案，以查看实现示例。它更加高效，但对于将来的 trie 使用而言，它允许的灵活性/方便性较少（与 OOP 方法相比）。所以对于我来说，对这个问题的最终答案是：“php 不是处理真正大型 tries 的最佳工具”。

- haldagan