python - 如何针对大型列表优化功能合并排序

Question

我正在尝试同时学习函数式编程和算法，并且我已经在 Haskell 中实现了合并排序。然后我将样式转换为python并在学习平台上运行测试，但我得到的返回是对1000个整数的列表进行排序需要很长时间。

有没有一种方法可以优化我的 python 代码并仍然保持我的函数式风格，或者我是否必须迭代地解决问题？

提前致谢。

这是我首先在 Haskell 中编写的代码。

merge :: Ord a => [a] -> [a] -> [a]
merge [] xs = xs
merge ys [] = ys
merge (x:xs) (y:ys)
  | (x <= y) = x : (merge xs (y:ys))
  | otherwise = y : (merge (x:xs) ys)

halve :: [a] -> ([a] , [a])
halve [x] = ([x], [])
halve xs = (take n xs , drop n xs)
        where n = length xs `div` 2

msort :: Ord a => [a] -> [a]
msort [x] = [x]
msort [] = []
msort xs = merge (msort n) (msort m)
    where (n,m) = halve xs

然后我根据 Haskell 风格用 python 编写了这段代码。

import sys
sys.setrecursionlimit(1002) #This is because the recursion will go 1002 times deep when I have a list on 1000 numbers.
    
def merge(xs,ys):
    if len(xs) == 0:
        return ys
    elif len(ys) == 0:
        return xs
    else:
        if xs[0] <= ys[0]:
            return [xs[0]] + merge(xs[1:], ys)
        else:
            return [ys[0]] + merge(xs, ys[1:])

def halve(xs):
    return (xs[:len(xs)//2],xs[len(xs)//2:])

def msort(xss):
    if len(xss) <= 1:
        return xss
    else:
        xs,ys = halve(xss)
        return merge(msort(xs), msort(ys))

是否有更智能的方法可以优化 python 版本并仍然具有函数式风格？

Answer 1

Haskell 列表是惰性的。 [x] ++ xs首先产生x ，然后它生成 xs 中的所有元素.

例如Lisp 列表是单链列表，附加它们复制第一个列表，因此在前面添加一个单例是一个O(1) 操作。

在Python中，虽然附加复制了第二列表(正如评论中的@chepner所确认的)，即[x] + xs将复制整个列表 xs因此是一个 O(n) 操作(其中 n 是 xs 的长度)。

这意味着您的 [xs[0]] + merge(xs[1:], ys)和[ys[0]] + merge(xs, ys[1:])导致二次行为，您将其观察为您所描述的急剧减速。

Python 相当于 Haskell 的惰性列表的不是列表，而是生成器，它在每个 yield 上一一生成元素。 。因此重写可能看起来像

def merge(xs,ys):
    if len(xs) == 0:
        return ys
    elif len(ys) == 0:
        return xs
    else:
        a = (x for x in xs)     # or maybe iter(xs)
        b = (y for y in ys)     # or maybe iter(ys)
        list( merge_gen(a,b))

现在剩下的就是重新实现您的 merge逻辑为merge_gen它需要两个生成器(或者应该是迭代器？一定要找到)作为其输入，并生成有序的元素流，该元素是通过根据需要从两个源中一一拉取而获得的。正如函数调用者所期望的那样，生成的元素流将转换回列表。不会执行多余的复制。

如果我犯了一些明显的 Python 错误，请将以上内容视为伪代码。

---

您的另一个选择是预先分配相同长度的第二个列表，并在合并时来回复制两个列表之间的元素，使用索引来引用数组的元素并进行变异存储结果的内容。