如何优化大型列表的功能合并排序

Question

我正在尝试同时学习函数式编程和算法，并且我在 Haskell 中实现了归并排序。然后我将样式转换为 python 和运行在学习平台上进行测试，但我得到 return 在 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 专家，所以我可能遗漏了一些东西。这是我最好的赌注：

Haskell 列表不是状态感知的。其中的一个含义是可以共享列表。这使得在内存分配上减半的操作更精简——要生成一个 'drop n xs' 你只需要分配一个列表节点（或者它们在 Haskell 中被调用的任何东西）并将它指向 ( n 'div' 2) + 减半前列表中的 1 个节点。请注意 'take' 无法执行此小技巧 - 不允许更改列表中任何节点的状态，因此它必须为第一个 n [=45] 分配具有相同值的新节点对象=] 前减半列表中的 2 个元素。

现在看看该函数的 python 等效项 - 要将列表减半，您可以使用列表切片：

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

在这里你分配了两个列表而不是一个 - 在递归树的每一层！（我也很确定 python 中的列表比 Haskell 中的列表复杂得多，所以分配也可能更慢）

我会做什么：

检查我的赌博 - 使用时间模块查看您的代码是否花费了太多时间来分配这些列表，与总体运行时间相比。
万一我的赌博被证明是正确的 - 避免这些分配。一种（不是很优雅，但可能很快）解决它的方法 - 传递一个列表，以及指示每一半开始和结束位置的索引。使用偏移量而不是每次都分配一个新列表。（编辑：）您也可以避免类似的分配 - 每当您想要切片时，将索引传递给新列表的 begin\end。
最后一句话 - 您提到的要求之一是保持功能方法。人们可以将其解释为让您的代码没有副作用。为此，我将定义一个输出列表，并将您合并的元素存储在其中。结合索引方法，不会改变输入列表的状态，并会产生一个新的排序输出列表。

编辑：另一件值得一提的事情是：python 列表不是单链表，就像 Haskell 列表一样。它们是一种更常被称为 Dynamic Arrays 的数据结构。这意味着像切片、从列表中间删除一个对象等东西是昂贵的，因为它对数组中的所有对象都有影响。另一方面，您可以访问 O(1) 中第 i 个索引处的对象。你应该记住这一点，它与你提出的问题密切相关。

Answer 2

Haskell 列表是惰性的。 [x] ++ xs 首先生成 x，然后生成 xs.

中的所有元素

例如Lisp 列表是单链表并附加它们 copies 第一个列表，所以在单例前面添加一个 O(1) 操作。

在 Python 中，尽管附加复制了 second 列表（正如 @chepner 在评论中确认的那样），即 [x] + xs 将 copy 整个列表 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 错误，请将以上内容视为伪代码。

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

如何优化大型列表的功能合并排序

How can I optimize a functional mergesort for large lists

python

recursion

performance

mergesort

haskell