代码之家 › 专栏 › 技术社区 › YasirA

气泡排序算法实现(Haskell与C)

bubble-sort functional-programming haskell optimization c

YasirA · 技术社区 · 14 年前

我已经用C和Haskell编写了2个气泡排序算法的实现。 Haskell实现:

module Main where
main = do
    contents <- readFile "./data"
    print "Data loaded. Sorting.."
    let newcontents = bubblesort contents
    writeFile "./data_new_ghc" newcontents
    print "Sorting done"
bubblesort list = sort list [] False
rev  = reverse          -- separated. To see
rev2 = reverse          --  who calls the routine
sort (x1:x2:xs) acc _
    | x1 > x2           = sort (x1:xs) (x2:acc) True
sort (x1:xs) acc flag   = sort xs (x1:acc) flag
sort [] acc True        = sort (rev acc) [] False
sort _ acc _            = rev2 acc

我比较了这两个实现在文件上都运行,大小为20kib。
C实施大约花了一秒钟,haskell_约1分10秒。
我还介绍了Haskell应用程序:
编译以进行分析:

C:\temp>ghc-prof-auto all-o-make main

轮廓:

C:\temp>主.exe+rts-P

并且得到 these 结果。这是算法的伪代码:

procedure bubbleSort( A : list of sortable items ) defined as:
    do
        swapped := false
        for each i in 0 to length(A) - 2 inclusive do:  
            if A[i] > A[i+1] then  
                swap( A[i], A[i+1] )  
                swapped := true  
            end if  
        end for  
    while swapped  
end procedure

我想知道是否可以在不更改算法的情况下使haskell实现更快地工作(实际上有一些技巧可以使算法更快地工作,但两个实现都没有这些优化)。

4 回复 | 直到 14 年前

Antal Spector-Zabusky 14 年前

这可能是因为冒泡排序是数组的一种算法,但您使用的是链表:在一个数组中交换两个项目(这是C使用的)是O(1)时间,不需要额外的空间,但在链表中交换两个项目(这是Haskell使用的)是O(n)时间和O(n)空间(这是堆空间,而不是堆空间)。但是,我在跟踪您的代码时遇到了一些问题(您确定这是相同的算法吗?)而且您的累加器可能处理交换的时间复杂性。但是,即使这样,您也要分配一个新的累加器列表;这肯定会分配额外的空间,我认为这可能仍然是导致haskell性能下降的原因之一。

还有,你为什么有 rev 和 rev2 ,而不仅仅是使用 reverse 在这两个地方?如果是因为您想单独分析它们,那么您应该使用scc(“ S 电子技师 C 奥斯特 C 输入”)pragma,如中所述 chapter 5 GHC用户指南: sort ({-# SCC "rev" #-} reverse acc) [] False 和 {-# SCC "rev2" #-} reverse acc . 各成本中心分别进行概要分析; -auto-all 只是在每个函数周围隐式地添加成本中心。如果您出于其他原因拥有这些功能,您可能仍然不应该(为什么要这样做?),但我的解释无关紧要:)

Reid Barton 14 年前

因为冒泡排序的内存位置属性非常差,所以我认为您的实现很可能是内存带宽限制的,尽管我没有做任何测试。

土生土长的哈斯克尔 String = [Char] 非常方便,但不适合以性能为主的情况。我忘了确切的数字,但我相信 String 在32位系统中,每个字符至少使用16个字节,而在64位系统中,大约使用两倍的字节。相比之下,我假设您的C程序每个字符使用1个字节。因此,单从这一点来看,经济增长将放缓约16倍。

您还通过一对链表(通常称为“拉链”)模拟可变数组。这是相当有效的,只要你在一个移动的焦点周围进行局部修改,这在大多数情况下都是如此。但是,在每次传球结束时,您需要将焦点移回开始位置(这是 rev )这可能是算法完成工作量的另一个因素2。

所以,我认为你的基准并不令人惊讶。

如果您想在haskell中编写一个快速的BubbleSort,那么接下来的方法是直接在 ST Monad使用可变的未装箱数组。我不认为你会很快看到一个完全纯语言的冒泡,有一个更好的常数(尽管我当然希望被证明是错误的)。

MtnViewMark 14 年前

您可以在haskell中更直接地表达算法,而不需要反向调用:

bubblesort :: (Ord a) => [a] -> [a]
bubblesort []      = []
bubblesort (x0:xs) = case bubble x0 xs of
   (xs', True)  -> bubblesort xs'
   (xs', False) -> xs'
   where bubble x1 (x2:xs) | x1 <= x2  = merge x1 False $ bubble x2 xs
                           | otherwise = merge x2 True  $ bubble x1 xs
         bubble x1 []                  = ([x1], False)
         merge x s (xs, s') = (x:xs, s || s')

在这里,局部冒泡函数执行冒泡值的任务,合并函数处理重建新的冒泡列表和交换标志。BubbleSort中的case表达式是haskell中的一个直接表达式,“在列表中冒泡一次,如果我们交换了任何东西,就再做一次”。

这个版本比原来的快35%。

P.S.:代码和驱动程序主文件如下: http://bitbucket.org/mtnviewmark/haskell-playground/src/tip/cafe/

Nathan Shively-Sanders 14 年前

我注意到你通过了 -O 而不是 -O2 . 你可能会加快速度 -O2 .

正如其他人提到的,这与C和Haskell中的算法不同,因为数据结构不同——Haskell使用了一个不可变的Unicode字符链接列表。你的目的是什么?

各种语言中最快的一种?
许多语言中最快的冒泡排序?
最快的 惯用的 多种语言的冒泡排序?

我想(1)不是这样的,因为您也在C中使用冒泡排序。如果(2),则应使用 Word8 S,这将给你一个接近C版本的算法(虽然可能更丑更慢)。如果(3),我有点困惑,因为冒泡排序实际上只在basic中看起来是惯用的(旧的那种,你将整个单词大写,而不是像只有两个大写的visualbasic)。您应该期望优雅和性能会随着语言与基本语言的相似性而下降。

不管是什么情况,在C语言中看到不可变的链表递归冒泡类型的Unicode字符串的性能是很有趣的。