annoy

1
# Copyright (c) 2013 Spotify AB
2
#
3
# Licensed under the Apache License, Version 2.0 (the "License"); you may not
4
# use this file except in compliance with the License. You may obtain a copy of
5
# the License at
6
#
7
# http://www.apache.org/licenses/LICENSE-2.0
8
#
9
# Unless required by applicable law or agreed to in writing, software
10
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12
# License for the specific language governing permissions and limitations under
13
# the License.
14

15
import random
16

17
import numpy
18

19
from annoy import AnnoyIndex
20

21

22
def test_random_holes():
23
    f = 10
24
    index = AnnoyIndex(f, "angular")
25
    valid_indices = random.sample(range(2000), 1000)  # leave holes
26
    for i in valid_indices:
27
        v = numpy.random.normal(size=(f,))
28
        index.add_item(i, v)
29
    index.build(10)
30
    for i in valid_indices:
31
        js = index.get_nns_by_item(i, 10000)
32
        for j in js:
33
            assert j in valid_indices
34
    for i in range(1000):
35
        v = numpy.random.normal(size=(f,))
36
        js = index.get_nns_by_vector(v, 10000)
37
        for j in js:
38
            assert j in valid_indices
39

40

41
def _test_holes_base(n, f=100, base_i=100000):
42
    annoy = AnnoyIndex(f, "angular")
43
    for i in range(n):
44
        annoy.add_item(base_i + i, numpy.random.normal(size=(f,)))
45
    annoy.build(100)
46
    res = annoy.get_nns_by_item(base_i, n)
47
    assert set(res) == set([base_i + i for i in range(n)])
48

49

50
def test_root_one_child():
51
    # See https://github.com/spotify/annoy/issues/223
52
    _test_holes_base(1)
53

54

55
def test_root_two_children():
56
    _test_holes_base(2)
57

58

59
def test_root_some_children():
60
    # See https://github.com/spotify/annoy/issues/295
61
    _test_holes_base(10)
62

63

64
def test_root_many_children():
65
    _test_holes_base(1000)
66