7

假设我使用字典表示一个特征向量（为什么？因为我知道这些特征是稀疏的，但是稍后会详细介绍）。

我应该如何实现两个这样的字典的内积（表示，A，B）

我尝试了天真的方法：

for k in A:
  if k in B:
    sum += A[k] * B[k]

但事实证明它很慢。

更多细节：

  • 我使用字典来表示特征，因为

    1. 功能键是字符串
    2. 大约有 20K 个可能的密钥
    3. 每个向量都是稀疏的（例如，大约 1000 个非零元素）。

  • 我对计算 N=2000 个不同字典（即它们的线性内核）的成对内积非常感兴趣。

4

5 回答 5

7

不确定更快，但这是另一种方法：

keys = A.viewkeys() & B.viewkeys()
the_sum = sum(a[k] * b[k] for k in keys)
于 2013-08-16T08:06:51.393 回答
7

嗯，看来您的方法实际上是最适合密集向量的方法：

>>> # Eric's answer
>>> timeit.timeit('sum([A[k]*B[k] for k in set(A.keys()) & set(B.keys())])', setup='A=dict((i,i) for i in xrange(100));B=dict((i,i) for i in xrange(100))', number=10000)
0.4360210521285808

>>> # My comment
>>> timeit.timeit('for k,v in A.iteritems(): sum += v*B.get(k,0)', setup='A=dict((i,i) for i in xrange(100));B=dict((i,i) for i in xrange(100));sum=0', number=10000)
0.4082838999682963

# My comment, more compact
>>> timeit.timeit('sum(v*B.get(k,0) for k,v in A.iteritems())', setup='A=dict((i,i) for i in xrange(100));B=dict((i,i) for i in xrange(100))', number=10000)
0.38053266868496394

>>> #Your approach
>>> timeit.timeit('for k in A: sum += A[k]*B[k] if k in B else 0.', setup='A=dict((i,i) for i in xrange(100));B=dict((i,i) for i in xrange(100));sum=0', number=10000)
0.35574231962510794

>>> # Your approach, more compact
>>> timeit.timeit('sum(A[k]*B[k] for k in A if k in B)', setup='A=dict((i,i) for i in xrange(100));B=dict((i,i) for i in xrange(100))', number=10000)
0.3400850549682559

对于稀疏的，埃里克的答案表现更好，但你的仍然是最快的：

# Mine
>>> timeit.timeit('sum(v*B.get(k,0) for k,v in A.iteritems())', setup='import random;A=dict((i,i) for i in xrange(100) if random.random() < 0.3);B=dict((i,i) for i in xrange(100) if random.random() < 0.2)', number=10000)
0.1390782696843189

# Eric's
>>> timeit.timeit('sum([A[k]*B[k] for k in set(A.keys()) & set(B.keys())])', setup='import random;A=dict((i,i) for i in xrange(100) if random.random() < 0.3);B=dict((i,i) for i in xrange(100) if random.random() < 0.2)', number=10000)
0.11702822992151596

# Yours
>>> timeit.timeit('sum(A[k]*B[k] for k in A if k in B)', setup='import random;A=dict((i,i) for i in xrange(100) if random.random() < 0.3);B=dict((i,i) for i in xrange(100) if random.random() < 0.2)', number=10000)
0.07878250570843193

编辑

折腾了一会儿之后，它似乎sum([x for x ...])比sum(x for x in ...). 用这个和 Janne 对 Eric 答案中键的评论进行重新基准测试，你的仍然是最重要的（Joowani 给出了轻微的改进）：

>>> timeit.timeit('sum([v*B.get(k,0) for k,v in A.items()])', setup='import random;A=dict((i,i) for i in xrange(100) if random.random() < 0.3);B=dict((i,i) for i in xrange(100) if random.random() < 0.2)', number=100000)
1.1604375791416714
>>> timeit.timeit('sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()])', setup='import random;A=dict((i,i) for i in xrange(100) if random.random() < 0.3);B=dict((i,i) for i in xrange(100) if random.random() < 0.2)', number=100000)
0.9234189571552633
>>> timeit.timeit('sum([A[k]*B[k] for k in A if k in B])', setup='import random;A=dict((i,i) for i in xrange(100) if random.random() < 0.3);B=dict((i,i) for i in xrange(100) if random.random() < 0.2)', number=100000)
0.5411289579401455
>>> timeit.timeit('sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A])', setup='import random;A=dict((i,i) for i in xrange(100) if random.random() < 0.3);B=dict((i,i) for i in xrange(100) if random.random() < 0.2)', number=100000)
0.5198972138696263

