短路排序

Question

我明白那个:

head (map (2**) [1..999999])

实际上只会评估2**1,而其余的都没有,但我正在阅读的书中说:

head (sort somelist)

只需要找到列表中最小的项目,因为这就是所有使用的项目.这是如何运作的？据我所知,使用我所知的排序算法(如冒泡排序)是不可能的.

我认为这样做的唯一方法是,如果排序算法要遍历整个列表,寻找最小的项目,然后在没有该项目的情况下递归列表.对我来说,这听起来很慢.

这是排序功能如何工作,还是有另一种我不知道的排序算法,可以像它一样短路？

Answer 1

这个:

只需要找到列表中最小的项目,因为这就是所有使用的项目.

...应该说该函数只需要进行排序算法查找最小元素所需的最少量工作.

例如,如果我们使用quicksort作为我们的基础排序算法,则head . quicksort相当于称为" quickselect " 的最佳(!)选择算法,这是最坏情况的线性.而且,我们只能通过实现k -quickselect .take k . quicksort

维基百科在其关于选择算法的文章中指出(我的重点):

由于对排序的语言支持更普遍,因此尽管在速度方面存在缺点,但在许多环境中,首选的简单方法是排序,然后进行索引.实际上,对于惰性语言,如果您的排序足够懒,这种简单的方法甚至可以为k最小/最大排序(最大/最小作为特殊情况)提供最佳复杂性.

Quicksort在这种情况下工作得很好,而Haskell中的默认排序(合并排序)也不是很好,因为它返回的工作量超过了返回排序列表的每个元素所需的工作量.正如Haskell邮件列表上的这篇文章所述:

懒惰的快速排序能够产生批量的前k个最小元素

O(n + k log k)总时间[1]

而懒惰的mergesort需要

O(n + k log n)总时间[2]

有关更多信息,您可以阅读此博文.

Answer 2

如果你创建一个跟踪其参数的比较函数,就像在GHCi的命令行中一样:

> :module + Data.List Debug.Trace
> let myCompare x y = trace ("\tCmp " ++ show x ++ " " ++ show y) $ compare x y

然后你可以自己看看这个行为:

> sortBy myCompare "foobar"

"     Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
a     Cmp 'b' 'r'
b     Cmp 'f' 'o'
      Cmp 'f' 'r'
f     Cmp 'o' 'o'
      Cmp 'o' 'r'
o     Cmp 'o' 'r'
or"

Haskell懒洋洋地评估字符串,一次一个字符.在找到每个字符时打印左侧列,右侧列记录所需的比较,由"跟踪"打印.

请注意,如果您编译它,特别是在启用优化时,您可能会得到不同的结果.优化器运行严格性分析器,可能会注意到整个字符串被打印出来,因此热切地评估它会更有效.

然后试试

> head $ sortBy myCompare "foobar"

      Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
'a'

如果您想了解其工作原理,请查看sort函数的源代码,并在纸上手动评估'sort"foobar"'.

qsort [] = []
qsort (x:xs) = qsort less ++ [x] ++ qsort greater
   where (less, greater) = partition (< x) xs

所以

   qsort ('f':"oobar")
 = qsort ('b':"a") ++ "f" ++ qsort ('o':"or")
 = ("a" ++ "b") ++ "f" ++ qsort ('o':"or")

现在我们已经做了足够的事情,发现'a'是结果中的第一项而不必评估对"qsort"的另一个调用.我省略了实际比较,因为它隐藏在对"分区"的调用中.实际上"分区"也是懒惰的,所以事实上其他"qsort"的论据并没有根据我的表现进行评估.