haskell - 在 Haskell 中使用二进制搜索更快的 `elem`

Question

我有一个Texts 列表，它们按排序顺序排列。elem在我看来，我可以通过将其实现为二进制搜索而不是线性搜索来编写更快的版本。这样的版本是否已经存在？

Answer 1

Haskell 的列表被实现为链表，这意味着对任意i-th 元素的访问位于O(i). 在正常使用中，for 列表的二进制搜索版本elem会比标准版本花费更多时间（请参阅下面的 @DanielFischer 的评论）。

您可能希望使用不同的容器，例如Data.Set或Data.Map，它们被实现为平衡二叉树，从而为您提供O(log n)访问时间（其中n是映射/集合中的元素数量）。

Answer 2

二进制搜索需要随机访问。由于 haskell 列表不提供随机访问（访问中间的元素需要线性时间），所以二分查找没有帮助。

如果您的数据位于Array提供随机访问的 中，则二进制搜索将是可行的。

Answer 3

我有一个文本列表，它们按排序顺序排列。

改变数据结构，你的算法就会很明显（用布鲁克斯的话说）。

Haskell 尤其如此，我们的数据结构通常不是可变数组（这意味着您不会依赖指针黑客攻击）。

如果您使用例如堆或树来存储文本，您将能够轻松实现O(log(n)) elem。您可以利用它们已排序的事实来提供更快的插入。