如何在Python中高效排序大型数据集？

Question

我正在做一个项目，需要在Python中高效地对一个大数据集进行排序。这个数据集有数百万条记录，而我现在使用的是内置的 sorted() 函数。不过，我遇到了性能问题，排序过程花费的时间很长。

我查过一些替代方案，比如 heapq、numpy 和一些外部排序算法，但对于我这个数据集的大小，我不太确定哪种方法最好。

有没有人能提供一些建议或者示例，介绍在Python中处理大数据集时高效的排序技巧？另外，如果能分享一些关于在排序过程中优化内存使用的见解，那就太好了。

Answer 1

编辑：在对提供的回应进行基准测试后，我发现多进程反而让排序变慢了。

如果你使用的是内置函数，那就说明你的数据可以放进内存里。

在不知道数据具体情况的前提下，如果有可能处理数据来加快排序的话，我会建议你在处理非常大的数据集时，可以使用并行处理来提升性能。

下面是一个使用Python内置包进行并行排序的方法：

import os
from multiprocessing import Pool
from random import sample
import heapq


def sort_chunk(chunk):
    return sorted(chunk)


def chunked_list(lst, n):
    for i in range(0, len(lst), n):
        yield lst[i:i + n]


def parallel_sort(lst, num_processes=None):
    if num_processes is None:
        num_processes = os.cpu_count() or 1

    chunk_size = len(lst) // num_processes
    chunks = list(chunked_list(lst, chunk_size))

    with Pool(processes=num_processes) as pool:
        sorted_chunks = pool.map(sort_chunk, chunks)

    return list(heapq.merge(*sorted_chunks))


if __name__ == '__main__':
    large_list = sample(range(1000000), 100000)
    sorted_list = parallel_sort(large_list)
    print(sorted_list[:10]) # If you would like to see all the output remove the array slice