title: Comparison of Pandas lookup times
body: <p>After experimenting with timing various types of lookups on a Pandas (0.17.1) DataFrame I am left with a few questions. </p>
  
  <p>Here is the set up...</p>
  
  <pre><code>import pandas as pd
  import numpy as np
  import itertools
  
  letters = [chr(x) for x in range(ord('a'), ord('z'))]
  letter_combinations = [''.join(x) for x in itertools.combinations(letters, 3)]
  
  df1 = pd.DataFrame({
          'value': np.random.normal(size=(1000000)), 
          'letter': np.random.choice(letter_combinations, 1000000)
      })
  df2 = df1.sort_values('letter')
  df3 = df1.set_index('letter')
  df4 = df3.sort_index()
  </code></pre>
  
  <p>So df1 looks something like this...</p>
  
  <pre><code>print(df1.head(5))
  
  
  &gt;&gt;&gt;
    letter     value
  0    bdh  0.253778
  1    cem -1.915726
  2    mru -0.434007
  3    lnw -1.286693
  4    fjv  0.245523
  </code></pre>
  
  <p>Here is the code to test differences in lookup performance...</p>
  
  <pre><code>print('~~~~~~~~~~~~~~~~~NON-INDEXED LOOKUPS / UNSORTED DATASET~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
  %timeit df1[df1.letter == 'ben']
  %timeit df1[df1.letter == 'amy']
  %timeit df1[df1.letter == 'abe']
  
  print('~~~~~~~~~~~~~~~~~NON-INDEXED LOOKUPS / SORTED DATASET~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
  %timeit df2[df2.letter == 'ben']
  %timeit df2[df2.letter == 'amy']
  %timeit df2[df2.letter == 'abe']
  
  print('~~~~~~~~~~~~~~~~~~~~~INDEXED LOOKUPS~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
  %timeit df3.loc['ben']
  %timeit df3.loc['amy']
  %timeit df3.loc['abe']
  
  print('~~~~~~~~~~~~~~~~~~~~~SORTED INDEXED LOOKUPS~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
  %timeit df4.loc['ben']
  %timeit df4.loc['amy']
  %timeit df4.loc['abe']
  </code></pre>
  
  <p>And the results...</p>
  
  <pre><code>~~~~~~~~~~~~~~~~~NON-INDEXED LOOKUPS / UNSORTED DATASET~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  10 loops, best of 3: 59.7 ms per loop
  10 loops, best of 3: 59.7 ms per loop
  10 loops, best of 3: 59.7 ms per loop
  ~~~~~~~~~~~~~~~~~NON-INDEXED LOOKUPS / SORTED DATASET~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  10 loops, best of 3: 192 ms per loop
  10 loops, best of 3: 192 ms per loop
  10 loops, best of 3: 193 ms per loop
  ~~~~~~~~~~~~~~~~~~~~~INDEXED LOOKUPS~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  The slowest run took 4.66 times longer than the fastest. This could mean that an intermediate result is being cached 
  10 loops, best of 3: 40.9 ms per loop
  10 loops, best of 3: 41 ms per loop
  10 loops, best of 3: 40.9 ms per loop
  ~~~~~~~~~~~~~~~~~~~~~SORTED INDEXED LOOKUPS~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  The slowest run took 1621.00 times longer than the fastest. This could mean that an intermediate result is being cached 
  1 loops, best of 3: 259 µs per loop
  1000 loops, best of 3: 242 µs per loop
  1000 loops, best of 3: 243 µs per loop
  </code></pre>
  
  <p>Questions...</p>
  
  <ol>
  <li><p>It's pretty clear why the lookup on the sorted index is so much faster, binary search to get O(log(n)) performance vs O(n) for a full array scan. But, why is the lookup on the sorted non-indexed <code>df2</code> column <em>SLOWER</em> than the lookup on the unsorted non-indexed column <code>df1</code>?</p></li>
  <li><p>What is up with the <code>The slowest run took x times longer than the fastest. This could mean that an intermediate result is being cached</code>. Surely, the results aren't being cached. Is it because the created index is lazy and isn't <em>actually</em> reindexed until needed? That would explain why it is only on the first call to <code>.loc[]</code>.</p></li>
  <li><p>Why isn't an index sorted by default? The fixed cost of the sort can be too much?</p></li>
  </ol>