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

Question

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

Answer 1

Haskell的列表是作为链接列表实现的，这意味着访问任意i的元素在O(i)。在正常使用情况下，列表的二进制搜索版本elem需要比标准版本更多的时间（请参阅下面的@ DanielFischer的评论）。

您可能希望使用一个不同的容器，如Data.Set或Data.Map，即实现为平衡二叉树，这给给你O(log n)访问时间（其中n是在图/集合中元素的个数）。

Answer 2

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

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

Answer 3

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

改变数据结构，你的算法将是显而易见的（用布鲁克斯来解释）。

Haskell尤其如此，我们的数据结构通常不是以可变数组的形式出现的（也就是说，您不必依靠指针黑客行为）。

如果您使用例如一个堆或树来存储你的文本，你就可以实现简单的实现。你可以利用他们排序的事实来提供更快的插入。