title: Python dictionary lookup speed with NumPy datatypes
body: <p><strong>BACKGROUND</strong></p>
  
  <p>I have a lot of numeric message codes in a NumPy array, and I'd need to convert them into strings fast. I have had some problems with the performance and would like to understand why and how to make it quick.</p>
  
  <p><strong>SOME BENCHMARKS</strong></p>
  
  <p><strong>I - The trivial approach</strong></p>
  
  <pre><code>import numpy as np
  
  # dictionary to use as the lookup dictionary
  lookupdict = {
       1: "val1",
       2: "val2",
      27: "val3",
      35: "val4",
      59: "val5" }
  
  # some test data
  arr = np.random.choice(lookupdict.keys(), 1000000)
  
  # create a list of words looked up
  res = [ lookupdict[k] for k in arr ]
  </code></pre>
  
  <p>The dictionary lookup takes the better part of my coffee break, 758 ms. (I also tried <code>res = map(lookupdict.get, arr)</code> but that's even worse.)</p>
  
  <p><strong>II - Without NumPy</strong></p>
  
  <pre><code>import random
  
  # dictionary to use as the lookup dictionary
  lookupdict = {
       1: "val1",
       2: "val2",
      27: "val3",
      35: "val4",
      59: "val5" }
  
  # some test data
  arr = [ random.choice(lookupdict.keys()) for _ in range(1000000) ]
  
  # create a list of words looked up
  res = [ lookupdict[k] for k in arr ]
  </code></pre>
  
  <p>The timing results change quite considerably to 76 ms!</p>
  
  <p>It should be noted that I am interested in timing the lookup. The random generation is just to create some test data. It is not interesting whether it takes a lot of time or not. All benchmark results given here are only for the one million lookups.</p>
  
  <p><strong>III - Convert NumPy array to a list</strong></p>
  
  <p>My first guess was that this has something to do with list vs. array problems. However, by modifying the NumPy version to use lists:</p>
  
  <pre><code>res = [ lookupdict[k] for k in list(arr) ]
  </code></pre>
  
  <p>gives me 778 ms, of which around 110 ms is spent converting the list and 570 ms doing the lookup. So, the lookup is a bit faster, but the total time is the same.</p>
  
  <p><strong>IV - Type conversion from <code>np.int32</code> to <code>int</code></strong></p>
  
  <p>As the only other difference seems to be the data type (<code>np.int32</code> vs. <code>int</code>), I tried converting the types on-the-fly. This is a bit stupid, as probably dict does the same:</p>
  
  <pre><code>res = [ lookupdict[int(k)] for k in arr ]
  </code></pre>
  
  <p>However, this seems to do something interesting, because the time drops to 266 ms. It seems that almost-but-not-quite-the-same datatypes play nasty tricks with dictionary lookups and that dict code is not very efficient with conversions. </p>
  
  <p><strong>V - Dictionary key conversion to <code>np.int32</code></strong></p>
  
  <p>To test this, I modified the NumPy version to use exactly the same data type in dict keys and lookup:</p>
  
  <pre><code>import numpy as np
  
  # dictionary to use as the lookup dictionary
  lookupdict = {
       np.int32(1): "val1",
       np.int32(2): "val2",
      np.int32(27): "val3",
      np.int32(35): "val4",
      np.int32(59): "val5" }
  
  # some test data
  arr = np.random.choice(lookupdict.keys(), 1000000)
  
  # create a list of words looked up
  res = [ lookupdict[k] for k in arr ]
  </code></pre>
  
  <p>This improved to 177 ms. Not an insignificant improvement but a far cry form the 76 ms. </p>
  
  <p><strong>VI - Array conversion to use <code>int</code> objects</strong></p>
  
  <pre><code>import numpy as np
  
  # dictionary to use as the lookup dictionary
  lookupdict = {
       1: "val1",
       2: "val2",
      27: "val3",
      35: "val4",
      59: "val5" }
  
  # some test data
  arr = np.array([ random.choice(lookupdict.keys()) for _ in range(1000000) ], 
                 dtype='object')
  
  # create a list of words looked up
  res = [ lookupdict[k] for k in arr ]
  </code></pre>
  
  <p>This gives 86 ms, which is already very close to the native Python 76 ms.</p>
  
  <p><strong>Result summary</strong></p>
  
  <ol>
  <li>dict keys <code>int</code>, indexing with <code>int</code> (native Python): 76 ms</li>
  <li>dict keys <code>int</code>, indexing with <code>int</code> objects (NumPy): 86 ms</li>
  <li>dict keys <code>np.int32</code>, indexing with <code>np.int32</code>: 177 ms</li>
  <li>dict keys <code>int</code>, indexing with <code>np.int32</code>: 758 ms</li>
  </ol>
  
  <p><strong>QUESTION(S)</strong> </p>
  
  <p>Why? And what can I do to make the dictionary lookups as fast as possible? My input data is a NumPy array, so the best (fastest but ugly) this far is to convert the dict keys into <code>np.int32</code>. (Unfortunately, the dict keys may be spread over a wide range of numbers, so indexing array-by-array is not a viable alternative. Fast it would be though, 10 ms.)</p>