Open DiegoAlbertoTorres opened 3 years ago
xref https://github.com/pandas-dev/pandas/issues/20803 possible implementation via KDTrees: https://github.com/pandas-dev/pandas/issues/9365
Here are the graphiz profiling of the two calls. It appears that most of the bottleneck is in the binary search calls for the partial key lookup so leveraging a new data structure would probably yield a performance improvement.
Full key
Part key
The full-key timing is almost exactly unchanged (.083s), but the partial-indexing timing is down from 4.77s to .289s
Indexing for entries in a series or dataframe with a multi-index has dramatically worse performance when using partial keys.
For example, for a series with a 3-level multi-index,
series[x]
is dramatically slower thanseries[(x,y,z)]
. Please see the session below for a minimal reproduction:From looking at the code, it seems that
BaseMultiIndexCodesEngine
(pandas/_libs/index.pyx) essentially creates a hash table (alibindex.UInt64Engine
) with entries for each full key. This makes full-key lookups fast. Meanwhile, for partial key lookups on a sorted index,MultiIndex._get_level_indexer
will do two binary searches for each provided level of the key.Instead of a flattened-index approach (again, via
libindex.UInt64Engine
), it would be excellent if Pandas implemented nested indeces (nested hash tables, if you will) for this. This would have a small impact on the performance of full key lookups (current lookup complexity is O(1), new complexity would be O(number_of_levels)). However, partial key lookups would greatly benefit, going from O(log(size_of_series)) to O(number_of_levels_in_key).