相关疑难解决方法(0)

在Wikibooks的Haskell中,有以下声明:

Data.List提供用于排序列表的排序功能.它不使用quicksort; 相反,它使用称为mergesort的算法的有效实现.

Haskell使用mergesort而不是quicksort的根本原因是什么？Quicksort通常具有更好的实际性能,但在这种情况下可能不是.我认为快速排序的现场好处很难(不可能？)与Haskell列表有关.

关于so​​ftwareengineering.SE有一个相关的问题,但实际上并不是为什么使用 mergesort.

我自己实现了两种类型的分析.Mergesort是优越的(大约是2 ^ 20个元素列表的两倍),但我不确定我的quicksort实现是否最佳.

编辑:这是我的mergesort和quicksort的实现:

mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
    where size = div (length l) 2
          (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls [] = ls
merge [] vs = vs
merge first@(l:ls) …

我有一个用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书籍的方式,并且已经到了一个章节,作者正在解释一些列表连接可能效率低下:例如

((((a ++ b) ++ c) ++ d) ++ e) ++ f

据说效率低下.作者提出的解决方案是使用定义为的"差异列表"

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

我很难理解为什么DiffList在某些情况下比简单串联更具计算效率.有人可以用简单的语言向我解释为什么上面的例子是如此低效,以及DiffList以什么方式解决了这个问题？

我正在寻找Haskell 上MergeSort的规范实现以移植到HOVM，我找到了这个StackOverflow 答案。在移植算法时，我意识到有些事情看起来很愚蠢：该算法有一个“减半”函数，除了在递归和合并之前使用一半的长度将列表一分为二之外什么也不做。所以我想：为什么不更好地利用这个传球，并使用一个枢轴，使每一半分别比该枢轴小和大呢？这会增加递归合并调用应用于已排序列表的可能性，这可能会加快算法速度！

我已经完成了此更改，生成以下代码：

import Data.List
import Data.Word

randomList :: Word32 -> Word32 -> [Word32]
randomList seed 0    = []
randomList seed size = seed : randomList (seed * 1664525 + 1013904223) (size - 1)

quacksort :: [Word32] -> [Word32]
quacksort []           = []
quacksort [x]          = [x]
quacksort (p : x : xs) = split p (p : x : xs) [] [] where

  -- Splits the list in two halves of elements …

正如他们所说,"真正的快速排序就地排序".所以标准的短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.伪快速排序时间复杂度.

我正在学习haskell,我看到的函数定义是:

quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
                 where less = filter (< x) xs
                       equal = filter (== x) xs
                       more = filter (> x) xs

是否可以只用一次遍历列表而不是3来编写它？

我正在通过Real World Haskell工作(我在第4章)并且练习了一下我已经创建了以下程序来计算第n个素数.

import System.Environment

isPrime primes test = loop primes test
    where
        loop (p:primes) test
            | test `mod` p == 0 = False
            | p * p > test = True
            | otherwise = loop primes test


primes = [2, 3] ++ loop [2, 3] 5
    where 
        loop primes test
            | isPrime primes test = test:(loop primes' test')
            | otherwise = test' `seq` (loop primes test')
            where
               test' = test + 2
               primes' = primes ++ [test]

main :: …

这就是我所做的:

(define qsort
  (lambda (l)
    (let ((lesser '()))
      (let ((greater '()))
        (cond
          ((null? l) '())
          (else (map (lambda (ele)
                       (if (> (car l) ele)
                           (set! lesser (cons ele lesser))
                           (set! greater (cons ele greater)))) (cdr l))
                (append (qsort lesser) (cons (car l) (qsort greater))))
        )))))

我注意到,当提供已经排序的列表时,它变得极其缓慢.经过一番搜索后,我发现如果以随机方式选择"枢轴",可以提高性能.然而,我知道实现这一目标的唯一方法是list-ref,它似乎是O(n).更糟糕的是,我必须实现一个类似cdr的函数来删除列表中的第n个元素,这可能也是非常低效的.

也许我的方向错了.你能给我一些建议吗？

我有这个代码:

import Data.List

newList_bad  lst = foldl' (\acc x -> acc ++ [x*2]) [] lst
newList_good lst = foldl' (\acc x -> x*2 : acc) [] lst

这些函数返回列表,每个元素乘以2:

*Main> newList_bad [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> newList_good [1..10]
[20,18,16,14,12,10,8,6,4,2]

在ghci:

*Main> sum $ newList_bad [1..15000]
225015000
(5.24 secs, 4767099960 bytes)
*Main> sum $ newList_good [1..15000]
225015000
(0.03 secs, 3190716 bytes)

为什么newList_bad功能比它慢200倍newList_good？我知道这不是一个很好的解决方案.但为什么这个无辜的代码工作得如此之慢？

这是什么"4767099960字节"?? 对于那个简单的操作,Haskell使用4 GiB ??

编译后:

C:\1>ghc -O --make test.hs
C:\1>test.exe
225015000
Time for sum (newList_bad [1..15000]) is 4.445889s …