Python：通过两个元素高效排序元组列表

Question

我有一个非常大的元组列表，我想根据两个元素来排序。例如：

List = [('chr1', 34234, 'extrainfo'), ('chr1', 1234, 'extrainfo'), ('chr3', 4234, 'extrainfo'), ('chr1', 3241, 'extrainfo')]

这是一个非常大的列表，我想用以下方式进行排序：

List = sorted(List, key=lambda i: (i[0], int[1])))

在处理像上面这个小列表时，这个方法效果很好。但是，当我用更大的数据集运行我的代码时，我遇到了内存错误：

Python(32306) malloc: *** mmap(size=34684928) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
Traceback (most recent call last):
  File "MyCode.py", line 139, in <module>
    List = sorted(List, key=lambda i: (i[0], int(i[1])))
MemoryError

Answer 1

对于大数据集来说，使用结构化数组可能会更有效，因为它们比列表更快。

http://docs.scipy.org/doc/numpy/user/basics.rec.html

http://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html

Answer 2

你有两个选择：

1. 增加内存的大小。

2. 尝试一次处理少量数据，特别是如果你在处理大量文本或数据的时候，似乎是这样的。

你似乎有一些相似的键值。所以可以试试使用从collections模块导入的特征计数器。如果额外的信息不同，那你可以考虑使用嵌套结构。

这样可以帮你省去很多麻烦。

Answer 3

这里有一些你可以尝试的方法，按照难度和效果大致排序。

• 不要用 sorted() 创建一个排序后的列表副本。相反，直接用 List.sort() 在原列表上进行排序。

• 对列表进行两次排序，第一次用 key=lambda i: i[1]，第二次用 key=lambda i: i[0]。这样做会花更多时间，但每次排序时需要的空间会更少。Python 从 2.2 版本开始保证排序是稳定的。按照重要性反向排序的方式是我们以前只能按一个关键字排序时的做法。

• 完全不使用关键字函数。默认情况下，按元组中的项目顺序排序就是这样！如果你不在意第三个及后续项目的顺序，那就让 Python 自己去排序吧！它们也会有序，但这也没什么不好。（如果其他元素是无法比较的类型，这种方法就不适用了。）

• 如果你的 Python 版本足够老，可以使用 cmp 函数，而不是 key 函数。这样可以避免生成关键字列表，但会比较慢，并且在 Python 3 中不适用。

• 在 64 位操作系统上使用 64 位版本的 Python，并确保机器有足够的内存。

• 自己实现一个排序算法。