Skip to content

Instantly share code, notes, and snippets.

@jjerphan

jjerphan/binary_tree_bench.py

Created April 15, 2021 08:45
Show Gist options
  • Save jjerphan/4bb326a67fcd944f2e01663383beaa5c to your computer and use it in GitHub Desktop.
Save jjerphan/4bb326a67fcd944f2e01663383beaa5c to your computer and use it in GitHub Desktop.
Download ZIP
Simple Benchmark for `sklearn.neighbours.BinaryTree`
Raw
binary_tree_bench.py
import numpy as np
from sklearn.neighbors import KDTree, BallTree
from .common import Benchmark
class BinaryTreeStatsBenchmark(Benchmark):
"""
Base class for BinaryTree benchmarks for removing statistics.
"""
param_names = ['BinaryTree', 'n', 'd', 'leaf_size']
params = (
[KDTree, BallTree],
[100, 1000, 10000],
[10, 100, 1000],
[10, 100]
)
class BinaryTreeStatsCreation(BinaryTreeStatsBenchmark):
"""
Benchmarks for BinaryTree creation.
"""
def setup(self, BinaryTree, n, d, leaf_size):
self.samples = np.random.rand(n, d)
self.leaf_size = leaf_size
self.BinaryTree = BinaryTree
def time_creation(self, BinaryTree, n, d, leaf_size):
self.BinaryTree(self.samples, leaf_size=self.leaf_size)
class BinaryTreeStatsQuery(BinaryTreeStatsBenchmark):
"""
Benchmarks for BinaryTree queries.
"""
def setup(self, BinaryTree, n, d, leaf_size):
self.tree = BinaryTree(np.random.rand(n, d), leaf_size=leaf_size)
self.query_points = np.random.rand(n, d)
def time_query(self, BinaryTree, n, d, leaf_size):
self.tree.query(
self.query_points,
dualtree=False,
breadth_first=False,
sort_results=False)
@jjerphan
Copy link
Author

jjerphan commented Apr 15, 2021 •
edited
Loading

Raw results for scikit-learn/scikit-learn#19884 (obtained with asv run -b BinaryTree):

· Running 4 total benchmarks (2 commits * 1 environments * 2 benchmarks)
[  0.00%] · For scikit-learn commit 7dd7c947 <remove_stats_binary_tree>:
[  0.00%] ·· Benchmarking conda-py3.9-cython-joblib-numpy-scipy-threadpoolctl
[ 25.00%] ··· binary_tree.BinaryTreeStatsCreation.time_creation
[ 25.00%] ··· ======================================= ======= ============ ============= ============ ============ ============ ============
              --                                                                              d / leaf_size
              ----------------------------------------------- ------------------------------------------------------------------------------
                             BinaryTree                  n      10 / 10       10 / 100     100 / 10    100 / 100    1000 / 10    1000 / 100
              ======================================= ======= ============ ============= ============ ============ ============ ============
                 sklearn.neighbors._kd_tree.KDTree      100     133±4μs       92.1±2μs     520±20μs     157±4μs     4.49±0.2ms    679±20μs
                 sklearn.neighbors._kd_tree.KDTree      1000   1.11±0.3ms   1.06±0.05ms   15.1±0.5ms    4.40±2ms     85.0±2ms    43.4±0.7ms
                 sklearn.neighbors._kd_tree.KDTree     10000   13.2±0.3ms    8.76±0.2ms    110±2ms      78.2±5ms    1.68±0.2s    1.55±0.1s
               sklearn.neighbors._ball_tree.BallTree    100     235±10μs      91.5±3μs    437±100μs     207±40μs    3.93±0.8ms    334±30μs
               sklearn.neighbors._ball_tree.BallTree    1000    789±20μs      527±80μs    6.21±0.2ms   3.40±0.1ms    66.1±3ms     29.8±2ms
               sklearn.neighbors._ball_tree.BallTree   10000    13.9±2ms      9.57±2ms     145±20ms     104±10ms    1.81±0.1s    1.31±0.04s
              ======================================= ======= ============ ============= ============ ============ ============ ============

