我想知道是否有任何有效的算法来计算大量整数数组之间匹配的整数的数量。Cython中的代码如下所示。match_ints.pyx
cimport cython
from libc.stdlib cimport calloc, free
import numpy as np
cimport numpy as np
np.import_array()
@cython.wraparound(False)
@cython.boundscheck(False)
@cython.initializedcheck(False)
cdef void count_matches(int[:, ::1] target_arrays, int[::1] ref_array, int[::1] num_matches):
cdef:
Py_ssize_t i, j
Py_ssize_t n = target_arrays.shape[0]
Py_ssize_t c = target_arrays.shape[1]
Py_ssize_t nf = ref_array.shape[0]
Py_ssize_t m = ref_array[nf - 1] + 5
int * ind = <int *> calloc(m, sizeof(int))
int k, g
for i in range(nf):
ind[ref_array[i]] = 1
for i in range(n):
k = 0
for j in range(c):
g = target_arrays[i, j]
if g < m and ind[g] == 1:
k += 1
num_matches[i] = k
free(ind)
cpdef count_num_matches(int[:, ::1] target_arrays, int[::1] ref_array):
cdef:
Py_ssize_t n = target_arrays.shape[0]
int[::1] num_matches = np.zeros(n, dtype=np.int32)
count_matches(target_arrays, ref_array, num_matches)
return np.asarray(num_matches)
这里的想法很简单。对于要匹配的引用整数数组,它按升序排序(通过sort
方法)。利用数组中的整数不大的优点,创建了一个指示符数组ind
,其长度为参考数组的最大整数(+5
,以避免索引超出范围)。因此,每个整数都被认为是一个索引,并且ind
中的相应位置被分配为1。然后遍历每一个target_array
来计算引用数组中匹配的整数的个数。
在匹配过程中,如果ind
中的索引为1
,则target_arrays
中的所有整数都被视为索引并匹配。
测试方法设置为test_main_counts.py
。
# test_main_counts.py
from match_ints import count_num_matches
import numpy as np
def count_num_matches_main():
x = np.random.randint(50, 6000, size=(1000000, 40), dtype=np.int32)
ref_x = np.random.randint(100, 2500, size=800, dtype=np.int32)
ref_x.sort()
return count_num_matches(x, ref_x)
if __name__ == "__main__":
nums = count_num_matches_main()
print(nums[:10])
setup
文件。
from setuptools import setup
from Cython.Build import cythonize
import numpy as np
setup(
ext_modules=cythonize(
"match_ints.pyx",
compiler_directives={
"language_level": "3",
}
),
include_dirs=[
np.get_include()
]
)
因为所有的整数都不是很大,并且有很多重复(在我的真实的应用中,数百万个数组只包含几千个唯一整数),所以有没有相关的算法可以通过例如利用更少的唯一整数来改善这类问题?
2条答案
按热度按时间kxxlusnw1#
target_arrays is fixed
-很漂亮!在这种情况下,您可以预先处理目标数组并构建一种“反向索引”(搜索引擎和数据库领域的概念)。对于每个可能的值,创建包含该值的目标数组的索引数组,如下所示:
现在,对于
ref_arr
中的每个元素,相应数组的递增计数器对于较短的目标数组(在示例中为40个),
inverted[]
的子列表应该很短,这样你会获得显著的收益:从当前主导的O(n*c)
复杂度到O(nf*mean_sublist_size)
简单的Python实现。
我在
targets
中删除了重复的内容,但为了简单起见,不在ref
中处理它们。vlju58qv2#
正如评论中所建议的,将内容计数到dict中,对dict.keys()使用集合操作,从结果dict中找到具有最小出现次数的公共键/删除唯一键。
你可以避免排序+遍历,在构建字典时只遍历。通过使用一组“seen_keys”,你可以忽略后面列表中还没有被看到的值:
输出: