ios - 如何有效地搜索有序列表？

Question

我有一个函数可以预测正在键入的单词并返回数组中的可能性。不幸的是，这些不是按使用频率排序的。所以我有一个 10K 有序单词的列表，按最频繁到最不频繁列出。比较数组中的单词和有序列表以返回出现频率最高的单词的有效方法是什么？ (即它首先遇到的那个？)

friend 建议我使用二叉搜索树，但我真的看不出这对我有什么帮助。据我了解 following website , 只能使用数值.. 我这样想是不是错了？有没有更好的方法来完成上述任务？

提前致谢

Answer 1

您可以创建一个字典，其中单词作为键，频率作为值。然后迭代你的结果数组，使用字典获取每个项目的频率值，并预测频率最高的项目。

我不会在这里使用普通的二叉搜索树。这是可能的——正如 Taylor Kirkpatrick 所说，您可以创建一个树，将单词作为键和频率，然后使用它来查找每个结果单词的频率，这与字典解决方案的方式大致相同。

问题是你不能保证一个简单的二叉树是平衡的。从它的声音来看，你的数据可能没问题，因为你的话是按频率顺序排列的。最坏的情况是，如果单词按字母顺序排列——那么你的二叉树最终将与链表相同——它永远不会分支，因为每个节点都会附加到前一个节点的右侧。因此，搜索的计算复杂度与遍历单词数组相同 - O(n) 而不是 O(log2N)(这是二叉树的最佳情况)。

当然，您可以通过在插入之前随机化单词列表来防止这种情况。但在我看来，使用字典更容易。我不知道 Swift 字典的实际实现是什么(我们不会知道，直到他们在几个月内将其开源)，但您可以理解为它将执行普通 BT 来进行值检索。

我不知道这个问题的背景是什么——如果你正在学习 CS，可能值得为了智力增长而实现 BST——在这种情况下，只有 10,000 个项目，你可能会发现性能差异最终相当大小的。但是，如果您是一名正在努力解决问题的程序员，请使用字典方法。