fnntw 0.4.1

FNNTW: Fastest Nearest Neighbor (in the) West. A fast kdtree/kNN library.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

import numpy as np
from time import perf_counter as time
import pyfnntw
from pykdtree.kdtree import KDTree as pykdTree
from scipy.spatial import cKDTree as scipyTree


NRAND = 4*10**6
NQUERY = 4*10**6
WARMUP = 20
RUNS = 100
LS = 32
KK = [1, 10]

print(f"(d={NRAND:,}, q={NQUERY:,}, ls={LS}, runs={RUNS}")

# Generate data 
DATA = np.random.uniform(size=(NRAND, 3))

times = []
for _ in range((len(KK) + 1)):
    times.append([])
libs = ["scipy", "pykdtree", "fnntw"]
for lib in libs:
    print()
    print(f"{lib} results")
 
    build_time = 0
    kdtree = None
    # Generate queries
    for run in range(-WARMUP, RUNS):
        # Build tree
        start = time()
        if lib == "scipy":
            kdtree = scipyTree(DATA, leafsize=LS)#, boxsize = 1.0)
        elif lib == "pykdtree":
            kdtree = pykdTree(DATA, leafsize=LS)
        elif lib == "fnntw":
            kdtree = pyfnntw.Treef64(DATA, leafsize=LS, par_split_level=4)
        else:
            assert False
        bt = (time() - start)*1000
        if run >= 0:
            build_time += bt
    avg_build = build_time / RUNS
    times[0].append(avg_build)
    print(f"{lib}: {avg_build=:.3f} ms")

    for (i, K) in enumerate(KK):
        query_time = 0
        qt = 0
        queries = np.random.uniform(size=(NQUERY, 3))
        for run in range(-WARMUP, RUNS):
            # Query tree
            if lib == "scipy":
                start = time()
                dist, idx = kdtree.query(queries, k=K, workers=-1)        
                qt = (time() - start)*1000
            elif lib == "pykdtree":
                start = time()
                dist, idx = kdtree.query(queries, k=K, sqr_dists=False)
                qt = (time() - start)*1000
            elif lib == "fnntw":
                start = time()
                dist, idx = kdtree.query(queries, K)
                qt = (time() - start)*1000
            else:
                assert False
            if run >= 0:
                query_time += qt

        avg_query = query_time / RUNS
        times[i+1].append(avg_query)
        print(f"{lib} k={K}: {avg_query=:.3f} ms")
    print()
print('\x1b[6;30;42m' + 'build & nonpbc winners:' + '\x1b[0m')
print(f"build winner: {libs[np.argmin(times[0])]} @ {np.min(times[0]):.3f} ms")
for (i, K) in enumerate(KK):
    print(f"{K=} query winner: {libs[np.argmin(times[1+i])]}: @ {np.min(times[i+1]):.3f} ms")

print()
print("periodic results")
times = []
for _ in range(len(KK)):
    times.append([])
libs = ["scipy", "fnntw"]
for lib in libs:
    print()
    print(f"{lib} results")

    # Build tree (no need to benchmark)
    kdtree = None
    if lib == "scipy":
        kdtree = scipyTree(DATA, boxsize = 1.0, leafsize=LS)
    else:
        kdtree = pyfnntw.Treef64(DATA, boxsize = np.array([1.0]*3), leafsize=LS, par_split_level=4)

    for (i, K) in enumerate(KK):
        query_time = 0
        qt = 0
        queries = np.random.uniform(size=(NQUERY, 3))
        for run in range(-WARMUP, RUNS):
            # Query tree
            if lib == "scipy":
                start = time()
                dist, idx = kdtree.query(queries, k=K, workers=-1)        
                qt = (time() - start)*1000
            else:
                start = time()
                dist, idx = kdtree.query(queries, K)
                qt = (time() - start)*1000
            if run >= 0:
                query_time += qt

        avg_query = query_time / RUNS
        times[i].append(avg_query)
        print(f"{lib} k={K}: {avg_query=:.3f} ms")
    print()
print('\x1b[6;30;42m' + 'pbc winners:' + '\x1b[0m')
for (i, K) in enumerate(KK):
    print(f"{K=} query winner: {libs[np.argmin(times[i])]} @ {np.min(times[i]):.3f} ms", )


times = []
for _ in range(len(KK)):
    times.append([])
libs = ["scipy", "pykdtree", "fnntw"]
DATA = DATA.astype(np.float32)
for lib in libs:
    print()
    print(f"{lib} single precision results")

    build_time = 0
    kdtree = None
    # Generate queries
    queries = np.random.uniform(size=(NQUERY, 3)).astype(np.float32)
    # Build tree (no need to benchmark)
    if lib == "scipy":
        kdtree = scipyTree(DATA, leafsize=LS)#, boxsize = 1.0)
    elif lib == "pykdtree":
        kdtree = pykdTree(DATA, leafsize=LS)
    else:
        kdtree = pyfnntw.Treef32(DATA, leafsize=LS, par_split_level=4)
        
    for (i, K) in enumerate(KK):
        query_time = 0
        qt = 0
        queries = np.random.uniform(size=(NQUERY, 3)).astype(np.float32)
        for run in range(-WARMUP, RUNS):
            # Query tree
            if lib == "scipy":
                start = time()
                dist, idx = kdtree.query(queries, k=K, workers=-1)        
                qt = (time() - start)*1000
            elif lib == "pykdtree":
                start = time()
                dist, idx = kdtree.query(queries, k=K, sqr_dists=False)
                qt = (time() - start)*1000
            else:
                start = time()
                dist, idx = kdtree.query(queries, K)
                qt = (time() - start)*1000
            if run >= 0:
                query_time += qt
            
        avg_query = query_time / RUNS
        times[i].append(avg_query)
        print(f"{lib} k={K}: {avg_query=:.3f} ms")
    print()
print('\x1b[6;30;42m' + 'single precision winners:' + '\x1b[0m')
for (i, K) in enumerate(KK):
    print(f"{K=} query winner: {libs[np.argmin(times[i])]}  @ {np.min(times[i]):.3f} ms", )