缩放到非常大的尺寸，您会看到完全相同的模式：

>>> #Mine
>>> timeit.timeit('sum([v*B.get(k,0) for k,v in A.iteritems()])', setup='import random;A=dict((i,i) for i in xrange(10000) if random.random() < 0.1);B=dict((i,i) for i in xrange(10000) if random.random() < 0.2)', number=100000)
45.328807250833506

>>> #Eric's
>>> timeit.timeit('sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()])', setup='import random;A=dict((i,i) for i in xrange(10000) if random.random() < 0.1);B=dict((i,i) for i in xrange(10000) if random.random() < 0.2)', number=100000)
28.042937058640973

>>> #Yours
>>> timeit.timeit('sum([A[k]*B[k] for k in A if k in B])', setup='import random;A=dict((i,i) for i in xrange(10000) if random.random() < 0.1);B=dict((i,i) for i in xrange(10000) if random.random() < 0.2)', number=100000)
16.55080344861699

>>> #Joowani's
>>> timeit.timeit('sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A])', setup='import random;A=dict((i,i) for i in xrange(10000) if random.random() < 0.1);B=dict((i,i) for i in xrange(10000) if random.random() < 0.2)', number=100000)
15.485236119691308

我认为 Joowani 的技巧在这里并没有显着改善它，因为向量的大小大致相同，但根据您的问题（如果某些向量比其他向量小得离谱），这可能更重要......

再次编辑

哎呀，好像我应该在发布之前再喝一杯咖啡......正如 Eric 指出的（虽然我完全错过了......），定义数组在setup所有试验中保持相同，这并不是最好的方法基准。使用适当的随机向量进行测试，结果没有显着差异，但为了完整起见：

>>> timeit.timeit('mine(dict((i,i) for i in xrange(100) if random.random() < 0.3),dict((i,i) for i in xrange(100) if random.random() < 0.2))', setup='import random;joowanis=lambda A,B:sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A]);mine=lambda A,B:sum([v*B.get(k,0) for k,v in A.iteritems()]);erics=lambda A,B:sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()]);yours=lambda A,B:sum([A[k]*B[k] for k in A if k in B])', number=100000)
6.294158102577967
>>> timeit.timeit('erics(dict((i,i) for i in xrange(100) if random.random() < 0.3),dict((i,i) for i in xrange(100) if random.random() < 0.2))', setup='import random;joowanis=lambda A,B:sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A]);mine=lambda A,B:sum([v*B.get(k,0) for k,v in A.iteritems()]);erics=lambda A,B:sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()]);yours=lambda A,B:sum([A[k]*B[k] for k in A if k in B])', number=100000)
6.068052507449011
>>> timeit.timeit('yours(dict((i,i) for i in xrange(100) if random.random() < 0.3),dict((i,i) for i in xrange(100) if random.random() < 0.2))', setup='import random;joowanis=lambda A,B:sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A]);mine=lambda A,B:sum([v*B.get(k,0) for k,v in A.iteritems()]);erics=lambda A,B:sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()]);yours=lambda A,B:sum([A[k]*B[k] for k in A if k in B])', number=100000)
5.745110704570834
>>> timeit.timeit('joowanis(dict((i,i) for i in xrange(100) if random.random() < 0.3),dict((i,i) for i in xrange(100) if random.random() < 0.2))', setup='import random;joowanis=lambda A,B:sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A]);mine=lambda A,B:sum([v*B.get(k,0) for k,v in A.iteritems()]);erics=lambda A,B:sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()]);yours=lambda A,B:sum([A[k]*B[k] for k in A if k in B])', number=100000)
5.737499445367575

缩放：

