澄清懒惰评估及其效率 [英] Clarification on Lazy Evaluation and its efficiency

问题描述

我在真实世界的Haskell上碰到了以下句子:

I came across following sentence on Real World Haskell:

懒惰的评估有一些怪异的效果.假设我们要找到 未排序列表的k个最小值元素.在传统 语言，最明显的方法是对列表进行排序并采用 前k个元素，但这很昂贵.为了提高效率，我们会 而是编写一个特殊函数来一次性获取这些值， 并且它必须执行一些中等复杂的簿记工作.在 Haskell，然后采取方法实际上表现良好:懒惰 确保列表仅排序到足以找到k个最小值 元素.

Lazy evaluation has some spooky effects. Let's say we want to find the k least-valued elements of an unsorted list. In a traditional language, the obvious approach would be to sort the list and take the first k elements, but this is expensive. For efficiency, we would instead write a special function that takes these values in one pass, and it would have to perform some moderately complex book-keeping. In Haskell, the sort-then-take approach actually performs well: laziness ensures that the list will only be sorted enough to find the k minimal elements.

为此，他们给出了代码隐含的含义:

And they give an code implemntation for that:

minima k xs = take k (sort xs)

是这样吗?我认为，即使在Haskell中，它也应该列出完整的列表以取出k元素. (想象一下，列表末尾的数字最小).我在这里想念什么吗?

But is that so ? I think even in Haskell it should do a full sort of the list to take out the k elements. ( Imagine having the smallest number at the end of the list ). Am I missing something here ?

推荐答案

(只需在此处回答我的意见)遍历整个列表并不等同于对其进行排序.假定执行quicksort，在该列表中您围绕枢轴对列表进行分区，然后以递归方式对列表的左半部分和右半部分进行排序.如果仅在左半部分要求元素，则无需对右半部分进行排序.此参数可以递归应用.因此，如果要在排序后从n长度列表中获取k元素，则复杂度为O(n + klog k)而不是O(n log n).正如@MoFu所指出的，Heinrich在此处上有一篇不错的博客文章.

(Just putting my comment to answer here) Traversing the whole list is not equivalent to sorting it. Assume doing quicksort where you partition the list around the pivot and then recursively sort left and right half of the list. If you are asking just for elements on the left half then there is no need to sort the right half. This argument can be applied recursively. Thus if you are taking k elements from n length list after sorting, the complexity is O(n + klog k) and not O(n log n). As pointed by @MoFu, Heinrich has a good blog post here.

这篇关于澄清懒惰评估及其效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！