Jaki jest wpływ nie unikatowych indeksów na wydajność w pandach?

Question

Z dokumentacji pandy wynika, że ​​indeksy o unikalnej wartości sprawiają, że niektóre operacje są wydajne, a nieunikalne indeksy są czasami tolerowane.

Z zewnątrz nie wygląda na to, że nieunikalne wskaźniki są w jakikolwiek sposób wykorzystywane. Na przykład, następujący ix zapytanie jest na tyle powolny, że wydaje się być skanowanie całego dataframe

In [23]: import numpy as np 
In [24]: import pandas as pd 
In [25]: x = np.random.randint(0, 10**7, 10**7) 
In [26]: df1 = pd.DataFrame({'x':x}) 
In [27]: df2 = df1.set_index('x', drop=False) 
In [28]: %timeit df2.ix[0] 
1 loops, best of 3: 402 ms per loop 
In [29]: %timeit df1.ix[0] 
10000 loops, best of 3: 123 us per loop 

(zdaję sobie sprawę, że dwa ix zapytań nie wraca to samo - to tylko przykład, który wzywa do ix na nieunikalnym indeksie pojawia się znacznie wolniej)

Czy istnieje sposób na zachęcenie pand do stosowania szybszych metod wyszukiwania, takich jak wyszukiwanie binarne na nieunikalnych i/lub posortowanych indeksach?

Answer 1

Gdy indeks jest unikalny, pandy używają hashtable do odwzorowania klucza na wartość O (1). Gdy indeks jest nieunikalny i posortowany, pandy używają wyszukiwania binarnego O (logN), gdy indeks jest losowo uporządkowany, pandy muszą sprawdzić wszystkie klucze w indeksie O (N).

Można zadzwonić sort_index metodę:

import numpy as np 
import pandas as pd 
x = np.random.randint(0, 200, 10**6) 
df1 = pd.DataFrame({'x':x}) 
df2 = df1.set_index('x', drop=False) 
df3 = df2.sort_index() 
%timeit df1.loc[100] 
%timeit df2.loc[100] 
%timeit df3.loc[100] 

wynik:

10000 loops, best of 3: 71.2 µs per loop 
10 loops, best of 3: 38.9 ms per loop 
10000 loops, best of 3: 134 µs per loop