>>> timeit.timeit('mine(dict((i,i) for i in xrange(10000) if random.random() < 0.1),dict((i,i) for i in xrange(10000) if random.random() < 0.2))', setup='import random;joowanis=lambda A,B:sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A]);mine=lambda A,B:sum([v*B.get(k,0) for k,v in A.iteritems()]);erics=lambda A,B:sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()]);yours=lambda A,B:sum([A[k]*B[k] for k in A if k in B])', number=1000)
5.0510995368395015
>>> timeit.timeit('erics(dict((i,i) for i in xrange(10000) if random.random() < 0.1),dict((i,i) for i in xrange(10000) if random.random() < 0.2))', setup='import random;joowanis=lambda A,B:sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A]);mine=lambda A,B:sum([v*B.get(k,0) for k,v in A.iteritems()]);erics=lambda A,B:sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()]);yours=lambda A,B:sum([A[k]*B[k] for k in A if k in B])', number=1000)
4.350612399185138
>>> timeit.timeit('yours(dict((i,i) for i in xrange(10000) if random.random() < 0.1),dict((i,i) for i in xrange(10000) if random.random() < 0.2))', setup='import random;joowanis=lambda A,B:sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A]);mine=lambda A,B:sum([v*B.get(k,0) for k,v in A.iteritems()]);erics=lambda A,B:sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()]);yours=lambda A,B:sum([A[k]*B[k] for k in A if k in B])', number=1000)
4.15619379016789
>>> timeit.timeit('joowanis(dict((i,i) for i in xrange(10000) if random.random() < 0.1),dict((i,i) for i in xrange(10000) if random.random() < 0.2))', setup='import random;joowanis=lambda A,B:sum([A[k]*B[k] for k in A if k in B]) if len(A)<len(B) else sum([A[k]*B[k] for k in B if k in A]);mine=lambda A,B:sum([v*B.get(k,0) for k,v in A.iteritems()]);erics=lambda A,B:sum([A[k]*B[k] for k in A.viewkeys() & B.viewkeys()]);yours=lambda A,B:sum([A[k]*B[k] for k in A if k in B])', number=1000)
4.185129374341159

我认为底线是你不能指望通过巧妙地重新排序这种事情的表达式来显着加速......也许你可以尝试在 C/Cython 中做数字部分或使用Scipy 的 Sparse包？

于 2013-08-16T08:24:33.890 回答
2

在 A 比 B 长得多的情况下，这可能会有所帮助吗？

if len(A) > len(B):
    A, B = B, A

for k in A:
    if k in B:
        the_sum += A[k] * B[k]
于 2013-08-16T08:31:34.233 回答
1

这是我的答案（根据@valentin-clement 的建议）：

首先我包装一个 scipy.sparse dok_matrix。这个想法是为每个可能的特征分配一个索引。

import scipy.sparse as sps
import numpy as np

class MSK:
    # DD is a dict of dict, whose values are of type float.
    # features - the set of possible features keys
    def __init__(self, DD, features):
        self.features = {k: j for (j, k) in enumerate(features)}
        self.strings = DD.keys()
        n = len(self.strings)
        d = len(self.features)
        self.M = sps.dok_matrix((n, d), dtype=np.float64)
        for (i, s) in enumerate(self.strings):
            v = DD[s]
            for k in v:
                j = self.features[k]
                self.M[i, j] = v[k]

并且我们使用下面的代码进行测试，其中元素的数量是 800，维度也是 800，但是稀疏度是 200（正好 200 个元素是非零的）。

np.random.seed(1)
N = 800
DD = dict()
R = range(N)
for i in xrange(N):
    DD[i] = dict()
    S = np.random.permutation(R)
    S = S[:N/4]
    for j in S:
        DD[i][j] = np.random.randn(1)[0]

K = MSK(DD, R)
import cProfile
cProfile.runctx("A = K.M * K.M.T", globals(), locals())
print A.todense()

输出是：

2080520 function calls (2080519 primitive calls) in 2.884 seconds

让我们说3秒。我的幼稚实现（使用@Joowani 的 if 语句）大约需要 19 秒。

（MSK 代表 MatrixSparseKeys）

于 2013-08-17T06:30:40.707 回答
1

您应该尝试使用 namedtuples 而不是 dict。

from collections import namedtuple
A = dict
B = dict
_A = namedtuple('_A', A.keys())
_B = namedtuple('_B', B.keys())
DictA = _A(**A)
DictB = _B(**B)

然后将它们用作字典。此处有关命名元组的更多信息：Python 中的“命名元组”是什么？

于 2013-08-16T08:21:28.387 回答