4

我想编写一个合并函数，该函数采用多个 x 排序列表并将它们按增量值（从最小到最大）合并到一个排序列表中。我想我可以做两个列表并组合成一个，但无法弄清楚多个列表的基本情况并组合成一个排序。

merge :: [[a]] -> [a]
4

6 回答 6

10

也许更快的实现：

mergeTwo :: Ord a => [a] -> [a] -> [a]
mergeTwo x [] = x
mergeTwo [] x = x
mergeTwo (x:xs) (y:ys) = if x < y
                          then x:(mergeTwo xs (y:ys))
                          else y:(mergeTwo (x:xs) ys)

mergePairs :: Ord a => [[a]] -> [[a]]
mergePairs [] = []
mergePairs (x:[]) = [x]
mergePairs (x:y:tail) = mergePairs ((mergeTwo x y):(mergePairs tail))

mergeAll :: Ord a => [[a]] -> [a]
mergeAll [] = []
mergeAll x = head $ mergePairs x

mergeTwo 只是合并两个列表。mergeAll 只是运行 mergePairs 并返回 head 如果有的话。魔术发生在 mergePairs 中，它采用列表列表并合并对，而不是再次这样做等等，而至少有两个列表。

它可能会更快，想象你正在跑步

merge = foldl merge2 []

它需要一个长列表并合并和合并。如果你在 [[1,2,3],[4,5,6],[7,8,9],[10,11,12]] 运行它，它会合并：

[] 与 [1,2,3]

[1,2,3] 与 [4,5,6]

[1,2,3,4,5,6] 与 [7,8,9]

[1,2,3,4,5,6,7,8,9] 与 [10,11,12]

但是您想保留大约相同长度的列表。所以你想合并：

[1,2,3] 与 [4,5,6]

[7,8,9] 与 [10,11,12]

[1,2,3,4,5,6] 与 [7,8,9,10,11,12]

您还可以考虑合并对的并行实现，它在多核处理器上可能很有用。但我没有这方面的经验：/

于 2013-03-10T21:05:09.657 回答
8

如果您可以为两个列表定义函数，那么您可以通过简单地遍历每个子列表并将其与当前结果合并，直到您合并所有列表，将其推广到任意多个列表。这可以表示为这样的折叠：

merge = foldr merge2 []
于 2013-03-10T20:30:47.270 回答
6

@sepp2k 的答案很好，但它只适用于有限多个输入列表。如果你给它无限多的列表，它将永远试图找到最小的起始元素。

我们可以通过要求输入列表已经通过增加第一个元素来排序来解决这个问题。然后我们知道我们可以产生“左上”元素（第一个列表的第一个元素），因为它将是所有内容的下限，这为我们提供了足够的信息来递归使用并产生完整的合并。

merge :: (Ord a) => [[a]] -> [a]
merge [] = []
merge ([]:xss) = merge xss
merge ((x:xs):xss) = x : merge2 xs (merge xss)

写作merge2仍然留给读者作为练习:-)

于 2013-03-10T21:01:57.803 回答
3

如果您先将列表与 合并，则要容易concat得多sort。

import Data.List(sort)

mergeSort = sort . concat
于 2013-03-10T22:49:34.817 回答
1

这是 mergeSort 或 timSort 算法的基本部分，但遗憾的是在这个主题下没有正确的答案。我的意思是一个有效率的。

让我们假设一个包含块的chunks列表，k = 9例如块在[as,bs,cs,ds,es,fs,gs,hs,is]哪里as..is。

foldl merger [] chunks

将产生以下操作

merge as bs -> abs
merge abs cs -> abcs
merge abcs ds -> abcds
merge abcds es -> abcdes
merge abcdes fs -> abcdefs
merge abcdefs gs -> abcdefgs
merge abchefgs hs -> abcdefghs
merge abcdefghs is -> abcdefghis

在哪里操作 8 次，as操作7 ..操作 1 次。总共是 k(k+1)/2 = 44 次操作。如果您有 100,000 个块，将进行 5,000,050,000 次操作。复杂度为 O(n^2)。bscsis

@kyticka 似乎已经注意到了这一事实，并在他的回答中提到了它的重要性，但未能正确实施（由于双重递归，这有时具有欺骗性）。他的方法仅在第一阶段消除了多余的操作，并将块放在排序的对中，然后像幼稚的方法一样继续进行，只是从右折叠如下；

let mt = mergeTwo
    mp = mergePairs

mp (mt as bs : mp [cs,ds,es,fs,gs,hs,is]))
mp (mt as bs : mp (mt cs ds : mp [es,fs,gs,hs,is]))
mp (mt as bs : mp (mt cs ds : mp (mt es fs : mp [gs,hs,is])))
mp (mt as bs : mp (mt cs ds : mp (mt es fs : mp (mt gs hs : mp [is])))
mp (mt as bs : mp (mt cs ds : mp (mt es fs : mp [ghs,is])))
mp (mt as bs : mp (mt cs ds : mp (mt es fs : mp (mt ghs is : mp []))))
mp (mt as bs : mp (mt cs ds : mp (mt es fs : mp [ghis])))
mp (mt as bs : mp (mt cs ds : mp [efs, ghis]))
mp (mt as bs : mp (mt cs ds : mp (mt efs ghis : mp [])))
mp (mt as bs : mp (mt cs ds : mp [efghis]))
mp (mt as bs : mp [cds, efghis])
mp (mt as bs : mp (mt cds efghis : mp []))
mp (mt as bs : mp [cdefghis])
mp [abs, cdefghis]
mp (mt abs cdefghis : mp [])
mp [abcdefghis]
[abcdefghis]

所以 chunks 的合并操作计数如下

  • 作为 = 2 ( mt as bs- mt abs cdefghis)
  • bs = 2 ( mt as bs- mt abs cdefghis)
  • cs = 3 ( mt cs ds- mt cds efghis- mt abs cdefghis)
  • ds = 3 ( mt cs ds- mt cds efghis- mt abs cdefghis)
  • es = 4 ( mt es fs- mt efs ghis- mt cds efghis- mt cds efghis)
  • fs = 4 与 es 相同
  • gs = 5 ...
  • hs = 5 与 gs 相同
  • 是 = 5

操作总数为 33。我猜这可能类似于 k(k+1)/2 - k..？与天真的解决方案相比，它不会产生任何显着差异，foldl因为它仍然是 O(n^2)。

这是一个 O(nLog(n)) 的尝试。

mergeChunks :: Ord a => [a] -> [a] -> [a]
mergeChunks xs [] = xs
mergeChunks [] ys = ys
mergeChunks p@(x:xs) q@(y:ys) | x <= y    = x : mergeChunks xs q
                              | otherwise = y : mergeChunks p ys

mergePairs :: Ord a => [[a]] -> [[a]]
mergePairs []         = []
mergePairs (ps:[])    = [ps]
mergePairs (ps:qs:rs) = mergeChunks ps qs : mergePairs rs

mergeAll :: Ord a => [[a]] -> [a]
mergeAll []     = []
mergeAll [c]    = c
mergeAll cs     = mergeAll (mergePairs cs)
于 2018-11-11T11:09:45.403 回答
-3 
import Data.List ( sort )

sortLists :: (Ord a) => [[a]] -> [a]
sortLists cs = concatMap sort cs

test = [ [3,1,2],
         [5,4],
         [6,8,9,7] ]

main = print $ sortLists test

要真正享受 haskell，请仔细查看并牢记Preludeand Data.List。它们是每个 Haskell 程序员的生计。

于 2013-03-10T21:32:08.713 回答