[ 50.00%] ··· binary_tree.BinaryTreeStatsQuery.time_query
[ 50.00%] ··· ======================================= ======= ============ ============ ============= ============ ============ ============
              --                                                                              d / leaf_size
              ----------------------------------------------- ------------------------------------------------------------------------------
                             BinaryTree                  n      10 / 10      10 / 100      100 / 10    100 / 100    1000 / 10    1000 / 100
              ======================================= ======= ============ ============ ============= ============ ============ ============
                 sklearn.neighbors._kd_tree.KDTree      100     977±40μs     455±20μs     6.38±0.5ms   1.85±0.2ms    58.3±2ms    12.9±0.7ms
                 sklearn.neighbors._kd_tree.KDTree      1000    28.9±1ms    13.7±0.5ms     298±9ms      130±3ms     3.08±0.05s   1.47±0.09s
                 sklearn.neighbors._kd_tree.KDTree     10000    778±50ms     736±60ms     36.9±0.3s    22.2±0.6s      failed       failed
               sklearn.neighbors._ball_tree.BallTree    100     268±10μs     201±6μs     1.35±0.04ms   1.83±0.2ms   12.9±0.7ms   11.1±0.5ms
               sklearn.neighbors._ball_tree.BallTree    1000   16.8±0.6ms   13.6±0.3ms    127±0.7ms    113±0.8ms    1.34±0.01s   1.22±0.04s
               sklearn.neighbors._ball_tree.BallTree   10000   1.08±0.03s   1.68±0.02s    24.6±0.4s    21.4±0.8s      failed       failed
              ======================================= ======= ============ ============ ============= ============ ============ ============

[ 50.00%] · For scikit-learn commit 7fa2e6e2 <main>:
[ 50.00%] ·· Building for conda-py3.9-cython-joblib-numpy-scipy-threadpoolctl...........
[ 50.00%] ·· Benchmarking conda-py3.9-cython-joblib-numpy-scipy-threadpoolctl
[ 75.00%] ··· binary_tree.BinaryTreeStatsCreation.time_creation
[ 75.00%] ··· ======================================= ======= ============= ============ ============ ============ ============= ============
              --                                                                               d / leaf_size
              ----------------------------------------------- -------------------------------------------------------------------------------
                             BinaryTree                  n       10 / 10      10 / 100     100 / 10    100 / 100     1000 / 10    1000 / 100
              ======================================= ======= ============= ============ ============ ============ ============= ============
                 sklearn.neighbors._kd_tree.KDTree      100      150±4μs      98.5±3μs     530±10μs     147±3μs      4.44±0.1ms    699±20μs
                 sklearn.neighbors._kd_tree.KDTree      1000   1.00±0.02ms    557±10μs    7.93±0.2ms   4.16±0.1ms     87.3±2ms    46.4±0.8ms
                 sklearn.neighbors._kd_tree.KDTree     10000    13.8±0.7ms   9.43±0.2ms    121±3ms      85.8±3ms     1.37±0.04s   1.07±0.02s
               sklearn.neighbors._ball_tree.BallTree    100      122±4μs      89.1±2μs     373±10μs     111±3μs     2.84±0.08ms    298±6μs
               sklearn.neighbors._ball_tree.BallTree    1000     774±20μs     437±10μs    5.41±0.1ms   3.03±0.3ms     53.9±2ms     28.3±1ms
               sklearn.neighbors._ball_tree.BallTree   10000    9.68±0.2ms   6.51±0.2ms    90.8±8ms     63.1±2ms     1.07±0.05s    786±20ms
              ======================================= ======= ============= ============ ============ ============ ============= ============

