способ сортировки слиянием быстрее, чем сортировка вставками - PullRequest
Новая
       6

способ сортировки слиянием быстрее, чем сортировка вставками

13 голосов
/ 19 января 2012

Только что промок в алгоритме сортировки с Haskell. Я реализовал сортировку вставкой и сортировку слиянием 

insert_sort :: (Ord a, Show a) => [a] -> [a]
insert_sort keys = foldr f [] keys
           where f key []        = [key]
                 f key acc       = insert key acc
                 insert y []     = [y]
                 insert y (x:xs)
                     | x < y     = x : insert y xs
                     | otherwise = y : x : xs

merge_sort :: (Ord a, Show a) => [a] -> [a]
merge_sort (x:[]) = [x]
merge_sort keys   = merge  (merge_sort (take len keys)) (merge_sort (drop len keys))
      where len         = length keys `div` 2
            merge :: [a] -> [a] -> [a]
            merge (x:xs) []     = (x:xs)
            merge []     (y:ys) = (y:ys)
            merge (x:xs) (y:ys) = if x <= y
                                  then x : merge (xs) (y:ys)
                                  else y : merge (x:xs) ys

Вот как я сравнил их эффективность: 

insert_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int]
merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int]

Оба они начинают распечатывать результаты после небольшой задержки, но сортировка слиянием печатает намного быстрее. Как мы знаем, сортировка слиянием намного быстрее, чем сортировка вставкой для больших наборов данных. Я думал, что это будет показано тем, как они дают результаты (например, большая задержка или короткая), а не тем, как они печатают результаты. Это потому, что я использую foldr в сортировке вставок? Что за сценой?

РЕДАКТИРОВАТЬ : Спасибо, ребята. Я слышал о ленивых оценках с тех пор, как начал изучать Haskell, но все же понял это. Кто-нибудь проиллюстрирует немного больше с небольшим набором данных, скажем, [5,2,6,3,1,4]? Как можно вывести результаты до завершения сортировки с foldr, так как первые элементы появляются в конце?

Ответы [ 2 ]

14 голосов
/ 19 января 2012

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

По запросу: как происходит сортировка [5,2,6,3,1,4]. Я использую insert_sort = foldr ins [] для краткости. 

insert_sort [5,2,6,3,1,4]
  = foldr ins [] [5,2,6,3,1,4]
  = 5 `ins` foldr ins [] [2,6,3,1,4]
  = 5 `ins` 2 `ins` [6,3,1,4] ...
  = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` 4 `ins` []
  = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` (4:[])
  = 5 `ins` 2 `ins` 6 `ins` 3 `ins` (1:4:[])
  = 5 `ins` 2 `ins` 6 `ins` (1 : (3 `ins` (4:[])))
  = 5 `ins` 2 `ins` (1 : (6 `ins` (3 `ins` (4:[]))))
  = 5 `ins` (1 : (2 `ins` (6 `ins` (3 `ins` (4:[])))))
  = 1 : (5 `ins` (2 `ins` (6 `ins` (3 `ins` (4:[])))))  -- now 1 can be output
  = 1 : (5 `ins` (2 `ins` (6 `ins` (3:4:[]))))
  = 1 : (5 `ins` (2 `ins` (3 : (6 `ins` (4:[])))))
  = 1 : (5 `ins` (2 : (3 : (6 `ins` (4:[])))))
  = 1 : 2 : (5 `ins` (3 : (6 `ins` (4:[]))))            -- now 2 can be output
  = 1 : 2 : 3 : (5 `ins` (6 `ins` (4:[])))              -- now 3
  = 1 : 2 : 3 : (5 `ins` (4:6:[]))
  = 1 : 2 : 3 : 4 : (5 `ins` (6:[]))                    -- now 4
  = 1 : 2 : 3 : 4 : 5 : 6 : []                          -- done

И сортировка слиянием (сокращения: merge = mg, merge_sort = ms): 

merge_sort [5,2,6,3,1,4]
  = mg (ms [5,2,6]) (ms [3,1,4])
  = mg (mg (ms [5]) (ms [2,6])) (mg (ms [3]) (ms [1,4]))
  = mg (mg [5] (mg [2] [6])) (mg [3] (mg [1] [4]))
  = mg (mg [5] [2,6]) (mg [3] [1,4])
  = mg (2 : mg [5] [6]) (1 : mg [3] [4])
  = 1 : mg (2 : mg [5] [6]) (mg [3] [4])                -- now 1 can be output
  = 1 : mg (2 : mg [5] [6]) [3,4]
  = 1 : 2 : mg (mg [5] [6]) [3,4]                       -- now 2 can be output
  = 1 : 2 : mg [5,6] [3,4]
  = 1 : 2 : 3 : mg [5,6] [4]                            -- now 3
  = 1 : 2 : 3 : 4 : mg [5,6] []                         -- now 4
  = 1 : 2 : 3 : 4 : 5 : 6 : []                          -- now 5 and 6

