Реализация алгоритма пузырьковой сортировки (Haskell vs. C) - PullRequest
Новая
       15

Реализация алгоритма пузырьковой сортировки (Haskell vs. C)

3 голосов
/ 21 марта 2010

Я написал 2 реализации алгоритма пузырьковой сортировки на C и Haskell. Реализация на 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

Я сравнил эти две реализации, запустив обе файлы размером 20 КиБ.
C реализация заняла около секунды, Haskell - около 1 мин 10 сек.
Я также профилировал приложение на Haskell:
Скомпилировать для профилирования:

C: \ Temp> ghc -prof -auto-all -O - сделать Main

Профиль:

C: \ Temp> Main.exe + RTS -p

и получил эти результаты. Это псевдокод алгоритма: 

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 ]

11 голосов
/ 21 марта 2010

Вероятно, это связано с тем, что пузырьковая сортировка является алгоритмом для массивов, но вы используете связанный список: замена двух элементов в массиве (то, что использует C) - это O (1) времени и не требует посторонних пробелов, а замена два элемента в связанном списке (который использует Haskell) - это O (n) время и O (n) пространство (а это пространство кучи, а не пространство стека). Однако у меня возникли небольшие проблемы с отслеживанием вашего кода (вы абсолютно уверены, что это тот же алгоритм?), И, возможно, ваш аккумулятор справляется со сложностью времени свопа. Однако, даже если это так, вы выделяете новый список аккумуляторов; это определенно все равно выделит дополнительное пространство, и я думаю, что это вполне может быть одной из причин худшей производительности Haskell.

Кроме того, почему у вас есть rev и rev2, а не просто reverse в обоих местах? Если это потому, что вы хотели профилировать их отдельно, то вместо этого следует использовать прагму SCC (" S et C ost C enter"), описанную в глава 5 Руководства пользователя GHC: sort ({-# SCC "rev" #-} reverse acc) [] False и {-# SCC "rev2" #-} reverse acc. Каждый МВЗ профилируется отдельно; -auto-all просто неявно добавляет центры затрат вокруг каждой функции. Если у вас есть эти функции по какой-то другой причине, вы все равно, вероятно, не должны (почему вы?), Но мое объяснение не имеет значения:)

6 голосов
/ 21 марта 2010

Поскольку пузырьковая сортировка имеет довольно плохие свойства локальности памяти, я думаю, что ваши реализации ограничены пропускной способностью памяти, хотя я не проводил никакого тестирования.

Собственный Haskell String = [Char] чрезвычайно удобен, но не подходит, когда производительность является основным приоритетом. Я забыл точные цифры, но я уверен, что String использует не менее 16 байтов на символ в 32-битной системе и примерно вдвое больше, чем в 64-битной системе. В отличие от этого я предполагаю, что ваша программа на C использует 1 байт на символ. Таким образом, от одного этого можно ожидать примерно 16-кратного замедления.

Вы также эмулируете изменяемый массив с помощью пары связанных списков (это обычно называется "молнией"). Это достаточно эффективно, если вы делаете локальные модификации вокруг движущегося фокуса, что верно по большей части в пузырьковой сортировке. Однако в конце каждого прохода вам необходимо переместить фокус обратно на начало (это rev). Это, вероятно, учитывает еще один фактор 2 в объеме работы, проделанной в алгоритме.

Итак, я не думаю, что ваши тесты очень удивительны.

Если вы хотите написать быструю пузырьковую сортировку в Haskell, вы можете реализовать псевдокод непосредственно в монаде ST, используя изменяемый распакованный массив. Я не думаю, что вы увидите пузырчатую сортировку на совершенно чистом языке с гораздо лучшим постоянным коэффициентом в ближайшее время (хотя я бы, конечно, хотел бы оказаться неправым).

5 голосов
/ 21 марта 2010

Вы можете выразить алгоритм более прямо в 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')

Здесь локальная пузырьковая функция выполняет работу по барботированию значения, а функция слияния обрабатывает как восстановление нового всплывающего списка, так и флага подкачки. Выражение case в bubblesort является прямым выражением в Haskell: «Один раз пролистайте список, и если мы что-то поменяли местами, сделаем это снова».

Эта версия работает примерно на 35% быстрее, чем ваша оригинальная.

P.S .: Код и драйвер Основные файлы можно найти здесь: http://bitbucket.org/mtnviewmark/haskell-playground/src/tip/cafe/

2 голосов
/ 22 марта 2010

Я заметил, что вы передали -O вместо -O2.Вы можете получить некоторую скорость от -O2.

. Как уже упоминали другие, это не тот же алгоритм в C и Haskell, потому что структуры данных различаются - Haskell использует неизменный связанный список символов Unicode.Какова ваша цель?

  1. Самый быстрый вид любого типа на многих языках?
  2. Самый быстрый вид пузырьков на многих языках?
  3. Самый быстрый идиоматический пузырьковая сортировка во многих языках?

Полагаю, (1) это не так, поскольку вы также используете пузырьковую сортировку в Си.Если (2), то вы должны использовать STUArray из Word8 s, что даст вам алгоритм, близкий к версии C (хотя, возможно, более уродливый и медленный).Если (3), я в некотором роде запутался, потому что пузырьковая сортировка действительно выглядит идиоматично только в BASIC (старый вид, где вы пишете с заглавной буквы все слово, а не как VisualBasic только с двумя заглавными буквами).Вы должны ожидать, что элегантность и производительность будут ухудшаться в прямой зависимости от сходства языка с BASIC.

В любом случае, было бы интересно увидеть производительность неизменяемого рекурсивного пузырькового рода связанного списка строк Unicode в C.

...