[100.00%] ··· binary_tree.BinaryTreeStatsQuery.time_query
[100.00%] ··· ======================================= ======= ============ ============ ============= ============= ============ ============
              --                                                                               d / leaf_size
              ----------------------------------------------- -------------------------------------------------------------------------------
                             BinaryTree                  n      10 / 10      10 / 100      100 / 10     100 / 100    1000 / 10    1000 / 100
              ======================================= ======= ============ ============ ============= ============= ============ ============
                 sklearn.neighbors._kd_tree.KDTree      100     498±30μs     208±3μs     3.28±0.08ms    1.49±0.1ms   34.3±0.5ms   12.5±0.3ms
                 sklearn.neighbors._kd_tree.KDTree      1000   28.1±0.6ms   13.2±0.3ms     310±3ms      127±0.9ms    3.06±0.05s   1.43±0.01s
                 sklearn.neighbors._kd_tree.KDTree     10000    737±30ms     660±3ms      37.9±0.3s      24.7±1s       failed       failed
               sklearn.neighbors._ball_tree.BallTree    100     264±7μs      207±6μs     1.39±0.04ms   1.17±0.03ms   13.1±0.4ms   10.2±0.1ms
               sklearn.neighbors._ball_tree.BallTree    1000   17.8±0.4ms   15.1±0.5ms     134±5ms      111±0.6ms     1.33±0s     1.20±0.01s
               sklearn.neighbors._ball_tree.BallTree   10000   1.08±0.01s   1.68±0.02s    24.9±0.6s     22.2±0.1s      failed       failed
              ======================================= ======= ============ ============ ============= ============= ============ ============

@jjerphan
Copy link
Author

Raw results for scikit-learn/scikit-learn#19893:

[  0.00%] · For scikit-learn commit 33c85c85 <rm-get_memview-nn-routines>:
[  0.00%] ·· Benchmarking conda-py3.9-cython-joblib-numpy-scipy-threadpoolctl
[ 25.00%] ··· binary_tree.BinaryTreeStatsCreation.time_creation
[ 25.00%] ··· ======================================= ======= ============= ============ ============ ============ ============= ============
              --                                                                               d / leaf_size
              ----------------------------------------------- -------------------------------------------------------------------------------
                             BinaryTree                  n       10 / 10      10 / 100     100 / 10    100 / 100     1000 / 10    1000 / 100
              ======================================= ======= ============= ============ ============ ============ ============= ============
                 sklearn.neighbors._kd_tree.KDTree      100      120±4μs      74.4±2μs     579±20μs     138±10μs     4.64±0.1ms    685±20μs
                 sklearn.neighbors._kd_tree.KDTree      1000   1.04±0.04ms    543±20μs    8.70±0.3ms   4.59±0.2ms     79.8±4ms     50.5±1ms
                 sklearn.neighbors._kd_tree.KDTree     10000    12.9±0.3ms   8.58±0.2ms    128±3ms      104±30ms     1.49±0.1s    1.03±0.07s
               sklearn.neighbors._ball_tree.BallTree    100      97.7±2μs     68.9±2μs     322±8μs      88.8±2μs    2.54±0.06ms    319±9μs
               sklearn.neighbors._ball_tree.BallTree    1000     678±10μs     387±9μs     4.85±0.1ms   4.92±0.3ms    62.9±20ms    31.4±0.9ms
               sklearn.neighbors._ball_tree.BallTree   10000    9.32±0.2ms   6.39±0.1ms    86.1±3ms     58.5±8ms     1.01±0.06s    809±60ms
              ======================================= ======= ============= ============ ============ ============ ============= ============

[ 50.00%] ··· binary_tree.BinaryTreeStatsQuery.time_query
[ 50.00%] ··· ======================================= ======= ============ ============ ============= ============= ============ ============
              --                                                                               d / leaf_size
              ----------------------------------------------- -------------------------------------------------------------------------------
                             BinaryTree                  n      10 / 10      10 / 100      100 / 10     100 / 100    1000 / 10    1000 / 100
              ======================================= ======= ============ ============ ============= ============= ============ ============
                 sklearn.neighbors._kd_tree.KDTree      100    931±100μs     460±10μs     6.53±0.2ms   2.29±0.08ms   35.3±10ms    11.8±0.4ms
                 sklearn.neighbors._kd_tree.KDTree      1000    30.5±2ms     14.2±1ms      326±30ms      139±2ms     3.16±0.2s    1.54±0.1s
                 sklearn.neighbors._kd_tree.KDTree     10000    776±10ms     721±30ms      45.4±1s      25.4±0.4s      failed       failed
               sklearn.neighbors._ball_tree.BallTree    100     263±30μs     192±7μs     1.30±0.03ms   1.23±0.04ms   12.2±0.3ms   10.4±0.1ms
               sklearn.neighbors._ball_tree.BallTree    1000   16.7±0.4ms   13.9±0.5ms     139±4ms      109±0.8ms    1.30±0.01s   1.18±0.01s
               sklearn.neighbors._ball_tree.BallTree   10000   1.08±0.01s   1.68±0.1s     23.9±0.8s     21.4±0.3s      failed       failed
              ======================================= ======= ============ ============ ============= ============= ============ ============