Правда, я сделал несколько коротких путей, но Хаскелл не единственный ленивый.

9 голосов
/ 19 января 2012

Хорошо, вот и сломался.Вы хотите, чтобы я распечатал: 

merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int]

Я знаю, что это список.Итак, сначала я распечатаю открытую скобку 

[

Затем я поищу первый элемент списка, распечатаю его, а затем запятую.Это означает, что я должен начать оценивать это выражение, пока не смогу выяснить, что является первым элементом списка. 

merge_sort THUNK0

Что ж, теперь мне нужно сопоставить шаблон.Либо THUNK соответствует (x:[]), либо нет.Но я пока не знаю.Так что я оценил это немного.Я делаю, что thunk производит первые два случайных числа (из 100000).Теперь я знаю , что оно не соответствует первому определению, поэтому я беру второе определение merge_sort. 

merge_sort keys = merge THUNK1 THUNK2 -- keys = THUNK0

Ну, это достаточно просто ... это просто вызовобъединить.Я расширю это определение.Вот дерьмо, это может соответствовать трем различным шаблонам.Думаю, мне следует немного оценить THUNK1 и посмотреть, соответствует ли он шаблону первого определения, (x:xs)

merge_sort (take THUNK3 THUNK0)

Вернемся к merge_sort, не так ли?Это означает, что мне нужно оценить (take THUNK3 THUNK0) достаточно, чтобы определить, соответствует ли оно (x:[]) или нет.Ох хреньtake является строгим в первом аргументе ... это означает, что я должен полностью оценить THUNK3.Хорошо ... глубокие вдохи ... 

len = length THUNK0 `div` 2

Теперь вот раздражающий случай.Чтобы вычислить length на THUNK0 (который является списком), я должен расширить ВЕСЬ СПИН.Мне не нужно на самом деле вычислять значения внутри, но мне нужно конкретизировать структуру всего списка.Это, конечно, делается по одному совпадению с шаблоном за раз, определяя, является ли оно [] или (x:xs).Но в целом, length является "строгим позвоночником".

короткая пауза, пока я уточняю позвоночник из списка из 100000 элементов

Фу, понял, чтосделанный.Теперь я знаю длину, а это значит, что я знаю len = 500000.THUNK0 наконец полностью оценено!Уф!Где я был? 

merge_sort (take 500000 THUNK3)

И так далее.merge_sort продолжит пытаться быть как можно более ленивым.Рекурсивные вызовы на merge_sort будут максимально ленивыми.В конце концов, чтобы определить самый первый элемент самого внешнего merge_sort, нам нужно будет знать самый первый элемент обоих рекурсивных вызовов merge_sort.И чтобы узнать первый элемент из них ... нам понадобится первый элемент последующих рекурсивных вызовов и т. Д. Так что будет выполнено около O (n) проделанной работы, потому что каждый элемент должен быть оценен(выполняя генерацию случайных чисел для каждого).

Тогда думайте об этом как о турнире.Каждый элемент связан с другим элементом.«Победившие» (самые низкие) элементы переходят к следующему раунду (становясь первым элементом рекурсивного вызова к самым низким merge_sort с).Существует еще одно соревнование, в котором участвуют 1/2 бойца, и 1/2 из тех, кто (1/4 от общего числа) переходит в следующий раунд и т. Д. Также получается, что O (n) работа, так как (n / 2) сравнения выполняются в течение первого раунда, а последующие раунды уменьшаются слишком быстро, чтобы быть значительными.(Сумма 1/2 + 1/4 + 1/8 ... сходится в 1, что означает, что выполнено всего n сравнений.)

Всего O (n) работа должна быть выполнена, чтобы наконец произвести первый элемент.Для последующих элементов необходимо выполнить дополнительную работу, но общий объем работы в итоге составит O (n log (n)) .

Теперь сопоставьте это с insert_sort,Подумайте, как это работает: он пересекает список и «вставляет» каждый элемент в отсортированный список.Это означает, что вы не можете точно знать , какой первый элемент отсортирован , пока вы не выполнили последний бит работы и не вставили последний элемент (который мог быть самым низким)в отсортированный список.

Я надеюсь, что это ясно иллюстрирует, как merge_sort не нужно выполнять все работы, чтобы начать давать результаты, в то время как insert_sort делает.

...