python - 将两个参数函数应用于列表以使用 NumPy 生成对称矩阵

Question

我有一个对称函数 get_corr，它使用两个字符串，并返回一个 double 值。

def get_corr(id1, id2):
    # some magic to find double x
    #...
    return x

我还有一个字符串列表 factors，我想用它生成一个大小为 len(factors)xlen(factors)< 的对称矩阵 通过将 get_corr 应用于 factors 与自身的笛卡尔积。

这将非常简单，只需使用嵌套的 for 循环，遍历 factors 的索引，为每个位置调用 get_corr。

corr_matr = np.identity(factor_length)
for i in factor_length:
    for j in factor_length:
        corr_matr[i,j] = corr_matr[j,i] = get_corr(factors[i], factors[j])

但是我觉得这一定有一些 NumPy 语法糖 - 是吗？我不认为它可以更快，但也许我错了。为此目的嵌套 for 循环似乎没有必要。我尝试使用 np.frompyfunc 并在 itertools.product 上调用它，但这看起来更糟，因为我将调用 get_corr 两次多次。此外，我无法使用 itertools.product 生成的元组序列正确矢量化该函数。

Answer 1

据我所知，在 numpy 中没有任何东西可以提高性能。 Numpy 非常快一旦您创建了一个数值数组。如果您有一个字符串列表和一个映射函数 string -> double，那么您将不得不遍历这些条目。

一个选择是将您的映射转换为 Cython，并在其中写入转换，这可能会加快速度。

如果你想坚持使用 python 代码，itertools 有一些有趣的工具。正如您提到的，product 可能不会提供任何改进，因为您必须进行两次 map 计算(而且它是对称的)。但是，combinations 和 combinations_with_replacement 对我来说似乎是不错的选择。

如果您的相关函数总是将自相关映射到 1 (get_corr(i, i) = 1) 则使用组合，因为它会忽略对角元素，如果没有，使用 combinations_with_replacement。

---

让我定义一个虚拟的类似相关性的字符串映射函数 -> double:

def get_corr(id1, id2):
    diff = len(id1) - len(id2)
    return 1. / (1. + diff * diff)

该函数既对称又测量相似性(1 表示长度相同的字符串，< 1 表示不同的字符串)。

字符串生成器函数(在 random strings 之后):

def random_strings(N, R):
    return [''.join(choice(string.ascii_uppercase + string.digits) 
                    for _ in range(randint(1, R)))
            for _ in range(N)]

还有几个测试函数，你的:

def test1(data):
    N = len(data)
    corr_matr = np.identity(N)
    for i in xrange(N):
        for j in xrange(N):
            corr_matr[i,j] = corr_matr[j,i] = get_corr(data[i], data[j])
    return corr_matr

并使用组合:

def test2(data):
    N = len(data)
    corr_matr = np.identity(N)
    for (i, j) in combinations(xrange(N), 2):
        corr_matr[i,j] = corr_matr[j,i] = get_corr(data[i], data[j])
    return corr_matr

现在使用 100 个随机字符串进行一些基准测试:

>>> data = random_strings(100, 10) # 100 random strings
>>> %timeit -n3 test1(data)
3 loops, best of 3: 5.24 ms per loop
>>> %timeit -n3 test2(data)
3 loops, best of 3: 2.29 ms per loop

和 1000 个随机字符串:

>>> data = random_strings(1000, 10) # 1000 random strings
>>> %timeit -n3 test1(data)
3 loops, best of 3: 452 ms per loop
>>> %timeit -n3 test2(data)
3 loops, best of 3: 232 ms per loop

使用 itertools(具有相当简单的映射函数)速度是原来的两倍。