<commit_before>#!/usr/bin/env python
#
# File: test_covertree.py
# Date of creation: 11/20/08
# Copyright (c) 2007, <NAME> <<EMAIL>>
# Copyright (c) 2011, <NAME> <<EMAIL>>
# All rights reserved.
#
# This is a tester for the cover tree nearest neighbor algorithm.  For
# more information please refer to the technical report entitled "Fast
# Nearest Neighbors" by Thomas Kollar or to "Cover Trees for Nearest
# Neighbor" by <NAME>, <NAME> and <NAME>
#  
# If you use this code in your research, kindly refer to the technical
# report.

from covertree import CoverTree
from naiveknn import knn
from pylab import sqrt, dot, plot, show
from numpy import subtract
# from scipy import random
from random import random, seed
import time

def distance(p, q):
    # print "distance"
    # print "p =", p
    # print "q =", q
    x = subtract(p, q)
    return sqrt(dot(x, x))

def test_covertree():
    seed(1)

    n_points = 1000

    k = 1
    
    pts = [(random(), random()) for _ in xrange(n_points)]

    gt = time.time
    
    t = gt()
    ct = CoverTree(distance)
    for p in pts:
        ct.insert(p)
    b_t = gt() - t
    print "Time to build a cover tree of", n_points, "2D points:", b_t, "seconds"

    query = (0.5,0.5)
    #cover-tree nearest neighbor
    t = gt()
    results = ct.knn(query, k)
    # print "result =", result
    ct_t = gt() - t
    print "Time to run a cover tree NN query:", ct_t, "seconds"
    
    # standard nearest neighbor
    t = gt()
    naive_results = knn(query, pts, distance, k)
    # print "resultNN =", resultNN
    n_t = gt() - t
    print "Time to run a naive NN query:", n_t, "seconds"

    if distance(results[0], naive_results[0]) != 0:
        print "This is bad"
        print results[0], "!=", naive_results[0]
    else:
        print "This is good"
        print "Cover tree query is", n_t/ct_t, "faster"


    # test find
    if ct.find(results[0]):
        print "This is good (covertree.find works)"
    else:
        print "This is bad (covertree.find doesn't work)"

    plot(pts[0], pts[1], 'rx')
    plot([query[0]], [query[1]], 'go')
    plot([naive_results[0][0]], [naive_results[0][1]], 'y^')
    plot([results[0][0]], [results[0][1]], 'mo')
    <commit_msg>last fix in test_covertree.py to test k-nn query<commit_after>#!/usr/bin/env python
#
# File: test_covertree.py
# Date of creation: 11/20/08
# Copyright (c) 2007, <NAME> <<EMAIL>>
# Copyright (c) 2011, <NAME> <<EMAIL>>
# All rights reserved.
#
# This is a tester for the cover tree nearest neighbor algorithm.  For
# more information please refer to the technical report entitled "Fast
# Nearest Neighbors" by Thomas Kollar or to "Cover Trees for Nearest
# Neighbor" by <NAME>, <NAME> and <NAME>
#  
# If you use this code in your research, kindly refer to the technical
# report.

from covertree import CoverTree
from naiveknn import knn
from pylab import sqrt, dot, plot, show
from numpy import subtract
# from scipy import random
from random import random, seed
import time

def distance(p, q):
    # print "distance"
    # print "p =", p
    # print "q =", q
    x = subtract(p, q)
    return sqrt(dot(x, x))

def test_covertree():
    seed(1)

    n_points = 1000

    k = 1
    
    pts = [(random(), random()) for _ in xrange(n_points)]

    gt = time.time
    
    t = gt()
    ct = CoverTree(distance)
    for p in pts:
        ct.insert(p)
    b_t = gt() - t
    print "Time to build a cover tree of", n_points, "2D points:", b_t, "seconds"

    query = (0.5,0.5)
    #cover-tree nearest neighbor
    t = gt()
    results = ct.knn(query, k)
    # print "result =", result
    ct_t = gt() - t
    print "Time to run a cover tree NN query:", ct_t, "seconds"
    
    # standard nearest neighbor
    t = gt()
    naive_results = knn(query, pts, distance, k)
    # print "resultNN =", resultNN
    n_t = gt() - t
    print "Time to run a naive NN query:", n_t, "seconds"

    if all([distance(r, nr) != 0 for r, nr in zip(results, naive_results)]):
        print "This is bad"
        print results, "!=", naive_results
    else:
        print "This is good"
        print "Cover tree query is", n_t/ct_t, "faster"


    # test find
    if ct.find(results[0]):
        print "This is good (covertree.find works)"
    else:
        print "This is bad (covertree.find doesn't work)"

    plot(pts[0], pts[1], 'rx')
    plot([query[0]], [query[1]], 'go')
    plot([naive_results[0][0]], [naive_results[0][1]], 'y^')
    plot([results[0][0]], [results[0][1]], 'mo')
    
{'fraction_non_alphanumeric': 0.13719376391982183, 'fraction_numerical': 0.01826280623608018, 'mean_word_length': 2.8648881239242683, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6769109', 'n_tokens_mistral': 1660, 'n_tokens_neox': 1540, 'n_words': 547}