Skip to content

Instantly share code, notes, and snippets.

@jaimefrio
Last active August 29, 2015 13:55
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jaimefrio/8704101 to your computer and use it in GitHub Desktop.
`np.searchsorted` benchmarks
-----------------+------------------------+------------------------
searchsorted | floats | ints
-----------------+------------------------+------------------------
haystack needle | old new gain | old new gain
-----------------+------------------------+------------------------
5 2 | 1.60e-06 1.64e-06 1.0x | 1.64e-06 1.64e-06 1.0x
5 10 | 1.65e-06 1.65e-06 1.0x | 1.64e-06 1.64e-06 1.0x
5 50 | 2.21e-06 2.03e-06 1.1x | 2.11e-06 1.69e-06 1.2x
5 200 | 4.98e-06 3.05e-06 1.6x | 4.53e-06 2.56e-06 1.8x
5 1000 | 2.54e-05 1.03e-05 2.5x | 2.12e-05 8.39e-06 2.5x
5 5000 | 1.33e-04 7.67e-05 1.7x | 1.10e-04 6.59e-05 1.7x
5 20000 | 5.39e-04 3.22e-04 1.7x | 4.41e-04 2.69e-04 1.6x
20 2 | 1.57e-06 1.64e-06 1.0x | 1.64e-06 1.65e-06 1.0x
20 10 | 1.65e-06 1.66e-06 1.0x | 1.64e-06 1.64e-06 1.0x
20 50 | 2.72e-06 2.11e-06 1.3x | 2.68e-06 1.94e-06 1.4x
20 200 | 7.42e-06 3.95e-06 1.9x | 6.99e-06 3.05e-06 2.3x
20 1000 | 4.56e-05 1.80e-05 2.5x | 3.79e-05 1.69e-05 2.2x
20 5000 | 2.30e-04 1.34e-04 1.7x | 1.92e-04 1.11e-04 1.7x
20 20000 | 9.30e-04 5.53e-04 1.7x | 7.67e-04 4.47e-04 1.7x
100 2 | 1.66e-06 1.66e-06 1.0x | 1.64e-06 1.65e-06 1.0x
100 10 | 1.83e-06 1.67e-06 1.1x | 1.77e-06 1.64e-06 1.1x
100 50 | 3.29e-06 2.46e-06 1.3x | 3.50e-06 2.05e-06 1.7x
100 200 | 1.15e-05 5.02e-06 2.3x | 1.03e-05 3.76e-06 2.7x
100 1000 | 7.24e-05 3.41e-05 2.1x | 5.90e-05 3.10e-05 1.9x
100 5000 | 3.67e-04 2.18e-04 1.7x | 2.98e-04 1.73e-04 1.7x
100 20000 | 1.47e-03 8.82e-04 1.7x | 1.20e-03 7.00e-04 1.7x
500 2 | 1.65e-06 1.64e-06 1.0x | 1.64e-06 1.64e-06 1.0x
500 10 | 2.02e-06 1.67e-06 1.2x | 1.86e-06 1.64e-06 1.1x
500 50 | 3.81e-06 2.52e-06 1.5x | 4.27e-06 2.18e-06 2.0x
500 200 | 1.80e-05 6.07e-06 3.0x | 1.41e-05 4.79e-06 2.9x
500 1000 | 1.07e-04 5.84e-05 1.8x | 7.96e-05 4.50e-05 1.8x
500 5000 | 5.40e-04 3.20e-04 1.7x | 3.99e-04 2.46e-04 1.6x
500 20000 | 2.18e-03 1.30e-03 1.7x | 1.62e-03 1.01e-03 1.6x
2000 2 | 1.64e-06 1.65e-06 1.0x | 1.64e-06 1.64e-06 1.0x
2000 10 | 2.05e-06 1.68e-06 1.2x | 2.05e-06 1.64e-06 1.2x
2000 50 | 4.50e-06 2.89e-06 1.6x | 5.02e-06 2.47e-06 2.0x
2000 200 | 2.37e-05 7.44e-06 3.2x | 1.78e-05 5.67e-06 3.1x
2000 1000 | 1.32e-04 7.73e-05 1.7x | 9.88e-05 5.97e-05 1.7x
2000 5000 | 6.69e-04 4.11e-04 1.6x | 5.05e-04 3.18e-04 1.6x
2000 20000 | 2.69e-03 1.66e-03 1.6x | 2.06e-03 1.30e-03 1.6x
10000 2 | 1.66e-06 1.64e-06 1.0x | 1.64e-06 1.64e-06 1.0x
10000 10 | 2.16e-06 2.03e-06 1.1x | 2.28e-06 1.74e-06 1.3x
10000 50 | 5.92e-06 3.34e-06 1.8x | 5.86e-06 2.74e-06 2.1x
10000 200 | 3.21e-05 1.05e-05 3.1x | 2.34e-05 7.30e-06 3.2x
10000 1000 | 1.65e-04 9.75e-05 1.7x | 1.25e-04 7.72e-05 1.6x
10000 5000 | 8.36e-04 5.16e-04 1.6x | 6.37e-04 4.10e-04 1.6x
10000 20000 | 3.34e-03 2.08e-03 1.6x | 2.56e-03 1.67e-03 1.5x
-----------------+------------------------+------------------------
argsearchsorted | floats | ints
-----------------+------------------------+------------------------
haystack needle | old new gain | old new gain
-----------------+------------------------+------------------------
5 2 | 1.64e-06 1.72e-06 1.0x | 1.64e-06 1.65e-06 1.0x
5 10 | 1.64e-06 1.68e-06 1.0x | 1.65e-06 1.65e-06 1.0x
5 50 | 2.47e-06 2.33e-06 1.1x | 2.30e-06 2.05e-06 1.1x
5 200 | 5.50e-06 4.08e-06 1.3x | 4.40e-06 3.38e-06 1.3x
5 1000 | 2.85e-05 1.71e-05 1.7x | 2.18e-05 1.24e-05 1.8x
5 5000 | 1.46e-04 1.09e-04 1.3x | 1.16e-04 9.02e-05 1.3x
5 20000 | 5.95e-04 4.60e-04 1.3x | 4.61e-04 3.68e-04 1.3x
20 2 | 1.65e-06 1.72e-06 1.0x | 1.64e-06 1.64e-06 1.0x
20 10 | 1.95e-06 2.01e-06 1.0x | 1.87e-06 1.78e-06 1.0x
20 50 | 3.06e-06 2.57e-06 1.2x | 2.67e-06 2.38e-06 1.1x
20 200 | 8.32e-06 5.53e-06 1.5x | 6.09e-06 4.14e-06 1.5x
20 1000 | 5.04e-05 2.80e-05 1.8x | 3.95e-05 2.30e-05 1.7x
20 5000 | 2.56e-04 1.89e-04 1.4x | 1.99e-04 1.50e-04 1.3x
20 20000 | 1.03e-03 7.74e-04 1.3x | 8.05e-04 6.19e-04 1.3x
100 2 | 1.64e-06 1.67e-06 1.0x | 1.65e-06 1.65e-06 1.0x
100 10 | 2.05e-06 2.05e-06 1.0x | 2.05e-06 1.88e-06 1.1x
100 50 | 3.74e-06 3.01e-06 1.2x | 3.28e-06 2.49e-06 1.3x
100 200 | 1.23e-05 7.14e-06 1.7x | 9.10e-06 5.36e-06 1.7x
100 1000 | 8.06e-05 5.11e-05 1.6x | 6.43e-05 4.12e-05 1.6x
100 5000 | 4.08e-04 3.06e-04 1.3x | 3.26e-04 2.35e-04 1.4x
100 20000 | 1.63e-03 1.25e-03 1.3x | 1.33e-03 9.79e-04 1.4x
500 2 | 1.65e-06 1.66e-06 1.0x | 1.65e-06 1.64e-06 1.0x
500 10 | 2.07e-06 2.05e-06 1.0x | 2.06e-06 2.04e-06 1.0x
500 50 | 4.39e-06 3.34e-06 1.3x | 3.79e-06 2.88e-06 1.3x
500 200 | 1.91e-05 1.00e-05 1.9x | 1.37e-05 6.60e-06 2.1x
500 1000 | 1.20e-04 8.23e-05 1.5x | 9.37e-05 6.45e-05 1.5x
500 5000 | 6.02e-04 4.48e-04 1.3x | 4.66e-04 3.41e-04 1.4x
500 20000 | 2.43e-03 1.82e-03 1.3x | 1.88e-03 1.38e-03 1.4x
2000 2 | 1.66e-06 1.67e-06 1.0x | 1.69e-06 1.67e-06 1.0x
2000 10 | 2.25e-06 2.07e-06 1.1x | 2.10e-06 2.05e-06 1.0x
2000 50 | 5.04e-06 3.77e-06 1.3x | 4.52e-06 3.33e-06 1.4x
2000 200 | 2.56e-05 1.26e-05 2.0x | 1.90e-05 7.86e-06 2.4x
2000 1000 | 1.50e-04 1.07e-04 1.4x | 1.15e-04 8.16e-05 1.4x
2000 5000 | 7.50e-04 5.70e-04 1.3x | 5.96e-04 4.45e-04 1.3x
2000 20000 | 3.05e-03 2.31e-03 1.3x | 2.42e-03 1.81e-03 1.3x
10000 2 | 1.67e-06 1.73e-06 1.0x | 1.74e-06 1.72e-06 1.0x
10000 10 | 2.47e-06 2.28e-06 1.1x | 2.46e-06 2.08e-06 1.2x
10000 50 | 6.35e-06 4.54e-06 1.4x | 5.15e-06 3.68e-06 1.4x
10000 200 | 3.50e-05 1.76e-05 2.0x | 2.77e-05 1.18e-05 2.4x
10000 1000 | 1.90e-04 1.41e-04 1.3x | 1.49e-04 1.12e-04 1.3x
10000 5000 | 9.72e-04 7.52e-04 1.3x | 7.70e-04 5.96e-04 1.3x
10000 20000 | 3.88e-03 3.04e-03 1.3x | 3.12e-03 2.43e-03 1.3x
+-----------------+---------------------------+-------------------+-----------------+-----------------+
| | | jtaylor | jtaylor vs 1.8 | jtaylor vs new |
| haystack needle | np 1.8 new gain | sorted random | sorted random | sorted random |
+-----------------+---------------------------+-------------------+-----------------+-----------------+
| 5 2 | 1.60E-06 1.64E-06 (0.98x) | 1.64E-06 1.64E-06 | (0.98x) (0.98x) | (1.00x) (1.00x) |
| 5 10 | 1.65E-06 1.65E-06 (1.00x) | 1.73E-06 1.68E-06 | (0.95x) (0.98x) | (0.95x) (0.98x) |
| 5 50 | 2.21E-06 2.03E-06 (1.09x) | 2.05E-06 2.20E-06 | (1.08x) (1.00x) | (0.99x) (0.92x) |
| 5 200 | 4.98E-06 3.05E-06 (1.63x) | 3.07E-06 4.31E-06 | (1.62x) (1.16x) | (0.99x) (0.71x) |
| 5 1000 | 2.54E-05 1.03E-05 (2.47x) | 9.21E-06 1.62E-05 | (2.76x) (1.57x) | (1.12x) (0.64x) |
| 5 5000 | 1.33E-04 7.67E-05 (1.73x) | 3.78E-05 1.03E-04 | (3.52x) (1.29x) | (2.03x) (0.74x) |
| 5 20000 | 5.39E-04 3.22E-04 (1.67x) | 1.49E-04 4.34E-04 | (3.62x) (1.24x) | (2.16x) (0.74x) |
| 20 2 | 1.57E-06 1.64E-06 (0.96x) | 1.63E-06 1.62E-06 | (0.96x) (0.97x) | (1.01x) (1.01x) |
| 20 10 | 1.65E-06 1.66E-06 (0.99x) | 1.64E-06 1.64E-06 | (1.01x) (1.01x) | (1.01x) (1.01x) |
| 20 50 | 2.72E-06 2.11E-06 (1.29x) | 2.18E-06 2.12E-06 | (1.25x) (1.28x) | (0.97x) (1.00x) |
| 20 200 | 7.42E-06 3.95E-06 (1.88x) | 3.84E-06 4.02E-06 | (1.93x) (1.85x) | (1.03x) (0.98x) |
| 20 1000 | 4.56E-05 1.80E-05 (2.53x) | 1.29E-05 2.34E-05 | (3.53x) (1.95x) | (1.40x) (0.77x) |
| 20 5000 | 2.30E-04 1.34E-04 (1.72x) | 5.84E-05 1.64E-04 | (3.94x) (1.40x) | (2.29x) (0.82x) |
| 20 20000 | 9.30E-04 5.53E-04 (1.68x) | 2.21E-04 6.62E-04 | (4.21x) (1.40x) | (2.50x) (0.84x) |
| 100 2 | 1.66E-06 1.66E-06 (1.00x) | 1.63E-06 1.64E-06 | (1.02x) (1.01x) | (1.02x) (1.01x) |
| 100 10 | 1.83E-06 1.67E-06 (1.10x) | 1.84E-06 1.65E-06 | (0.99x) (1.11x) | (0.91x) (1.01x) |
| 100 50 | 3.29E-06 2.46E-06 (1.34x) | 2.46E-06 2.41E-06 | (1.34x) (1.37x) | (1.00x) (1.02x) |
| 100 200 | 1.15E-05 5.02E-06 (2.29x) | 5.10E-06 5.17E-06 | (2.25x) (2.22x) | (0.98x) (0.97x) |
| 100 1000 | 7.24E-05 3.41E-05 (2.12x) | 1.93E-05 4.72E-05 | (3.75x) (1.53x) | (1.77x) (0.72x) |
| 100 5000 | 3.67E-04 2.18E-04 (1.68x) | 8.69E-05 2.72E-04 | (4.22x) (1.35x) | (2.51x) (0.80x) |
| 100 20000 | 1.47E-03 8.82E-04 (1.67x) | 3.32E-04 1.12E-03 | (4.43x) (1.31x) | (2.66x) (0.79x) |
| 500 2 | 1.65E-06 1.64E-06 (1.01x) | 1.64E-06 1.64E-06 | (1.01x) (1.01x) | (1.00x) (1.00x) |
| 500 10 | 2.02E-06 1.67E-06 (1.21x) | 1.71E-06 1.69E-06 | (1.18x) (1.20x) | (0.98x) (0.99x) |
| 500 50 | 3.81E-06 2.52E-06 (1.51x) | 2.70E-06 2.85E-06 | (1.41x) (1.34x) | (0.93x) (0.88x) |
| 500 200 | 1.80E-05 6.07E-06 (2.97x) | 6.48E-06 6.89E-06 | (2.78x) (2.61x) | (0.94x) (0.88x) |
| 500 1000 | 1.07E-04 5.84E-05 (1.83x) | 2.68E-05 6.97E-05 | (3.99x) (1.54x) | (2.18x) (0.84x) |
| 500 5000 | 5.40E-04 3.20E-04 (1.69x) | 1.15E-04 3.75E-04 | (4.70x) (1.44x) | (2.78x) (0.85x) |
| 500 20000 | 2.18E-03 1.30E-03 (1.68x) | 4.41E-04 1.53E-03 | (4.94x) (1.42x) | (2.95x) (0.85x) |
| 2000 2 | 1.64E-06 1.65E-06 (0.99x) | 1.65E-06 1.65E-06 | (0.99x) (0.99x) | (1.00x) (1.00x) |
| 2000 10 | 2.05E-06 1.68E-06 (1.22x) | 1.79E-06 1.81E-06 | (1.15x) (1.13x) | (0.94x) (0.93x) |
| 2000 50 | 4.50E-06 2.89E-06 (1.56x) | 3.12E-06 2.97E-06 | (1.44x) (1.52x) | (0.93x) (0.97x) |
| 2000 200 | 2.37E-05 7.44E-06 (3.19x) | 8.13E-06 8.67E-06 | (2.92x) (2.73x) | (0.92x) (0.86x) |
| 2000 1000 | 1.32E-04 7.73E-05 (1.71x) | 3.72E-05 8.60E-05 | (3.55x) (1.53x) | (2.08x) (0.90x) |
| 2000 5000 | 6.69E-04 4.11E-04 (1.63x) | 1.52E-04 4.52E-04 | (4.40x) (1.48x) | (2.70x) (0.91x) |
| 2000 20000 | 2.69E-03 1.66E-03 (1.62x) | 5.53E-04 1.86E-03 | (4.86x) (1.45x) | (3.00x) (0.89x) |
| 10000 2 | 1.66E-06 1.64E-06 (1.01x) | 1.66E-06 1.65E-06 | (1.00x) (1.01x) | (0.99x) (0.99x) |
| 10000 10 | 2.16E-06 2.03E-06 (1.06x) | 1.94E-06 2.05E-06 | (1.11x) (1.05x) | (1.05x) (0.99x) |
| 10000 50 | 5.92E-06 3.34E-06 (1.77x) | 3.32E-06 3.51E-06 | (1.78x) (1.69x) | (1.01x) (0.95x) |
| 10000 200 | 3.21E-05 1.05E-05 (3.06x) | 9.98E-06 1.31E-05 | (3.22x) (2.45x) | (1.05x) (0.80x) |
| 10000 1000 | 1.65E-04 9.75E-05 (1.69x) | 5.43E-05 1.08E-04 | (3.04x) (1.53x) | (1.80x) (0.90x) |
| 10000 5000 | 8.36E-04 5.16E-04 (1.62x) | 2.17E-04 5.75E-04 | (3.85x) (1.45x) | (2.38x) (0.90x) |
| 10000 20000 | 3.34E-03 2.08E-03 (1.61x) | 7.26E-04 2.34E-03 | (4.60x) (1.43x) | (2.87x) (0.89x) |
+-----------------+---------------------------+-------------------+-----------------+-----------------+
(*) All timings in seconds, averages of 100 runs each of
h.searchsorted(n, side='l')
h.searchsorted(n, side='r')
with
h = np.sort(np.random.rand(haystack))
n = np.random.rand(needle) # "random" timings
n = np.sort(n = np.random.rand(needle)) # "sorted" timings
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment