我试图找到一个~8000*8000 pandas df矩阵中每对行的加权jaccard距离。我尝试了以下方法:
import pandas as pd
import numpy as np
def weighted_j_sim(array1, array2):
return np.minimum(array1, array2).sum()/np.maximum(array1, array2).sum()
matrix = pd.DataFrame([[1, 2 ,3],
[2, 1, 1],
[3, 1, 1]])
for index, (name, values) in enumerate(matrix.iterrows()):
for other_index, (other_name, other_values) in enumerate(matrix.iterrows()):
if other_index>index: #dont check self or something already compared
weighted_js = weighted_j_sim(values,
other_values)
和
import pandas as pd
import numpy as np
def weighted_j_sim(array1, array2):
#https://stackoverflow.com/a/71276180/11357695
q = np.concatenate((array1.T, array2.T), axis=1)
return np.sum(np.amin(q,axis=1))/np.sum(np.amax(q,axis=1))
matrix = pd.DataFrame([[1, 2 ,3],
[2, 1, 1],
[3, 1, 1]])
for index, (name, values) in enumerate(matrix.iterrows()):
for other_index, (other_name, other_values) in enumerate(matrix.iterrows()):
if other_index>index: #dont check self or something already compared
weighted_jd = weighted_j_sim(np.array([values.values]),
np.array([other_values.values]))
这是非常缓慢的-任何人都可以建议一些 numpy 魔术应用在这里?
1条答案
按热度按时间ldxq2e6h1#
一个很大的性能问题是代码在Pandas系列对象上执行二次运行时算法,这通常比Numpy数组慢得多。另一个问题是,将同一行多次转换为Numpy数组效率不高。此外,创建多次临时Numpy数组有点昂贵。此外,如果阵列很大,则在同一个阵列中同时运行最小值和最大值可能会效率低下,因为需要将其重新加载到L1缓存。
实现更快
首先要做的是将pandas数组转换为一个连续的Numpy数组。然后,我们可以使用基于编译器的工具,如Numba和Cython,以避免创建许多临时数组并更有效地使用缓存。此外,我们还可以通过在正确的索引处启动第二个循环来轻松删除条件。最重要的是,可以使用多线程(假设
weighted_js
的计算是线程安全的)。下面是一个非常快速的Numba实现:
性能结果
下面是我的i5- 9600 KF处理器在1000 x1000的架构上的性能:
因此,Numba实现比问题中提供的(第一个)实现快**~1660倍**。它能够在65秒内(而不是几十个小时)计算8000 x8000的矩阵。
注意事项及性能提升
请注意,
fastmath
只应在输入没有任何特殊值(如NaN、Inf或subnormals)时使用。它也只有在sum2
永远不为0时才是安全的(因为被零除)。请注意,这可以进一步优化。一种方法是使用 * 循环平铺 *,以便更好地使用CPU缓存。如果算法在目标机器上是内存受限的(在我的机器上就是这种情况),这会快得多。另一种方法是在线程之间进行负载平衡。这将使计算速度提高 * 两倍 *。另一个优化包括使用 *SIMD指令 *。这似乎不可能与Numba(至少不容易也不有效)。您需要使用母语(例如:C/C++)来执行这样的优化。这将使计算速度在大多数机器上快4倍。这两种优化可以结合在一起,使计算速度提高8倍。生成的程序应该能够在 * 最佳时间 * 内计算Jaccard距离(假设需要计算所有距离)。
请注意,使用 * 简单精度 *(以及更一般的小类型)可以使计算速度提高两倍(因此,使用之前的优化可以提高16倍)。