在Python中对大量数组进行排序的最快方法

Question

我正在尝试在Python中对大量数组进行排序。 我需要一次对超过1100万个数组进行排序。

此外，如果我能够直接获得将对数组进行排序的索引，那就太好了。

因此，目前我正在使用numpy.argsort（），但它在我的计算机上速度太慢（需要一个多小时才能运行）。

同一台计算机上，在R中进行相同的操作大约需要15分钟。

有人能告诉我在Python中更快的方法吗？

谢谢

编辑：

添加示例

如果我有以下数据框：

agg:

x      y        w        z  

1      2        2        5                 
1      2        6        7         
3      4        3        3        
5      4        7        8    
3      4        2        5    
5      9        9        9    

我正在运行以下函数和命令：

def fucntion(group):
    z = group['z'].values   
    w = group['w'].values 
    func = w[np.argsort(z)[::-1]][:7]  #i need top 7 in case there are many  
    return np.array_str(func)[1:-1]

output = agg.groupby(['x,'y']).apply(function).reset_index()

因此，我的输出数据框将如下所示：

output:

x   y   w   

1   2   6,2    
3   4   2,3    
5   4   7    
5   9   9

- user324

---

你的输入是什么？是一个数组列表吗？能否提供一个示例输入案例？ - Divakar

这是 pandas 数据帧的一列。 - user324

请问您能否提供一些样本数据和期望的输出，以及您已经尝试过的内容？ - Alexander

你是否了解argsort函数中的axis参数？ - user2357112

不，我不是。@user2357112。我读了一些关于它的介绍，但我真的不认为它能胜任我的工作。 - user324

Answer 1

如果您需要部分排序索引的情况，可以使用NumPy的argpartition。

在代码中，您可能会遇到麻烦的np.argsort：w[np.argsort(z)[::-1]][:7]，实际上是w[idx]，其中idx = np.argsort(z)[::-1][:7]。

因此，可以使用np.argpartition来计算idx，如下所示 -

idx = np.argpartition(-z,np.arange(7))[:7]

需要使用-z选项，因为默认情况下np.argpartition会尝试按升序获取排序后的索引。因此，为了将其反转，我们对元素取了反。

因此，原始代码中建议的更改应为：

func = w[np.argpartition(-z,np.arange(7))[:7]]

运行时测试 -

In [162]: z = np.random.randint(0,10000000,(1100000)) # Random int array

In [163]: idx1 = np.argsort(z)[::-1][:7]
     ...: idx2 = np.argpartition(-z,np.arange(7))[:7]
     ...: 

In [164]: np.allclose(idx1,idx2) # Verify results
Out[164]: True

In [165]: %timeit np.argsort(z)[::-1][:7]
1 loops, best of 3: 264 ms per loop

In [166]: %timeit np.argpartition(-z,np.arange(7))[:7]
10 loops, best of 3: 36.5 ms per loop

- Divakar

---

这是一个很好的解决方案，但如果在我的数据框中有些数字需要排序的数量少于7，则我认为它将不起作用。(这是可能的。输出最多需要为7) - user324

@GunjanDewan 所以，只需将此处的 7 替换为那个数字？您可以将其保留为变量，并让变量处理它？类似于 n = 5; func = w[np.argpartition(-z,np.arange(n))[:n]]，其中 n 是该变量。 - Divakar

@GunjanDewan 你是在说 z 本身可能少于 7 个元素吗？ - Divakar

是的，z本身可以小于7。但我已经在len（z）上添加了一个变量。我目前正在我的数据集上运行它。我希望它能更快地工作。 - user324

@GunjanDewan 是的，这正是我要建议的，使用 n = min(len(z),7) 然后 func = w[np.argpartition(-z,np.arange(n))[:n]]。我也很想看到你的运行时间结果！保持联系。 - Divakar

@GunjanDewan 很高兴听到这个消息！ - Divakar

Answer 2

Python比R慢得多的原因是，Python不会对变量进行类型转换（即int，string，float），因此每次比较以确定哪个值更大时都要花费时间确定变量类型。

您无法仅使用Python解决此问题，但可以使用Cython包含类型定义（ctypes和psyco也可以执行相同的功能，但我更喜欢Cython）。如何实现这一点的简单示例在http://docs.cython.org/src/quickstart/cythonize.html上。

Cython编译了您的Python文件的.c版本，可以导入该文件而不是.py文件以减少运行时间。使用Cython进行编译的所有可能方法都显示在http://docs.cython.org/src/reference/compilation.html上。

- dan arters

---

你似乎忽略或者错过了提问者正在使用NumPy这一事实。NumPy和R需要进行相似数量的类型检查；它们在排序时只需要检查一次数组元素类型，而不是每次比较都要检查一次。 - user2357112

Answer 3

您的输入和输出有些混淆。请提供一些示例数据。

但是请看：http://pandas.pydata.org/pandas-docs/stable/api.html#reshaping-sorting-transposing Pandas排序已经优化到了极致。请将重点放在序列排序上，因为每个DataFrame列更准确地表示为一个序列。

- feynmanium

---

我已经进一步编辑了它。请告诉我现在是否清晰。 - user324

Gunjan，你在这里尝试做什么？你能口头解释一下你想要它做什么吗？这个例子毫无意义，如果没有对你所想要的东西的解释，那么问题的解决方案就仅限于你的代码。 - feynmanium