多个列表排序的最快方法 - Python

Question

我有两个列表 x 和 y，我想对 x 进行排序，并通过 x 排序的排列方式重新排列 y。 例如，给定：

x = [4, 2, 1, 3]
y = [40, 200, 1, 30]

我想获取

x_sorted = [1,2,3,4]
y_sorted = [1, 200, 30, 40]

正如在过去的问题中讨论的那样，解决这个问题的简单方法是

x_sorted, y_sorted = zip(*sorted(zip(x,y)))

我的问题是：最快的方法是什么？

---

我有三种方法可以完成这个任务。

import numpy as np
x = np.random.random(1000)
y = np.random.random(1000)

方法1：

x_sorted, y_sorted = zip(*sorted(zip(x,y))) #1.08 ms 

方法二：

foo = zip(x,y)
foo.sort()
zip(*foo)       #1.05 ms

方法三;

ind = range(1000)
ind.sort(key=lambda i:x[i])
x_sorted = [x[i] for i in ind]
y_sorted = [y[i] for i in ind]  #934us

是否有一种比上述三种方法执行更快的更好的方法？

---

其他问题。

1. 为什么方法2虽然使用了排序方法但不比方法1快？
2. 如果我单独执行方法2，它会更快。在IPython终端中，

我有

%timeit foo = zip(x,y)   #1000 loops, best of 3: 220 us per loop
%timeit foo.sort()       #10000 loops, best of 3: 78.9 us per loop
%timeit zip(*foo)        #10000 loops, best of 3: 73.8 us per loop

- ywat

Answer 1

使用 numpy.argsort：

>>> import numpy as np
>>> x = np.array([4,2,1,3])
>>> y = np.array([40,200,1,30])
>>> order = np.argsort(x)
>>> x_sorted = x[order]
>>> y_sorted = y[order]
>>> x_sorted
array([1, 2, 3, 4])
>>> y_sorted
array([  1, 200,  30,  40])

---

>>> timeit('order = np.argsort(x); x_sorted = x[order]; y_sorted = y[order]', 'from __main__ import x, y, np', number=1000)
0.030632019043

注意

如果输入数据已经是numpy数组，则这样做是有意义的。

- falsetru

---

这里显然是个伟大的、明显的赢家 :) - Roman Pekar

Answer 2

你没有正确计时

%timeit foo.sort()

在第一个循环之后，剩余部分已经排序完成。对于预先排序的列表，Timsort非常高效。 我有些惊讶@Roman使用键函数会更快。您可以通过使用itemgetter进一步改进。

from operator import itemgetter
ig0 = itemgetter(0)
zip(*sorted(zip(x, y), key=ig0))

这比对1000个元素的列表使用lambda函数要快大约9%。

- John La Rooy

---

很好，我检查了你的解决方案，它给出了0.7580892901514744，+1分给你。 - Roman Pekar

Answer 3

>>> x = [4, 2, 1, 3]
>>> y = [40, 200, 1, 30]    
>>> x_sorted, y_sorted = zip(*sorted(zip(x, y), key=lambda a:a[0]))
>>> x_sorted
(1, 2, 3, 4)
>>> y_sorted
(1, 200, 30, 40)

性能：

>>> timeit('foo = zip(x,y); foo.sort(); zip(*foo)', 'from __main__ import x, y', number=1000)
1.0197240443760691
>>> timeit('zip(*sorted(zip(x,y)))', 'from __main__ import x, y', number=1000)
1.0106219310922597
>>> timeit('ind = range(1000); ind.sort(key=lambda i:x[i]); x_sorted = [x[i] for i in ind]; y_sorteds = [y[i] for i in ind]', 'from __main__ import x, y', number=1000)
0.9043525504607857
>>> timeit('zip(*sorted(zip(x, y), key=lambda a:a[0]))', 'from __main__ import x, y', number=1000)
0.8288150863453723

为了全面了解情况，请参阅完整图片：

>>> timeit('sorted(x)', 'from __main__ import x, y', number=1000)
0.40415491505723367            # just getting sorted list from x
>>> timeit('x.sort()', 'from __main__ import x, y', number=1000)
0.008009909448446706           # sort x inplace

@falsetru 方法 - 对于np.array来说最快的方法

>>> timeit('order = np.argsort(x); x_sorted = x[order]; y_sorted = y[order]', 'from __main__ import x, y, np', number=1000)
0.05441799872323827

正如@AshwiniChaudhary在评论中建议的那样，对于列表，可以使用itertools.izip代替zip来加快速度:

>>> timeit('zip(*sorted(izip(x, y), key=itemgetter(0)))', 'from __main__ import x, y;from operator import itemgetter;from itertools import izip', number=1000)
0.4265049757161705

- Roman Pekar

---

您可以使用 itertools.izip 进行内部压缩以使其更加高效。 - Ashwini Chaudhary

不要在sorted之外使用izip，因为它返回的是迭代器而不是列表。 - Ashwini Chaudhary

好的，但如果我们只需要得到y_sorted，像这样y_sorted = [k[1] for k in izip(*sorted(izip(x, y), key=itemgetter(0)))]，这个方法会有用吗？ - Roman Pekar

但是这样我们只能得到 y_sorted 而不能得到 x_Sorted。 - Ashwini Chaudhary

@AshwiniChaudhary 是的，我的意思是如果我们根本不需要 x_sorted，只想要 y 排序，那么这是否有用呢？ - Roman Pekar