python - 在数组的两个不同部分中计算重复整数的最快方法

Question

在这段 Python 代码中，

fun 遍历数组 arr 并计算每个部分对的两个数组部分中相同整数的数量。 (它模拟一个矩阵。)这使得 n*(n-1)/2*m 总共进行了比较，给出了 O(n^2) 的时间复杂度。

是否有编程解决方案或重构此问题的方法可以产生相同的结果但降低了时间复杂度？

# n > 500000, 0 < i < n, m = 100
# dim(arr) = n*m, 0 < arr[x] < 4294967311

arr = mp.RawArray(ctypes.c_uint, n*m)

def fun(i):
    for j in range(i-1,0,-1):
        count = 0
        for k in range(0,m):
            count += (arr[i*m+k] == arr[j*m+k])
        if count/m > 0.7:
            return (i,j)
    return ()

• arr 是共享内存数组，因此出于简单性和性能原因，最好将其保持为只读。

• arr 被实现为 multiprocessing 的 1D RawArray。根据我的测试，它具有迄今为止最快的性能。使用 numpy 二维数组，例如，如下所示:

  arr = np.ctypeslib.as_array(mp.RawArray(ctypes.c_uint, n*m)).reshape(n,m)
  

  将提供矢量化功能，但会增加一个数量级的总运行时间 - 250 秒对比 n = 1500 时的 30 秒，总计 733%。

Answer 1

由于您根本无法更改数组特性，我认为您被 O(n^2) 困住了。 numpy 会获得一些矢量化，但会改变其他共享数组的访问权限。从最里面的操作开始:

    for k in range(0,m):
        count += (arr[i][k] == arr[j][k])

将其更改为单行分配:

    count = sum(arr[i][k] == arr[j][k] for k in range(m))

现在，如果这真的是一个数组，而不是列表的列表，使用数组包的矢量化来简化循环，一次一个:

    count = sum(arr[i] == arr[j])   # results in a vector of counts

您现在可以返回 j 索引，其中 count[j]/m > 0.7。请注意，实际上没有必要为每个返回 i:它在函数中是常量，并且调用程序已经具有该值。您的数组包可能有一对可以返回这些索引的矢量化索引操作。如果您使用的是 numpy，那么可以很容易地在本网站上查找它们。