[ 50.00%] · For scikit-learn commit 7fa2e6e2 <main>:
[ 50.00%] ·· Building for conda-py3.9-cython-joblib-numpy-scipy-threadpoolctl.........
[ 50.00%] ·· Benchmarking conda-py3.9-cython-joblib-numpy-scipy-threadpoolctl
[ 75.00%] ··· binary_tree.BinaryTreeStatsCreation.time_creation
[ 75.00%] ··· ======================================= ======= ============= ============ ============= ============= ============= ============
              --                                                                                d / leaf_size
              ----------------------------------------------- ---------------------------------------------------------------------------------
                             BinaryTree                  n       10 / 10      10 / 100      100 / 10     100 / 100     1000 / 10    1000 / 100
              ======================================= ======= ============= ============ ============= ============= ============= ============
                 sklearn.neighbors._kd_tree.KDTree      100      130±3μs      85.4±2μs      574±10μs      156±4μs      4.71±0.1ms    743±20μs
                 sklearn.neighbors._kd_tree.KDTree      1000   1.05±0.03ms    584±20μs     8.24±0.2ms    4.40±0.2ms     83.0±1ms    40.6±0.3ms
                 sklearn.neighbors._kd_tree.KDTree     10000    12.5±0.2ms   8.41±0.1ms     116±1ms      86.3±0.8ms    1.31±0.05s    955±10ms
               sklearn.neighbors._ball_tree.BallTree    100      109±2μs      79.6±1μs      341±6μs       108±5μs     2.58±0.05ms    295±5μs
               sklearn.neighbors._ball_tree.BallTree    1000     691±10μs     402±7μs     4.93±0.09ms   2.87±0.09ms    55.7±0.6ms   31.2±0.6ms
               sklearn.neighbors._ball_tree.BallTree   10000    9.89±0.2ms   6.74±0.2ms    85.1±0.8ms    57.1±0.5ms     999±20ms     722±20ms
              ======================================= ======= ============= ============ ============= ============= ============= ============

[100.00%] ··· binary_tree.BinaryTreeStatsQuery.time_query
[100.00%] ··· ======================================= ======= ============ ============ ============= ============= ============ ============
              --                                                                               d / leaf_size
              ----------------------------------------------- -------------------------------------------------------------------------------
                             BinaryTree                  n      10 / 10      10 / 100      100 / 10     100 / 100    1000 / 10    1000 / 100
              ======================================= ======= ============ ============ ============= ============= ============ ============
                 sklearn.neighbors._kd_tree.KDTree      100     457±9μs      202±5μs     3.20±0.06ms   1.17±0.02ms   30.3±0.4ms   11.1±0.2ms
                 sklearn.neighbors._kd_tree.KDTree      1000   27.5±0.5ms   14.1±0.3ms     298±2ms       130±5ms     2.71±0.02s   1.25±0.01s
                 sklearn.neighbors._kd_tree.KDTree     10000    772±6ms      679±20ms     34.4±0.2s     21.6±0.3s      failed       failed
               sklearn.neighbors._ball_tree.BallTree    100     240±5μs      186±3μs     1.25±0.02ms   1.05±0.02ms   11.7±0.2ms   10.1±0.2ms
               sklearn.neighbors._ball_tree.BallTree    1000   17.7±0.4ms   14.8±0.4ms    131±0.8ms      116±1ms      1.31±0s     1.17±0.01s
               sklearn.neighbors._ball_tree.BallTree   10000   1.03±0.01s   1.73±0.01s    22.0±0.6s     19.6±0.03s     failed      1.96±0m
              ======================================= ======= ============ ============ ============= ============= ============ ============

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment