title: How to efficiently compute the inner product of two dictionaries
body: <p>Suppose I represent a feature vector using a dictionary (why? because I know the features are sparse, but, more on that later).</p>
  
  <p>How should I implement the inner product of two such dictionaries (denoted, A, B)</p>
  
  <p>I tried the naive approach:</p>
  
  <pre><code>for k in A:
    if k in B:
      sum += A[k] * B[k]
  </code></pre>
  
  <p>but it turns out to be slow.</p>
  
  <p>Some more details:</p>
  
  <ul>
  <li><p>I'm using a dictionary to represent features because</p>
  
  <ol>
  <li>The feature keys are strings</li>
  <li>There are ~20K possible keys</li>
  <li>Each vector is sparse (say, about 1000 non-zero elements).</li>
  </ol></li>
  <li><p>I'm really interested in computing the pairwise inner product of N=2000 different dictionaries (that is, their linear kernel).</p></li>
  </ul>