¿La búsqueda de Pandas DataFrame es tiempo lineal o tiempo constante?

Tengo un df de dataframe de más de 15000 filas como:

 anime_id name genre rating 1234 Kimi no nawa Romance, Comedy 9.31 5678 Stiens;Gate Sci-fi 8.92 

Y estoy tratando de encontrar la fila con un anime_id particular.

 a_id = "5678" temp = (df.query("anime_id == "+a_id).genre) 

Solo quería saber si esta búsqueda se realizó en tiempo constante (como diccionarios) o tiempo lineal (como listas).

¡Esta es una pregunta muy interesante!

Creo que depende de los siguientes aspectos:

el acceso a una fila por índice (el índice está ordenado y es único ) debe tener un tiempo de ejecución O(m) donde m << n_rows

el acceso a una fila por índice (el índice NO es único y NO está ordenado ) debe tener un tiempo de ejecución O(n_rows)

el acceso a una fila por índice (el índice NO es único y está ordenado ) debe tener un tiempo de ejecución O(m) donde `m

accediendo a la (s) fila (s) (independientemente de un índice) por medio del índice booleano shoudl have runtime O(n_rows)


Manifestación:

El índice es ordenado y único:

 In [49]: df = pd.DataFrame(np.random.rand(10**5,6), columns=list('abcdef')) In [50]: %timeit df.loc[random.randint(0, 10**4)] The slowest run took 27.65 times longer than the fastest. This could mean that an intermediate result is being cached. 1000 loops, best of 3: 331 µs per loop In [51]: %timeit df.iloc[random.randint(0, 10**4)] 1000 loops, best of 3: 275 µs per loop In [52]: %timeit df.query("a > 0.9") 100 loops, best of 3: 7.84 ms per loop In [53]: %timeit df.loc[df.a > 0.9] 100 loops, best of 3: 2.96 ms per loop 

El índice NO está ordenado y NO es único:

 In [54]: df = pd.DataFrame(np.random.rand(10**5,6), columns=list('abcdef'), index=np.random.randint(0, 10000, 10**5)) In [55]: %timeit df.loc[random.randint(0, 10**4)] 100 loops, best of 3: 12.3 ms per loop In [56]: %timeit df.iloc[random.randint(0, 10**4)] 1000 loops, best of 3: 262 µs per loop In [57]: %timeit df.query("a > 0.9") 100 loops, best of 3: 7.78 ms per loop In [58]: %timeit df.loc[df.a > 0.9] 100 loops, best of 3: 2.93 ms per loop 

El índice NO es único y está ordenado:

 In [64]: df = pd.DataFrame(np.random.rand(10**5,6), columns=list('abcdef'), index=np.random.randint(0, 10000, 10**5)).sort_index() In [65]: df.index.is_monotonic_increasing Out[65]: True In [66]: %timeit df.loc[random.randint(0, 10**4)] The slowest run took 9.70 times longer than the fastest. This could mean that an intermediate result is being cached. 1000 loops, best of 3: 478 µs per loop In [67]: %timeit df.iloc[random.randint(0, 10**4)] 1000 loops, best of 3: 262 µs per loop In [68]: %timeit df.query("a > 0.9") 100 loops, best of 3: 7.81 ms per loop In [69]: %timeit df.loc[df.a > 0.9] 100 loops, best of 3: 2.95 ms per loop 

No puedo decirle cómo se implementó, pero después de ejecutar una pequeña prueba. Parece que la máscara booleana dataframe más como lineal.

 >>> timeit.timeit('dict_data[key]',setup=setup,number = 10000) 0.0005770014540757984 >>> timeit.timeit('df[df.val==key]',setup=setup,number = 10000) 17.583375428628642 >>> timeit.timeit('[i == key for i in dict_data ]',setup=setup,number = 10000) 16.613936403242406 

Debe tener en cuenta que incluso iloc es aproximadamente 2 órdenes de magnitud más lento que el hashmap cuando su índice es único:

 df = pd.DataFrame(np.random.randint(0, 10**7, 10**5), columns=['a']) %timeit df.iloc[random.randint(0,10**5)] 10000 loops, best of 3: 51.5 µs per loop s = set(np.random.randint(0, 10**7, 10**5)) %timeit random.randint(0,10**7) in s The slowest run took 9.70 times longer than the fastest. This could mean that an intermediate result is being cached. 1000000 loops, best of 3: 615 ns per loop