Refactor the Implementation to Find an Index in a Multi-index Set
As part of the refactoring of MultiIndexSet
class (see Issue #99 (closed)), especially in relation to the separation between the notion of completeness and downward closedness (see Issue #105 (closed)), several internal utility functions shall be refactored.
One of the inner-most utility function related to the checking of downward-closedness is minterpy.jit_compiled_utils.get_match_idx()
. The function takes an array of lexicographically sorted multi-indices and an index element, and return the position of the index if found (and -1
otherwise).
The implementation exploits the fact that the indices must already be lexicographically sorted and do, in principle, a linear search, searching from bottom to the top.
However, if we really want to exploit the fact that the indices are already sorted, it might be better to use binary search (whose time complexity is better) instead.
An implementation of a binary index search seems to work better. See table below for time comparison (m
and n
are the spatial dimension and polynomial degree, respectively; all is with respect to l_p
-degree of \infty
).
m |
n |
number of indices | Linear search | Binary search |
---|---|---|---|---|
3 | 6 | 3.43e+02 | 8.82149e-06 | 2.14576721e-06 |
3 | 8 | 7.29e+02 | 3.81470e-06 | 1.19209290e-06 |
3 | 10 | 1.33e+03 | 5.00679e-06 | 9.53674316e-07 |
6 | 6 | 1.18e+05 | 3.81947e-04 | 2.14576721e-06 |
6 | 8 | 5.31e+05 | 3.01123e-04 | 2.62260437e-06 |
6 | 10 | 1.77e+06 | 7.67112e-03 | 2.86102295e-06 |
7 | 6 | 8.24e+05 | 3.73840e-04 | 4.76837158e-06 |
7 | 8 | 4.78e+06 | 2.39511e-02 | 4.76837158e-06 |
7 | 10 | 1.95e+07 | 9.36909e-02 | 1.00135803e-05 |
Now in the scale of things, this such a speedup may not matter much (I don't know). But it's not a bad idea to implement this anyway.