相关疑难解决方法(0)

我有一个用Python和Haskell编写的简单脚本.它读取一个包含1,000,000个换行符分隔整数的文件,将该文件解析为整数列表,对其进行快速排序,然后将其写入已排序的其他文件.此文件的格式与未排序的文件相同.简单.

这是Haskell:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

main = do
    file <- readFile "data"
    let un = lines file
    let f = map (\x -> read x::Int ) un
    let done = quicksort f
    writeFile "sorted" (unlines (map show done))

这是Python:

def qs(ar):
    if len(ar) == 0:
        return ar

    p …

我对Haskell很新,我对使用不纯(可变)数据结构可以提高性能有疑问.我正在尝试拼凑一些我听过的不同的东西,所以如果我的术语不完全正确,或者如果有一些小错误,请耐心等待.

为了具体化,请考虑快速排序算法(取自Haskell wiki).

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

这不是"真正的快速入门"."真正的"快速排序算法就位,但事实并非如此.这是非常低效的内存.

另一方面,可以在Haskell中使用向量来实现就地快速排序.这个stackoverflow答案给出了一个例子.

第二种算法比第一种算法快多少？Big O符号在这里没有用,因为性能的提高将来自更有效地使用内存,而不是更好的算法(对吧？).我厌倦了自己构建一些测试用例,但是我很难让事情运行起来.

理想的答案可以让我们了解在理论上使原位Haskell算法更快的原因,以及某些测试数据集上运行时间的示例比较.

我无法理解这段代码:

let
  sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]

有人可以为我分手吗？我知道它有递归,但这就是问题我无法理解这个例子中的递归是如何工作的.

有人可以提供就地快速排序haskell功能吗？即它返回一个新的排序列表,但输入列表被复制到一个可变数组或其他东西.

我想看看如何做到这一点,因为我有一个性能关键程序,我需要模拟比赛和计数得分.如果我为此使用不可变数据结构,则每个种族将采用O(log(numRaces)+ numRunners)时间,而如果我使用可变数组等,则每个种族将采用O(log(numRaces))时间.

哦顺便说一句我实际上并不需要做快速排序,我只是想要一个例子来看看如何有效地使用可变数组

我有这个看似琐碎的并行快速实现,代码如下:

import System.Random
import Control.Parallel
import Data.List

quicksort :: Ord a => [a] -> [a]
quicksort xs = pQuicksort 16 xs -- 16 is the number of sparks used to sort

-- pQuicksort, parallelQuicksort  
-- As long as n > 0 evaluates the lower and upper part of the list in parallel,
-- when we have recursed deep enough, n==0, this turns into a serial quicksort.
pQuicksort :: Ord a => Int -> [a] -> [a]
pQuicksort _ [] = …

正如他们所说,"真正的快速排序就地排序".所以标准的短Haskell代码用于quicksort,

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
  where
    lesser  = filter (< p) xs
    greater = filter (>= p) xs

毕竟,它描述的算法/计算过程是什么？

肯定不是Tony Hoare设计的,缺乏最明确的功能,就地分区算法.

(答案可能是众所周知的,但在SO上还没有).

纠正:这个问题实际上是重复的:毕竟在SO 上已知答案:cf.伪快速排序时间复杂度.

我试图理解 APL 中的经典快速排序：

Q\xe2\x86\x90{1\xe2\x89\xa5\xe2\x89\xa2\xe2\x8d\xb5:\xe2\x8d\xb5 \xe2\x8b\x84 S\xe2\x86\x90{\xe2\x8d\xba\xe2\x8c\xbf\xe2\x8d\xa8\xe2\x8d\xba \xe2\x8d\xba\xe2\x8d\xba \xe2\x8d\xb5} \xe2\x8b\x84 \xe2\x8d\xb5((\xe2\x88\x87<S)\xe2\x8d\xaa=S\xe2\x8d\xaa(\xe2\x88\x87>S))\xe2\x8d\xb5\xe2\x8c\xb7\xe2\x8d\xa8?\xe2\x89\xa2\xe2\x8d\xb5}\n

有些事情我不明白，有些风格选择困扰我，所以我要把它们全部列出来。我希望有人可以向我解释它们。

\n
1. 我知道在{ }defn 中，\xe2\x8d\xba是左参数，\xe2\x8d\xb5是右参数。\xe2\x8d\xba\xe2\x8d\xba里面是什么 S\xe2\x86\x90{\xe2\x8d\xba\xe2\x8c\xbf\xe2\x8d\xa8\xe2\x8d\xba \xe2\x8d\xba\xe2\x8d\xba \xe2\x8d\xb5}？同样，有一个\xe2\x8d\xb5\xe2\x8d\xb5? \xe2\x8d\xba里面的是S指 的左参数S还是 的左参数Q？
\n

我的猜测是，\xe2\x8d\xba里面的S指的是 的左边参数S。the\xe2\x8d\xba\xe2\x8d\xba指的是封闭函数\xe2\x8d\xba的 的（即Q 的 ）。\xe2\x8d\xba

Q\xe2\x86\x90{1\xe2\x89\xa5\xe2\x89\xa2\xe2\x8d\xb5:\xe2\x8d\xb5 \xe2\x8b\x84 S\xe2\x86\x90{(\xe2\x8d\xba \xe2\x8d\xba\xe2\x8d\xba \xe2\x8d\xb5)\xe2\x8c\xbf\xe2\x8d\xba} \xe2\x8b\x84 \xe2\x8d\xb5((\xe2\x88\x87<S)\xe2\x8d\xaa=S\xe2\x8d\xaa(\xe2\x88\x87>S))\xe2\x8d\xb5[?\xe2\x89\xa2\xe2\x8d\xb5]}\n