澄清懶惰評估其效率

Question

我碰到下面的句子來到真實世界哈斯克爾：

懶惰的評價有一些怪異的效果。假設我們想查找未排序列表的k個最小值元素。在傳統的 語言中，顯而易見的方法是對列表進行排序並採用第一個k元素，但這很昂貴。爲了提高效率，我們將 改爲編寫一個特殊函數，該函數一次性讀取這些值，即 ，並且它必須執行一些適度複雜的簿記。在 Haskell中，sort-then-take方法實際上表現良好：懶惰 確保列表僅被排序到足以找到k個最小元素 。

，他們給的，一個代碼implemntation：

minima k xs = take k (sort xs) 

但就是這樣的嗎？我認爲，即使在Haskell中，它也應該完整地列出k元素。 （想象一下列表末尾的數字最小）。我在這裏錯過了什麼嗎？

Answer 1

（只是把我的評論回答在這裏）遍歷整個列表不等同於對它進行排序。假設在圍繞數據透視表對列表進行分區的情況下執行快速排序，然後遞歸排序列表的左半部分和右半部分。如果你只是要求左半部分的元素，那麼就不需要對右半部分進行排序。這個參數可以遞歸地應用。因此，如果您在排序後從n長度列表中選取k元素，則複雜度爲O(n + klog k)，而不是O(n log n)。正如@MoFu所指出的，海因裏希有一篇很好的博文here。