Pandas DataFrame Search - is it linear time or constant time?
I have a dataframe object df
with more than 15000 rows, for example:
anime_id name genre rating
1234 Kimi no nawa Romance, Comedy 9.31
5678 Stiens;Gate Sci-fi 8.92
And I am trying to find a string with a specific anime_id.
a_id = "5678"
temp = (df.query("anime_id == "+a_id).genre)
I just wanted to know if this search was done in constant time (like dictionaries) or linear time (like lists).
source to share
This is a very interesting question!
I think it depends on the following aspects:
single row access by index ( index sorted and unique ) must have a runtime O(m)
wherem << n_rows
single row access by index ( index is NOT unique and NOT sorted ) must have a runtimeO(n_rows)
single row access by index ( index is NOT unique and sorted ) must have a runtime O(m)
where `m <n_rows)
accessing rows (regardless of index) using boolean indexing shoudl has a runtime O(n_rows)
Demo:
the index is sorted and unique:
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
the index is NOT sorted and is NOT unique:
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
the index is NOT unique and sorted:
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
source to share
I can't tell you how this is implemented, but after a little test. It seems that the logical dataframe bus looks more like a linear one.
>>> 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
source to share