php前缀树实现与assoc数组

Closed. This question is opinion-based。它当前不接受答案。












想要改善这个问题吗？更新问题，以便editing this post用事实和引用来回答。

4年前关闭。



Improve this question




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

这是一个简短的版本，没有代码。

我正在尝试从字典构建前缀树。因此，使用以下字典'and','anna','ape','apple'，图形应如下所示:

我尝试了2种方法:使用关联数组和使用自写的树/节点类。

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

问题:有什么好的(快速/高效)方法吗？

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

php关联数组(它们对于以后使用此图不是很灵活)。

自行编写的Tree/Node类(性能问题-执行时间最多增加7倍，即使不执行除inserting函数以外的任何操作，内存使用量也增加2倍)。

示例代码可在codereview上找到(有问题的第一个链接)

最佳答案

只要切换到C++并在codereview上得到一个很好的答案，我就在这里回答自己的问题。

还有一种方法可以通过增加内存使用率来提高时间效率(与“array s的array s的array……”相比，这并不是什么大的增加)。该方法称为“双数组特里”，您可以阅读有关此主题here的信息，并阅读有关codereview的上述答案，以查看实现示例。

它更省时，但为将来的Trie使用提供了较少的灵活性/便利性(与OOP方法相比)。

因此，对我来说，这个问题的最终答案是:“php并不是进行大量尝试的最佳工具”。