# k-Nearest Neighbor (kNN) exercise

Complete and hand in this completed worksheet (including its outputs and any supporting code outside of the worksheet) with your assignment submission. For more details see the assignments page on the course website.

The kNN classifier consists of two stages:

• During training, the classifier takes the training data and simply remembers it
• During testing, kNN classifies every test image by comparing to all training images and transfering the labels of the k most similar training examples
• The value of k is cross-validated

In this exercise you will implement these steps and understand the basic Image Classification pipeline, cross-validation, and gain proficiency in writing efficient, vectorized code.

``````

In [24]:

# Run some setup code for this notebook.

import random
import numpy as np
from data_utils import load_CIFAR10
import matplotlib.pyplot as plt

# This is a bit of magic to make matplotlib figures appear inline in the notebook
# rather than in a new window.
%matplotlib inline
plt.rcParams['figure.figsize'] = (10.0, 8.0) # set default size of plots
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'

# Some more magic so that the notebook will reload external python modules;

``````
``````

``````
``````

In [25]:

# Load the raw CIFAR-10 data.
cifar10_dir = 'data/cifar-10-batches-py'
X_train, y_train, X_test, y_test = load_CIFAR10(cifar10_dir)

# As a sanity check, we print out the size of the training and test data.
print 'Training data shape: ', X_train.shape
print 'Training labels shape: ', y_train.shape
print 'Test data shape: ', X_test.shape
print 'Test labels shape: ', y_test.shape

``````
``````

Training data shape:  (50000, 32, 32, 3)
Training labels shape:  (50000,)
Test data shape:  (10000, 32, 32, 3)
Test labels shape:  (10000,)

``````
``````

In [5]:

# Visualize some examples from the dataset.
# We show a few examples of training images from each class.
classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']
num_classes = len(classes)
samples_per_class = 7
for y, cls in enumerate(classes):
print "ytrain check",y_train ,y
idxs = np.flatnonzero(y_train == y)
idxs = np.random.choice(idxs, samples_per_class, replace=False)
for i, idx in enumerate(idxs):
plt_idx = i * num_classes + y + 1
plt.subplot(samples_per_class, num_classes, plt_idx)
plt.imshow(X_train[idx].astype('uint8'))
plt.axis('off')
if i == 0:
plt.title(cls)
plt.show()

``````
``````

ytrain check [6 9 9 ..., 9 1 1] 0
ytrain check [6 9 9 ..., 9 1 1] 1
ytrain check [6 9 9 ..., 9 1 1] 2
ytrain check [6 9 9 ..., 9 1 1] 3
ytrain check [6 9 9 ..., 9 1 1] 4
ytrain check [6 9 9 ..., 9 1 1] 5
ytrain check [6 9 9 ..., 9 1 1] 6
ytrain check [6 9 9 ..., 9 1 1] 7
ytrain check [6 9 9 ..., 9 1 1] 8
ytrain check [6 9 9 ..., 9 1 1] 9

``````
``````

In [26]:

# Subsample the data for more efficient code execution in this exercise
num_training = 5000

num_test = 500

``````
``````

In [27]:

# Reshape the image data into rows
print X_train.shape[0]

X_train = np.reshape(X_train, (X_train.shape[0], -1))
print X_train
X_test = np.reshape(X_test, (X_test.shape[0], -1))
print X_train.shape, X_test.shape

``````
``````

5000
[[  59.   62.   63. ...,  123.   92.   72.]
[ 154.  177.  187. ...,  143.  133.  144.]
[ 255.  255.  255. ...,   80.   86.   84.]
...,
[ 167.  163.  145. ...,   42.   78.   84.]
[ 154.  152.  125. ...,  194.  247.  114.]
[  45.   32.   21. ...,  156.  142.  100.]]
(5000, 3072) (500, 3072)

``````
``````

In [28]:

from classifiers.k_nearest_neighbor import KNearestNeighbor

# Create a kNN classifier instance.
# Remember that training a kNN classifier is a noop:
# the Classifier simply remembers the data and does no further processing
classifier = KNearestNeighbor()
classifier.train(X_train, y_train)

``````

We would now like to classify the test data with the kNN classifier. Recall that we can break down this process into two steps:

1. First we must compute the distances between all test examples and all train examples.
2. Given these distances, for each test example we find the k nearest examples and have them vote for the label

Lets begin with computing the distance matrix between all training and test examples. For example, if there are Ntr training examples and Nte test examples, this stage should result in a Nte x Ntr matrix where each element (i,j) is the distance between the i-th test and j-th train example.

First, open `cs231n/classifiers/k_nearest_neighbor.py` and implement the function `compute_distances_two_loops` that uses a (very inefficient) double loop over all pairs of (test, train) examples and computes the distance matrix one element at a time.

``````

In [7]:

# Open cs231n/classifiers/k_nearest_neighbor.py and implement
# compute_distances_two_loops.

# Test your implementation:

dists = classifier.compute_distances_two_loops(X_test)
print dists.shape

``````
``````

500 5000
[[ 3803.92350081  4210.59603857  5504.0544147  ...,  4007.64756434
4203.28086142  4354.20256764]
[ 6336.83367306  5270.28006846  4040.63608854 ...,  4829.15334194
4694.09767687  7768.33347636]
[ 5224.83913628  4250.64289255  3773.94581307 ...,  3766.81549853
4464.99921613  6353.57190878]
...,
[ 5366.93534524  5062.8772452   6361.85774755 ...,  5126.56824786
4537.30613911  5920.94156364]
[ 3671.92919322  3858.60765044  4846.88157479 ...,  3521.04515734
3182.3673578   4448.65305458]
[ 6960.92443573  6083.71366848  6338.13442584 ...,  6083.55504619
4128.24744898  8041.05223214]]
(500, 5000)

``````
``````

In [8]:

# We can visualize the distance matrix: each row is a single test example and
# its distances to training examples
plt.imshow(dists, interpolation='none')

``````
``````

Out[8]:

<matplotlib.image.AxesImage at 0x123d56410>

``````

Inline Question #1: Notice the structured patterns in the distance matrix.

• What is the cause behind the distinctly visible rows?
• What causes the columns?

Your Answer: fill this in. default color scheme ->black -> low distance, white-> high distance 1)One distinctly bright row indicates that this testing image is not similar to a large number of training images in terms of L2 distance.

2)One distinguishable column implies that this training image is either similar to a lot of testing images (black column, low L2 distance) or not similar to a lot of training images (white column, high L2 distance).

``````

In [13]:

# Now implement the function predict_labels and run the code below:
# We use k = 1 (which is Nearest Neighbor).
print y_train[4601]
state = [8,3]
print y_train[17]
# print y_train.
y_test_pred = classifier.predict_labels(dists, k=2)
# Compute and print the fraction of correctly predicted examples
num_correct = np.sum(y_test_pred == y_test)
accuracy = float(num_correct) / num_test
print 'Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy)

``````
``````

0
(array([   8,    9,   17, ..., 4988, 4994, 4995]),)
3
[ 420 3684 4224 ..., 4375 2744 4601]
[False False False ..., False False False]
closest_y [8, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2192 4848 2166 ..., 4400 4688 1387]
[False False False ..., False False False]
closest_y [9, 7]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4469  909 3904 ..., 4921 3355 3837]
[False False False ..., False False False]
closest_y [2, 2]
<type 'list'> <built-in method count of list object at 0x123d692d8>
[ 252 4453 4270 ..., 4688 4921 1387]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[1881 3949 3797 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [4, 8]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2654  347 1983 ...,  790 4601 2744]
[False False False ..., False False False]
closest_y [0, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4033  831   22 ..., 1342 2744 4601]
[False False False ..., False False False]
closest_y [0, 2]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 910 4055 1838 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [3, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4808 1686 1283 ..., 4813 4940 1387]
[False False False ..., False False False]
closest_y [0, 4]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2096 4320  126 ..., 2814 3035 4688]
[False False False ..., False False False]
closest_y [7, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 303  456 1759 ..., 1387 4940 3286]
[False False False ..., False False False]
closest_y [0, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 139  722 2905 ..., 4921 3355 3837]
[False False False ..., False False False]
closest_y [7, 3]
<type 'list'> <built-in method count of list object at 0x123d692d8>
[2745 3540 4124 ..., 4271 3205 4601]
[False False False ..., False False False]
closest_y [4, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 825 4279  920 ..., 1342 2744 1527]
[False False False ..., False False False]
closest_y [4, 2]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[ 271 4066 2749 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [2, 8]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4183 4453 1832 ..., 4273 1342 4564]
[False False False ..., False False False]
closest_y [2, 2]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4153 1160 2550 ...,  977 3737 4564]
[False False False ..., False False False]
closest_y [2, 1]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[  80 4864 4045 ..., 4940 3286  735]
[False False False ..., False False False]
closest_y [4, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3059 2192 2670 ..., 4590 3355 3837]
[False False False ..., False False False]
closest_y [5, 2]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1881 4139 4604 ..., 4601 4418 1527]
[False False False ..., False False False]
closest_y [1, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2693 1440 1038 ...,  735 4601  504]
[False False False ..., False False False]
closest_y [1, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1522 3382 3842 ..., 1843 2439 4940]
[False False False ..., False False False]
closest_y [3, 1]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4282 2277 2660 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [4, 6]
<type 'list'> <built-in method count of list object at 0x123d692d8>
[ 313 2196 2069 ..., 4645 4601  735]
[False False False ..., False False False]
closest_y [4, 7]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2764 2859  982 ..., 4656 1387 4940]
[False False False ..., False False False]
closest_y [6, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 420 4224 3913 ..., 4601 2744  504]
[False False False ..., False False False]
closest_y [4, 6]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1359 1126 1318 ..., 4500 4601  735]
[False False False ..., False False False]
closest_y [9, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2074  711 3845 ..., 4688 2814 3035]
[False False False ..., False False False]
closest_y [2, 7]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2678  571 2481 ..., 3467 3035  735]
[False False False ..., False False False]
closest_y [5, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[3712 1692 3178 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [9, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2124 1530 1596 ..., 2744 4645 4601]
[False False False ..., False False False]
closest_y [8, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2133   42 1143 ..., 1342 4601 4271]
[False False False ..., False False False]
closest_y [9, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 398 2522  130 ..., 4564 4348 4271]
[False False False ..., False False False]
closest_y [3, 1]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1176  721 1962 ..., 3671 4271 4601]
[False False False ..., False False False]
closest_y [0, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[4066 3874  749 ..., 2744 1527 4601]
[False False False ..., False False False]
closest_y [1, 1]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[3649 4565 1881 ..., 4375 2744 4601]
[False False False ..., False False False]
closest_y [6, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2133 4208 3116 ..., 2744 4271 4601]
[False False False ..., False False False]
closest_y [0, 4]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[2172 4540 3638 ..., 4400 1387 4921]
[False False False ..., False False False]
closest_y [6, 8]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[ 982 1458 1360 ..., 1387 3035 4940]
[False False False ..., False False False]
closest_y [7, 5]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2567  993 1314 ..., 4564 4273 2320]
[False False False ..., False False False]
closest_y [1, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[3579 1404 4723 ..., 4940 3286 4921]
[False False False ..., False False False]
closest_y [1, 2]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[1596  850 2124 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [9, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2966 3768 4066 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [9, 6]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2943 3670  552 ..., 4601 4500  735]
[False False False ..., False False False]
closest_y [0, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[ 763  365 1999 ..., 1527 3286  504]
[False False False ..., False False False]
closest_y [8, 6]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[1759 4540 1065 ..., 4940 4921 1387]
[False False False ..., False False False]
closest_y [4, 3]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1355 3935 2266 ..., 1527 4271 3205]
[False False False ..., False False False]
closest_y [8, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 564 1162  906 ..., 3205 2744 4601]
[False False False ..., False False False]
closest_y [9, 8]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[3718 1746 3797 ..., 4418 4271 4601]
[False False False ..., False False False]
closest_y [4, 4]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2812 4732 2983 ..., 2744 4645 4601]
[False False False ..., False False False]
closest_y [7, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4134 3640 1711 ...,  790  504 2744]
[False False False ..., False False False]
closest_y [2, 2]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[1092  906 3065 ...,  504 4601 2744]
[False False False ..., False False False]
closest_y [1, 7]
<type 'list'> <built-in method count of list object at 0x123d69200>
[   3  961 3170 ..., 4271 4348 4601]
[False False False ..., False False False]
closest_y [2, 3]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3178 2966 4135 ..., 1527 4645 4601]
[False False False ..., False False False]
closest_y [5, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2344 2003 1711 ..., 4921 3837 3355]
[False False False ..., False False False]
closest_y [0, 2]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1229 4298 1284 ..., 3355  504 3837]
[False False False ..., False False False]
closest_y [8, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3031 3408 4905 ..., 4375 4564 2744]
[False False False ..., False False False]
closest_y [1, 0]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3136 2602 3467 ..., 1527 2744 4601]
[False False False ..., False False False]
closest_y [1, 6]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1759 1065 3627 ..., 4940 1387 4921]
[False False False ..., False False False]
closest_y [6, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[ 254  658 4398 ..., 3286 4940  735]
[False False False ..., False False False]
closest_y [7, 2]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 254 1027  933 ..., 3286 2907 4940]
[False False False ..., False False False]
closest_y [7, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1537 1716  217 ..., 4500 4601  735]
[False False False ..., False False False]
closest_y [6, 0]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[2112  682 4284 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [4, 6]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[4128 4053 1726 ..., 1328 3355  504]
[False False False ..., False False False]
closest_y [1, 2]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4007 2695 4715 ...,  735 2744 4601]
[False False False ..., False False False]
closest_y [3, 2]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 910  180 1207 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [2, 6]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[ 716 1404 1284 ..., 2744 1527  504]
[False False False ..., False False False]
closest_y [3, 7]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 786 3254 3918 ..., 1387 4940 3286]
[False False False ..., False False False]
closest_y [4, 3]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1345 3178  838 ..., 2744 4645 4601]
[False False False ..., False False False]
closest_y [8, 6]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 749 4684 4775 ..., 2744 3837  504]
[False False False ..., False False False]
closest_y [0, 1]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2543 4683 1065 ..., 4400 1387 4940]
[False False False ..., False False False]
closest_y [3, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1695 1917  347 ...,  790 2744 4601]
[False False False ..., False False False]
closest_y [0, 6]
<type 'list'> <built-in method count of list object at 0x123d69200>
[3579 4540 4807 ..., 4921 4940 1387]
[False False False ..., False False False]
closest_y [0, 0]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1039 3121 1162 ..., 3205 1342 3837]
[False False False ..., False False False]
closest_y [4, 1]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4053 3304 4544 ..., 4590 2814 4688]
[False False False ..., False False False]
closest_y [8, 8]
<type 'list'> <built-in method count of list object at 0x123d69200>
[3418 2197  800 ..., 4271 4601  735]
[False False False ..., False False False]
closest_y [2, 8]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1360 4228 4527 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [9, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4310 2745 2181 ..., 4418 3205 1342]
[False False False ..., False False False]
closest_y [5, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4907 4324 2842 ..., 4418 1527 4601]
[False False False ..., False False False]
closest_y [2, 8]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[3503 2176  782 ..., 4400 1387 4940]
[False False False ..., False False False]
closest_y [7, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3638 2172 4540 ..., 4940 4921 1387]
[False False False ..., False False False]
closest_y [1, 4]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 850 1367 1351 ..., 3205 4271 4601]
[False False False ..., False False False]
closest_y [6, 6]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[3949 3841  420 ..., 2744  735 4601]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2341 4056 2441 ..., 4400 1387 4940]
[False False False ..., False False False]
closest_y [2, 0]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1118 2346 4471 ..., 4400 4940 1387]
[False False False ..., False False False]
closest_y [5, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3116 2840 4066 ...,  504 2744 4601]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[4827 4034 1469 ..., 4418 2744 4601]
[False False False ..., False False False]
closest_y [8, 6]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2172 2577  185 ..., 4400 4921 1387]
[False False False ..., False False False]
closest_y [4, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2172 1770 3304 ..., 4921 1387 4688]
[False False False ..., False False False]
closest_y [2, 3]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1229 1431 1999 ..., 3355 1342  504]
[False False False ..., False False False]
closest_y [7, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1759 4861 3034 ..., 4940 3035 3286]
[False False False ..., False False False]
closest_y [6, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 979 4550 1530 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [5, 4]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2172 1278 3215 ..., 4400 4921 1387]
[False False False ..., False False False]
closest_y [5, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4172 1458 1563 ..., 3616 4601 4645]
[False False False ..., False False False]
closest_y [2, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[  10 2253 2725 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [6, 4]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1759  933 2576 ..., 3286 4921 4940]
[False False False ..., False False False]
closest_y [3, 3]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 347  420 3684 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [0, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1759 2859  303 ..., 3286 1387 4940]
[False False False ..., False False False]
closest_y [5, 6]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[3842  266  317 ..., 2439 1766 4940]
[False False False ..., False False False]
closest_y [4, 7]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1770 1882 2233 ..., 3035 1387 4940]
[False False False ..., False False False]
closest_y [4, 3]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3408 2922 2301 ...,  735 3626 4564]
[False False False ..., False False False]
closest_y [7, 0]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[ 662 1221 2922 ..., 3286 4940 3626]
[False False False ..., False False False]
closest_y [7, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[3048 1351 4087 ..., 2744 1342 4601]
[False False False ..., False False False]
closest_y [8, 9]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4195 3654 4445 ..., 3355 2948 3772]
[False False False ..., False False False]
closest_y [6, 4]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[1559 2922  250 ..., 2744 4601  735]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x123d69200>
[3452  524 1597 ..., 4132 4921 1387]
[False False False ..., False False False]
closest_y [6, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1881 3528 1917 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [5, 5]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4907 2650 4732 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [8, 4]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4808 1091 1933 ..., 4273 4331 4564]
[False False False ..., False False False]
closest_y [0, 4]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2108 3303 4153 ..., 4518 4331 4564]
[False False False ..., False False False]
closest_y [2, 0]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[3855  804 2041 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [7, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 373 4190 4588 ..., 2439 1977 4940]
[False False False ..., False False False]
closest_y [7, 1]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4954 4752 1132 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [2, 4]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[2859 4224 1143 ...,  504 2744 4601]
[False False False ..., False False False]
closest_y [1, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 982 1284  102 ..., 3355 4921  504]
[False False False ..., False False False]
closest_y [6, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4987 2678 1937 ..., 4601  504  735]
[False False False ..., False False False]
closest_y [0, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2867 2066  153 ..., 1387 3286 4940]
[False False False ..., False False False]
closest_y [7, 8]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 271 4066 3919 ..., 4645 4601 3837]
[False False False ..., False False False]
closest_y [5, 2]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[4741 1843  781 ..., 2744 4645 4601]
[False False False ..., False False False]
closest_y [3, 6]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 692  521 3182 ..., 4418  735 4331]
[False False False ..., False False False]
closest_y [3, 8]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2172 3638 4540 ..., 4400 4921 1387]
[False False False ..., False False False]
closest_y [8, 6]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[ 959 3219 3897 ...,  735 4500 4601]
[False False False ..., False False False]
closest_y [1, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 420 2812 4647 ..., 1527 2744 4601]
[False False False ..., False False False]
closest_y [5, 6]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2583 2982 4208 ..., 1363 2814 4940]
[False False False ..., False False False]
closest_y [6, 5]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1770  987  554 ..., 3035 1387 4940]
[False False False ..., False False False]
closest_y [5, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2133 4224  420 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [0, 6]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[1759 2310 3246 ...,  790 4601 2744]
[False False False ..., False False False]
closest_y [3, 9]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[4755 2730  197 ..., 4518 4273 4331]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4590 4801 3989 ..., 2577 3199 3626]
[False False False ..., False False False]
closest_y [4, 6]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2993  120  827 ..., 4400 1387 4940]
[False False False ..., False False False]
closest_y [0, 4]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 403 2543 1283 ..., 4656 1387 4940]
[False False False ..., False False False]
closest_y [3, 3]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2362 2768 3922 ..., 4921 4940 1387]
[False False False ..., False False False]
closest_y [2, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3246 1708 4794 ..., 2356 3355 4940]
[False False False ..., False False False]
closest_y [1, 3]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[1690 4472 2017 ..., 1363 3467 4940]
[False False False ..., False False False]
closest_y [1, 8]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3411 2017  203 ..., 3746 1766 4940]
[False False False ..., False False False]
closest_y [4, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 767 3077 2093 ..., 4940 4921 1387]
[False False False ..., False False False]
closest_y [4, 3]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4164 4128 4545 ..., 4375 2744  504]
[False False False ..., False False False]
closest_y [3, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 974 3376 1759 ..., 4940 1387 3286]
[False False False ..., False False False]
closest_y [6, 8]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3558  622 2983 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [3, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4320 3039  793 ..., 3035 1387 4921]
[False False False ..., False False False]
closest_y [1, 7]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[3164  130 1759 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [9, 1]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4453 1759 3121 ..., 4921 3837 4564]
[False False False ..., False False False]
closest_y [3, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1017 3985 3634 ..., 1387 3467 4940]
[False False False ..., False False False]
closest_y [1, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[4956  849  784 ..., 4601 1342 4418]
[False False False ..., False False False]
closest_y [1, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 562 2272  252 ...,  535 4564 3355]
[False False False ..., False False False]
closest_y [1, 8]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4985 4113 1139 ..., 4400 1387 4921]
[False False False ..., False False False]
closest_y [6, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4426 1136 2112 ..., 1342 2744 4601]
[False False False ..., False False False]
closest_y [3, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4463 3194 1600 ..., 1342 4418  504]
[False False False ..., False False False]
closest_y [3, 2]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 157 1160  931 ..., 4331 1342 4564]
[False False False ..., False False False]
closest_y [4, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[4283 1036 4166 ..., 2744 1342 4375]
[False False False ..., False False False]
closest_y [6, 9]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 600 3246 2868 ..., 3035 1387 4921]
[False False False ..., False False False]
closest_y [1, 7]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 101  338 2472 ..., 4375 2744  504]
[False False False ..., False False False]
closest_y [0, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[ 710 2595 2782 ..., 1527 4645 4601]
[False False False ..., False False False]
closest_y [1, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 341  974 2193 ..., 1387 3467 4940]
[False False False ..., False False False]
closest_y [0, 4]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[3670 4773 1491 ...,  221  735 3199]
[False False False ..., False False False]
closest_y [5, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1324 1881 2116 ..., 2744 1342 4601]
[False False False ..., False False False]
closest_y [7, 3]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2441  957 2034 ..., 4813 1387 4940]
[False False False ..., False False False]
closest_y [6, 1]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4834 2483  139 ..., 4921 1387 3355]
[False False False ..., False False False]
closest_y [0, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2266 3949 2400 ...,  735 4500 4601]
[False False False ..., False False False]
closest_y [9, 7]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[4527 1500 4868 ...,  504 4601  735]
[False False False ..., False False False]
closest_y [7, 7]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 348 2017  820 ..., 1766 4940 3746]
[False False False ..., False False False]
closest_y [4, 6]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3189 1299 2112 ...,  735 4645 4601]
[False False False ..., False False False]
closest_y [7, 9]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[3403 3080 1164 ..., 2744 4271 4601]
[False False False ..., False False False]
closest_y [0, 1]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[3393 2983 1838 ...,  790 2744 4601]
[False False False ..., False False False]
closest_y [6, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2881  659 3438 ..., 4940 1387 4921]
[False False False ..., False False False]
closest_y [7, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4018 4527  898 ..., 4656 4921 4940]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[2172 4540  566 ..., 4400 1387 4921]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[4550 2372 2812 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [2, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2017 4804  762 ..., 4656 1387 4940]
[False False False ..., False False False]
closest_y [2, 2]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[3063  749 4544 ..., 3355  504 3837]
[False False False ..., False False False]
closest_y [2, 7]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[3039 3579 1439 ..., 4400 4940 1387]
[False False False ..., False False False]
closest_y [5, 9]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 898 4427 4794 ..., 2814 1387 4940]
[False False False ..., False False False]
closest_y [9, 6]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 592 1759 2993 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [4, 7]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[3065 1162 4925 ..., 1342 4601 3205]
[False False False ..., False False False]
closest_y [7, 0]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[1826  887 4224 ..., 2744  735 4601]
[False False False ..., False False False]
closest_y [5, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1640 4557 4291 ..., 3035 4921 1554]
[False False False ..., False False False]
closest_y [0, 9]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[3549 2777 3049 ...,  735   21 3286]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 951 4703  337 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [6, 5]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 420 3873 2595 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [4, 3]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[ 554 2882 4060 ..., 2263 4688 2814]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 596 2162  743 ..., 1387 4940 3035]
[False False False ..., False False False]
closest_y [2, 4]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 695 3985 1158 ..., 1387 4921 4940]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4211  933  990 ..., 1387 4921 4940]
[False False False ..., False False False]
closest_y [8, 7]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 420 1500 4868 ..., 1342 2744 4601]
[False False False ..., False False False]
closest_y [0, 5]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 695 2794 3010 ..., 1387 1766 4940]
[False False False ..., False False False]
closest_y [5, 3]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 974 1720 3157 ..., 4940 1387 3286]
[False False False ..., False False False]
closest_y [2, 1]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2112 2507 4217 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [5, 3]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4346 2875 3739 ..., 4940 3746  735]
[False False False ..., False False False]
closest_y [7, 1]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[3482  691 4322 ..., 3035 3365 4940]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4277 1243 3745 ..., 4651   21 3286]
[False False False ..., False False False]
closest_y [9, 3]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2723  144 3359 ..., 4940 1387 4688]
[False False False ..., False False False]
closest_y [8, 1]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[3587  254 4808 ..., 4331 3286 4940]
[False False False ..., False False False]
closest_y [5, 6]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[1788 1143 2133 ...,  504 3671 4601]
[False False False ..., False False False]
closest_y [0, 9]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2535 2130  243 ..., 2744 4271 4601]
[False False False ..., False False False]
closest_y [4, 5]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 951 4703 1220 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [7, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2116 4628   54 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [9, 3]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2979 1463 2344 ..., 4940 3467 1363]
[False False False ..., False False False]
closest_y [6, 1]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[2176 2391 1432 ..., 4400 4940 1387]
[False False False ..., False False False]
closest_y [1, 1]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[4184 2699 2223 ..., 4601  816  735]
[False False False ..., False False False]
closest_y [3, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2567 3458 4808 ..., 1387 4940 3286]
[False False False ..., False False False]
closest_y [8, 2]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[  18 3939 1220 ..., 2744 4601 2907]
[False False False ..., False False False]
closest_y [4, 1]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4053  448 3573 ..., 3355 4590 3837]
[False False False ..., False False False]
closest_y [4, 2]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 554 1323  379 ..., 1387 3286 4940]
[False False False ..., False False False]
closest_y [5, 2]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 910 2018  263 ..., 4645 4601 4500]
[False False False ..., False False False]
closest_y [2, 5]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2725 4647 3178 ..., 1342 1527 4601]
[False False False ..., False False False]
closest_y [7, 2]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 403 4808 3046 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [8, 8]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2350 2277 2789 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [8, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 933 4521 4211 ..., 4348 4564 4271]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1220  383  933 ..., 3467 2907 4940]
[False False False ..., False False False]
closest_y [7, 4]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2171 4455  252 ..., 4921 4688 3837]
[False False False ..., False False False]
closest_y [8, 5]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[1563 2875 4224 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [0, 4]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 121 1506  909 ..., 2744 3837  504]
[False False False ..., False False False]
closest_y [5, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[3436 4552 2079 ..., 1843 1387 4940]
[False False False ..., False False False]
closest_y [0, 9]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 558 4254 3784 ..., 3616 3837 1363]
[False False False ..., False False False]
closest_y [5, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2979 4226  766 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [8, 2]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2349 3163 3277 ..., 1766 1387 4940]
[False False False ..., False False False]
closest_y [5, 7]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[1593  866  441 ..., 4921 4940 1387]
[False False False ..., False False False]
closest_y [3, 8]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3677 2635 4953 ..., 3467 1387 4940]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4645 4601 4355 ..., 4400 1387 4940]
[False False False ..., False False False]
closest_y [1, 2]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[3418 2716  933 ..., 4500 4601 4271]
[False False False ..., False False False]
closest_y [2, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4706 4147 2213 ..., 3467 1977 4940]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 336 2594 2252 ..., 4645 4271 4601]
[False False False ..., False False False]
closest_y [8, 0]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[3623 4191 4453 ..., 4921 4564 3837]
[False False False ..., False False False]
closest_y [4, 2]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2350 2594  710 ...,  790 4601 2744]
[False False False ..., False False False]
closest_y [3, 0]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4288 4827 4491 ..., 4601 2744  504]
[False False False ..., False False False]
closest_y [4, 0]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[1809 4715 3138 ...,  790 4601 2744]
[False False False ..., False False False]
closest_y [3, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 558 3886 2905 ..., 4601 1527 3837]
[False False False ..., False False False]
closest_y [9, 1]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2543 1686 1283 ..., 4813 4940 1387]
[False False False ..., False False False]
closest_y [0, 9]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2858 4082 2441 ..., 1387 1766 4940]
[False False False ..., False False False]
closest_y [4, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4987 4693  951 ..., 4645 4500 4601]
[False False False ..., False False False]
closest_y [1, 8]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4108 2766 3670 ..., 4601  816  735]
[False False False ..., False False False]
closest_y [3, 5]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[3735  364 2664 ..., 3035 4940 2907]
[False False False ..., False False False]
closest_y [2, 4]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 963 2116 4733 ..., 1527 4601 4418]
[False False False ..., False False False]
closest_y [8, 6]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4108  673 3670 ...,  735 2744 4601]
[False False False ..., False False False]
closest_y [3, 4]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2172 4477 3607 ..., 4688 1387 3837]
[False False False ..., False False False]
closest_y [7, 9]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2247 1243 3049 ...,   21 4940 3286]
[False False False ..., False False False]
closest_y [0, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[  10 1530 3560 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [7, 2]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[3882 3501 1490 ..., 3616 4590 3355]
[False False False ..., False False False]
closest_y [2, 7]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1618 1211 4322 ..., 4400 1387 4940]
[False False False ..., False False False]
closest_y [6, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2509 2674 1674 ..., 3746 1766 4940]
[False False False ..., False False False]
closest_y [6, 1]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[  77 1470 1201 ..., 4375 4601 2744]
[False False False ..., False False False]
closest_y [0, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1284   69 1166 ..., 4601 2744  504]
[False False False ..., False False False]
closest_y [9, 1]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3116 3845   69 ...,  790 2744 4601]
[False False False ..., False False False]
closest_y [8, 1]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4477 2156 3607 ..., 4688 3355 3837]
[False False False ..., False False False]
closest_y [8, 1]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2247 1243 3829 ..., 2744 4601 3286]
[False False False ..., False False False]
closest_y [9, 8]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1122 1613  856 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [8, 9]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2605 2106 3739 ..., 4500  735 4601]
[False False False ..., False False False]
closest_y [2, 4]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[4477 2156 3607 ..., 4921 4688 3837]
[False False False ..., False False False]
closest_y [1, 3]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[1832 4905 4224 ..., 1342 4601 4418]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2507  850 2959 ...,  790 2744 4601]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[3376 4208 2867 ..., 1766 3746 4940]
[False False False ..., False False False]
closest_y [1, 4]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 914 1367 4033 ..., 4601 4375 2744]
[False False False ..., False False False]
closest_y [7, 0]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 299 3412 1991 ..., 4348 4601 3205]
[False False False ..., False False False]
closest_y [5, 5]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1530 2666 2211 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [4, 5]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[2831 2764 2573 ..., 2744 4601  504]
[False False False ..., False False False]
closest_y [2, 8]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 982 4029 4159 ..., 4101 1387 4940]
[False False False ..., False False False]
closest_y [7, 7]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1881 2730  420 ..., 4375 2744 4601]
[False False False ..., False False False]
closest_y [9, 0]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[2003  185 3478 ..., 1387 4921 4688]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2003 3573 2137 ..., 1387 4921 4688]
[False False False ..., False False False]
closest_y [5, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4801  399 4969 ..., 2744 4601 4500]
[False False False ..., False False False]
closest_y [2, 8]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[2745 4310 3529 ..., 3205 4348 4271]
[False False False ..., False False False]
closest_y [4, 9]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2839 4758 1162 ..., 2744 1342 4601]
[False False False ..., False False False]
closest_y [4, 6]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4106  878 1427 ...,  735 4645 4601]
[False False False ..., False False False]
closest_y [6, 0]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4493  626 2968 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [7, 8]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2213 2859   69 ..., 3467 4940 4656]
[False False False ..., False False False]
closest_y [6, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2096  126 1770 ..., 3837 3035 4688]
[False False False ..., False False False]
closest_y [4, 6]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2212 2546 2859 ..., 1387 4940 4921]
[False False False ..., False False False]
closest_y [6, 9]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4297 4426   10 ..., 2744  735 4601]
[False False False ..., False False False]
closest_y [2, 0]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3627 2859  982 ..., 4940 4921 1387]
[False False False ..., False False False]
closest_y [0, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1787 3979 2079 ..., 4400 1387 4940]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 383  254 4398 ..., 1387 3286 4940]
[False False False ..., False False False]
closest_y [2, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1283 3376  383 ..., 1387 3035 4940]
[False False False ..., False False False]
closest_y [5, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2150 1367 4946 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [9, 0]
<type 'list'> <built-in method count of list object at 0x123d69200>
[3787 4197  918 ..., 4375 4601 2744]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[3144 3607 2172 ..., 4940 4921 1387]
[False False False ..., False False False]
closest_y [5, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1027 2154 3376 ..., 4940 3746 1766]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4571 3977 1431 ..., 1527 4645  735]
[False False False ..., False False False]
closest_y [3, 7]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[1746 2983 2698 ..., 1342 4418 4601]
[False False False ..., False False False]
closest_y [0, 6]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 337 3739  951 ..., 2412 4601 1363]
[False False False ..., False False False]
closest_y [7, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2684 2946 3249 ..., 1342 4348 4418]
[False False False ..., False False False]
closest_y [9, 9]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[3623 1284 1235 ..., 4375 2744  504]
[False False False ..., False False False]
closest_y [9, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 887  552  372 ..., 2744 4601  735]
[False False False ..., False False False]
closest_y [9, 7]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2796 3376 2867 ..., 2439 1387 4940]
[False False False ..., False False False]
closest_y [1, 3]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 105 1853  207 ...,  134 3467 4940]
[False False False ..., False False False]
closest_y [5, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 811 2715 3304 ..., 4400 4940 1387]
[False False False ..., False False False]
closest_y [9, 4]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1826 4527 1500 ..., 3205 1527 4601]
[False False False ..., False False False]
closest_y [8, 5]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 359 4579 1201 ..., 4601 4375 2744]
[False False False ..., False False False]
closest_y [8, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4540 4096 1439 ..., 4921 4940 1387]
[False False False ..., False False False]
closest_y [5, 3]
<type 'list'> <built-in method count of list object at 0x123d69200>
[  69 3939 2603 ..., 4601 2263 2814]
[False False False ..., False False False]
closest_y [8, 8]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4594 1640 4643 ..., 1766 1387 4940]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[1141 3043  420 ..., 4601  504 1342]
[False False False ..., False False False]
closest_y [7, 6]
<type 'list'> <built-in method count of list object at 0x123d69200>
[3847  420 2372 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [0, 7]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[1838  347 2372 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [2, 2]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[2894 1162 3065 ..., 4601 1342  504]
[False False False ..., False False False]
closest_y [0, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1161 1535 1271 ...,  816 4601 2744]
[False False False ..., False False False]
closest_y [6, 2]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2573 4224 1832 ..., 2744 4601  504]
[False False False ..., False False False]
closest_y [1, 5]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[3166 1777  243 ..., 4645 4601  735]
[False False False ..., False False False]
closest_y [9, 3]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1178 4941  757 ..., 3467 3286 4940]
[False False False ..., False False False]
closest_y [7, 0]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2229 3579  557 ..., 4940 1387 3286]
[False False False ..., False False False]
closest_y [2, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 420 1838 4550 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [9, 6]
<type 'list'> <built-in method count of list object at 0x123d69200>
[3383 4106 4482 ..., 4645  735 4601]
[False False False ..., False False False]
closest_y [2, 2]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[3608 3997  982 ..., 4688 3035 4940]
[False False False ..., False False False]
closest_y [7, 8]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[ 337 4695  951 ..., 4645 4271 4601]
[False False False ..., False False False]
closest_y [2, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 986 3423  420 ..., 4601 1527 4418]
[False False False ..., False False False]
closest_y [4, 7]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1677 4905 2779 ..., 2744 4271 4601]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[2172  406 2192 ..., 3035 4921 1387]
[False False False ..., False False False]
closest_y [9, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1643  420 4577 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 982 4527  120 ..., 1766 1387 4940]
[False False False ..., False False False]
closest_y [6, 6]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[1933 2005 2745 ..., 2744 4601 3205]
[False False False ..., False False False]
closest_y [5, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1838 2812  622 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [7, 7]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1323 1229 4320 ..., 3837  504 3355]
[False False False ..., False False False]
closest_y [9, 3]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[2730 3797  452 ..., 4375 4601 2744]
[False False False ..., False False False]
closest_y [5, 4]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 974 2034 4683 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [3, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4645 2176 1787 ..., 4400 1387 4940]
[False False False ..., False False False]
closest_y [8, 9]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[2982 2066   80 ..., 1527 4601 4271]
[False False False ..., False False False]
closest_y [5, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2017  820 3962 ..., 2412 3746 1766]
[False False False ..., False False False]
closest_y [9, 7]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4755 1120 4224 ..., 4375 2744  504]
[False False False ..., False False False]
closest_y [7, 7]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[ 254  933 1500 ..., 2744 4601  735]
[False False False ..., False False False]
closest_y [7, 4]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4108 1777 3524 ...,  735 4418 4601]
[False False False ..., False False False]
closest_y [8, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 420 3684  564 ..., 2744 4271 4601]
[False False False ..., False False False]
closest_y [1, 7]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[4808 2522 1991 ..., 3286 4273 4940]
[False False False ..., False False False]
closest_y [4, 0]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1271 3960 4637 ..., 4855 4601 4418]
[False False False ..., False False False]
closest_y [3, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2112 4426 1596 ...,  790 2744 4601]
[False False False ..., False False False]
closest_y [3, 2]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[ 931 4969 2943 ..., 2744  735 4601]
[False False False ..., False False False]
closest_y [4, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1016 2836    3 ..., 1342 4271 4601]
[False False False ..., False False False]
closest_y [8, 4]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2894 1092  526 ..., 4601 1527  504]
[False False False ..., False False False]
closest_y [9, 3]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[ 420 4224 1500 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [4, 0]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2266 2197   42 ..., 4601 1527 4271]
[False False False ..., False False False]
closest_y [7, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3948  716 1500 ..., 2744 4601 1527]
[False False False ..., False False False]
closest_y [3, 1]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[3077 2310 4090 ..., 3286 4921 4564]
[False False False ..., False False False]
closest_y [2, 5]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4200 3693 4801 ..., 2065 4601  735]
[False False False ..., False False False]
closest_y [8, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2953 4134 2690 ..., 4940 1387 4921]
[False False False ..., False False False]
closest_y [2, 4]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[3164 2213 4224 ...,  735 2744  504]
[False False False ..., False False False]
closest_y [9, 2]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4687 3245 3540 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [8, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2573 1746 2121 ...,  504 2744 4601]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x1139bc998>
[4583 3178 3663 ..., 2744 1527 4601]
[False False False ..., False False False]
closest_y [6, 5]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[3873  420 4959 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [0, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1797 2797 2483 ...,  504 3837 3355]
[False False False ..., False False False]
closest_y [6, 2]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4056 2598 2478 ..., 4656 1387 4940]
[False False False ..., False False False]
closest_y [6, 1]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4208  982 4527 ...,  504  735 4940]
[False False False ..., False False False]
closest_y [8, 1]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2106 3408  933 ..., 3286 4564 4940]
[False False False ..., False False False]
closest_y [3, 3]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 985 3506 1959 ..., 4601 2744  504]
[False False False ..., False False False]
closest_y [8, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2034 3918  557 ..., 1387 3286 4940]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4808 4163 4905 ..., 4273 4564 4331]
[False False False ..., False False False]
closest_y [3, 7]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4577 1162 4066 ..., 2744 1342 4601]
[False False False ..., False False False]
closest_y [9, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 180 3423 2730 ...,  790 2744 4601]
[False False False ..., False False False]
closest_y [8, 1]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1221 1366 2949 ..., 1977 4940 2412]
[False False False ..., False False False]
closest_y [6, 4]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[ 804 2133 4703 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [0, 9]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[1993 1261 1056 ..., 4273 3286 4564]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1284  716 3948 ..., 1342 1527  504]
[False False False ..., False False False]
closest_y [4, 0]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[4618 4770  849 ..., 4418 4601 1527]
[False False False ..., False False False]
closest_y [0, 7]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2595  420  399 ..., 2744  735 4601]
[False False False ..., False False False]
closest_y [2, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2166 2192 3665 ..., 4590 3837 3355]
[False False False ..., False False False]
closest_y [9, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[1965 3586 4897 ..., 3035 1387 4940]
[False False False ..., False False False]
closest_y [9, 6]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 933 2796  130 ..., 4656 1387 4940]
[False False False ..., False False False]
closest_y [8, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 767 2794 2868 ..., 2907 1387 4921]
[False False False ..., False False False]
closest_y [6, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[2796 3376  403 ..., 4656 1387 4940]
[False False False ..., False False False]
closest_y [0, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 951  337  537 ...,  735 4645 4601]
[False False False ..., False False False]
closest_y [4, 9]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1092  170 4583 ...,  504 3205 4601]
[False False False ..., False False False]
closest_y [0, 7]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[1413 3063 2526 ..., 4337 3837  504]
[False False False ..., False False False]
closest_y [9, 4]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 196 4304 2725 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2859  490 3028 ..., 4940 1387 4921]
[False False False ..., False False False]
closest_y [6, 8]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[ 971 1720 1261 ..., 1387 4688 3286]
[False False False ..., False False False]
closest_y [6, 6]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 733 2330 1162 ..., 4601 3205 4271]
[False False False ..., False False False]
closest_y [9, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4592 4683 4527 ..., 4656 1387 4940]
[False False False ..., False False False]
closest_y [4, 7]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[1770 1597 4539 ..., 4940 1387 4921]
[False False False ..., False False False]
closest_y [6, 1]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2520 1459  622 ..., 4645 4601  735]
[False False False ..., False False False]
closest_y [0, 4]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3987 4755 1162 ..., 4601  504 1342]
[False False False ..., False False False]
closest_y [4, 8]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4919 3549 3259 ..., 4500 3199  735]
[False False False ..., False False False]
closest_y [0, 6]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4153  980 2922 ..., 4273 2744 3205]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2796  383 3376 ..., 3035 1387 4940]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2833  600 1770 ..., 2814 4688 4921]
[False False False ..., False False False]
closest_y [8, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2995 3380 3573 ..., 4921 1387 3355]
[False False False ..., False False False]
closest_y [2, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 909 1166 1284 ...,  504 4601 2744]
[False False False ..., False False False]
closest_y [7, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2253 3226 2787 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [8, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[1273  271 3606 ...,  790 2744 4601]
[False False False ..., False False False]
closest_y [9, 7]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4828  290 3250 ..., 4940 3035 1387]
[False False False ..., False False False]
closest_y [3, 6]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1092  558 1295 ..., 1527 4601  504]
[False False False ..., False False False]
closest_y [5, 9]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 420 2372 3178 ..., 2744 1527 4601]
[False False False ..., False False False]
closest_y [8, 4]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[3193 2372 2983 ..., 1342 2744 4601]
[False False False ..., False False False]
closest_y [4, 6]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 420 4583 2725 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [1, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 139  909 1711 ..., 3035 4688 2814]
[False False False ..., False False False]
closest_y [5, 9]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 317 4573 2349 ..., 1766 1387 4940]
[False False False ..., False False False]
closest_y [5, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 974  743 3579 ...,  134 1387 4940]
[False False False ..., False False False]
closest_y [4, 4]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[3178 2983 1838 ..., 4375 2744 4601]
[False False False ..., False False False]
closest_y [1, 0]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4645 2744 4601 ..., 4400 1387 4940]
[False False False ..., False False False]
closest_y [6, 0]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1092 4887  909 ...,  790 2744  504]
[False False False ..., False False False]
closest_y [3, 4]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2712 3569 3797 ..., 4500 4271 4601]
[False False False ..., False False False]
closest_y [6, 8]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[2993 2540  767 ..., 1661 2907 2412]
[False False False ..., False False False]
closest_y [2, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2276 2925  827 ..., 2412 4940 2907]
[False False False ..., False False False]
closest_y [7, 1]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 906  420 4235 ...,  790 2744 4601]
[False False False ..., False False False]
closest_y [2, 1]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3259  220 2610 ..., 1342 2744 4601]
[False False False ..., False False False]
closest_y [8, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[3418  990  933 ..., 3205  504  735]
[False False False ..., False False False]
closest_y [8, 9]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[1842 2479  291 ..., 1342  735 4418]
[False False False ..., False False False]
closest_y [7, 7]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4007 3768 1521 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [5, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2465 2106  692 ..., 2744 4500 4601]
[False False False ..., False False False]
closest_y [0, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 420 2854 1867 ..., 4689 4271 4601]
[False False False ..., False False False]
closest_y [1, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1220 3213 4772 ..., 4500  735 4601]
[False False False ..., False False False]
closest_y [7, 1]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4774 2894 2156 ..., 3837 3205  504]
[False False False ..., False False False]
closest_y [3, 0]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4221 3634 3263 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [4, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4858  219 1171 ..., 1387 3035 4921]
[False False False ..., False False False]
closest_y [8, 2]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1282  336 3826 ..., 4645 4271 4601]
[False False False ..., False False False]
closest_y [0, 6]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4750 1158 4935 ..., 2412 3035 4940]
[False False False ..., False False False]
closest_y [3, 1]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 566 4287  811 ..., 4400 1387 4921]
[False False False ..., False False False]
closest_y [2, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[4053  749 2325 ..., 3355 1328  504]
[False False False ..., False False False]
closest_y [0, 4]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[  10 4217 2124 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [4, 1]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1533  456 1376 ..., 3746 4940 3286]
[False False False ..., False False False]
closest_y [4, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1264 4715  927 ...,  735 2744 4601]
[False False False ..., False False False]
closest_y [0, 0]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4540  698 3634 ..., 4940 4921 1387]
[False False False ..., False False False]
closest_y [1, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[3328 3889  557 ..., 4940 4921 1387]
[False False False ..., False False False]
closest_y [9, 4]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1284 2859  982 ..., 4940 4921 1387]
[False False False ..., False False False]
closest_y [7, 0]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[1278 2918 2172 ..., 4921 4400 1387]
[False False False ..., False False False]
closest_y [4, 1]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[2540  658 3372 ..., 2439 2907 4940]
[False False False ..., False False False]
closest_y [8, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[1746 4905   58 ..., 4375 4601 2744]
[False False False ..., False False False]
closest_y [0, 7]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[2224  408 1361 ..., 3286 4272  735]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[1277 4812  139 ..., 4590 1513 3837]
[False False False ..., False False False]
closest_y [9, 5]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 695 2598 3438 ..., 1766 3746 4940]
[False False False ..., False False False]
closest_y [2, 6]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4393 2745 1053 ..., 4601 1342 3205]
[False False False ..., False False False]
closest_y [1, 9]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[1881 4411 4604 ..., 4348 3205 4601]
[False False False ..., False False False]
closest_y [0, 6]
<type 'list'> <built-in method count of list object at 0x123d69200>
[3784  558  722 ...,  504 1363 3837]
[False False False ..., False False False]
closest_y [1, 2]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[ 781  850 4426 ..., 2744 4645 4601]
[False False False ..., False False False]
closest_y [3, 4]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[3408 3031 2716 ...,  259 1731  735]
[False False False ..., False False False]
closest_y [9, 9]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 982   69 4277 ..., 1387 2814 4921]
[False False False ..., False False False]
closest_y [1, 4]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[4087  918  682 ..., 4375 2744 4601]
[False False False ..., False False False]
closest_y [2, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[ 933  403 4090 ..., 4656 1387 4940]
[False False False ..., False False False]
closest_y [5, 6]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2003 4226 2160 ..., 3355 1387 4921]
[False False False ..., False False False]
closest_y [9, 1]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[1842 3060 1600 ..., 4418 4273 1342]
[False False False ..., False False False]
closest_y [2, 4]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[3377 4224 2922 ...,  735 2744 4601]
[False False False ..., False False False]
closest_y [0, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[4491 1525 2966 ..., 4375 2744 4601]
[False False False ..., False False False]
closest_y [3, 7]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[3892 2127 3411 ..., 1977 3467 4940]
[False False False ..., False False False]
closest_y [6, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[1867 1910   80 ..., 1342  735 4601]
[False False False ..., False False False]
closest_y [5, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[3493 2707 3176 ..., 4921 4400 1387]
[False False False ..., False False False]
closest_y [1, 1]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[3873 1314 3173 ..., 4418 4601 4271]
[False False False ..., False False False]
closest_y [3, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4770  299  345 ..., 3205 1527 4601]
[False False False ..., False False False]
closest_y [8, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[1092 1284 4887 ..., 4601  504 2744]
[False False False ..., False False False]
closest_y [5, 6]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2943 1875 4969 ..., 4500 4601  735]
[False False False ..., False False False]
closest_y [7, 9]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 882 1284 4298 ..., 1527 2744  504]
[False False False ..., False False False]
closest_y [1, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2842 3245 2116 ..., 2744 4645 4601]
[False False False ..., False False False]
closest_y [7, 8]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1530  334 1596 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [4, 0]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4661 4349  804 ...,  504 2744 4601]
[False False False ..., False False False]
closest_y [5, 3]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[ 592 2575 1832 ..., 1387 3286 4940]
[False False False ..., False False False]
closest_y [2, 7]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[  10  910 4007 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [1, 7]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[1557 4492 4643 ..., 1363 1527 3837]
[False False False ..., False False False]
closest_y [5, 2]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[1711 1141  139 ...,  504 3355 3837]
[False False False ..., False False False]
closest_y [6, 0]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[3587  171 2550 ..., 3286 4518 4331]
[False False False ..., False False False]
closest_y [8, 6]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 673 1126 4232 ..., 4500 4601  735]
[False False False ..., False False False]
closest_y [3, 6]
<type 'list'> <built-in method count of list object at 0x1139e0ef0>
[2859 1284 4868 ..., 4921 1387  504]
[False False False ..., False False False]
closest_y [9, 8]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2460 1787 2808 ..., 3286 1387 4940]
[False False False ..., False False False]
closest_y [7, 9]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2543 3376 1283 ..., 3035 1387 4940]
[False False False ..., False False False]
closest_y [0, 5]
<type 'list'> <built-in method count of list object at 0x1139cc170>
[2867 2034  348 ..., 1387 3286 4940]
[False False False ..., False False False]
closest_y [4, 6]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1563 1374 2510 ...,  735 4601 4645]
[False False False ..., False False False]
closest_y [0, 1]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[  31 1156  170 ..., 3205  504 3837]
[False False False ..., False False False]
closest_y [3, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3953  882 2779 ..., 2744 3205 4564]
[False False False ..., False False False]
closest_y [2, 3]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1686 1065 2543 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [0, 3]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[3984 1897 1253 ..., 4656 3467 4940]
[False False False ..., False False False]
closest_y [2, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2543 2710 1030 ..., 3467 3286 4940]
[False False False ..., False False False]
closest_y [0, 9]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2983 3797 3558 ..., 1342 4418 4601]
[False False False ..., False False False]
closest_y [3, 1]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[2812 1968  830 ..., 4271 4645 4601]
[False False False ..., False False False]
closest_y [7, 9]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 243 2130 4108 ..., 4271  735 4601]
[False False False ..., False False False]
closest_y [5, 4]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[ 882 2881 3246 ..., 1387 3355 4921]
[False False False ..., False False False]
closest_y [4, 9]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 521 4015 1762 ..., 3199 3978  735]
[False False False ..., False False False]
closest_y [6, 0]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 287 4429 4703 ..., 4271  735 4601]
[False False False ..., False False False]
closest_y [4, 7]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[1067 2998 1542 ..., 3205  735 4720]
[False False False ..., False False False]
closest_y [6, 4]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4905 2266 3684 ..., 4271 4601 4273]
[False False False ..., False False False]
closest_y [6, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2868  982 4113 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [8, 2]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2213 2091  571 ..., 1387 3467 4940]
[False False False ..., False False False]
closest_y [3, 8]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 158 1019 3167 ..., 1342 3205 4418]
[False False False ..., False False False]
closest_y [6, 2]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[2868 4540 2867 ..., 3035 1387 4940]
[False False False ..., False False False]
closest_y [9, 6]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[4294 3632  337 ...,  834 4940 1363]
[False False False ..., False False False]
closest_y [1, 0]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[1926  933  216 ..., 4601 3737 4271]
[False False False ..., False False False]
closest_y [0, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[3480   10 2372 ..., 4375 2744 4601]
[False False False ..., False False False]
closest_y [0, 1]
<type 'list'> <built-in method count of list object at 0x123e4cd88>
[2553 1366  272 ..., 3626 3467 4940]
[False False False ..., False False False]
closest_y [0, 7]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 328 4338 1166 ..., 1342 3205  504]
[False False False ..., False False False]
closest_y [5, 0]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[2415 4723 1404 ..., 1387 4940 3286]
[False False False ..., False False False]
closest_y [4, 7]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[4350 3448 2378 ..., 3199 4564 3626]
[False False False ..., False False False]
closest_y [8, 0]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2922 1318 4864 ...,  735 4601 4271]
[False False False ..., False False False]
closest_y [0, 0]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[4224 3164 3418 ..., 2744  735 4601]
[False False False ..., False False False]
closest_y [2, 4]
<type 'list'> <built-in method count of list object at 0x123dc43b0>
[ 983  126  704 ..., 3616 4688 3837]
[False False False ..., False False False]
closest_y [5, 9]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[4703 1018 1038 ...,  735 4500 4601]
[False False False ..., False False False]
closest_y [7, 3]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 558 3116 2069 ..., 4645 4601 1527]
[False False False ..., False False False]
closest_y [4, 8]
<type 'list'> <built-in method count of list object at 0x123d69200>
[ 901 4159 4935 ..., 1387 3035 4940]
[False False False ..., False False False]
closest_y [9, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[3193 2836 3797 ..., 4271 2744 4601]
[False False False ..., False False False]
closest_y [4, 3]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[2859   69  600 ..., 4940 1387 4921]
[False False False ..., False False False]
closest_y [1, 1]
<type 'list'> <built-in method count of list object at 0x123d69200>
[2943 4905 3377 ..., 4375 4601 2744]
[False False False ..., False False False]
closest_y [3, 0]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[ 820 3554  571 ..., 3035 1387 4940]
[False False False ..., False False False]
closest_y [7, 4]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[3874 1092 3063 ...,  790 2744  504]
[False False False ..., False False False]
closest_y [6, 4]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[1185 3677  753 ..., 3035 3355 4940]
[False False False ..., False False False]
closest_y [0, 5]
<type 'list'> <built-in method count of list object at 0x1139bcdd0>
[ 420 1867 2989 ..., 4645 2744 4601]
[False False False ..., False False False]
closest_y [4, 0]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 974 4540 3039 ..., 4921 1387 4940]
[False False False ..., False False False]
closest_y [3, 4]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[ 557 1009 2333 ..., 4940 1387 3286]
[False False False ..., False False False]
closest_y [0, 8]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[3469  716  564 ..., 4601 3205 2744]
[False False False ..., False False False]
closest_y [1, 5]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[ 749 2325 3488 ...,  790 4645  504]
[False False False ..., False False False]
closest_y [8, 4]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[1431  982 4303 ..., 3035 2814 4688]
[False False False ..., False False False]
closest_y [8, 9]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[2830 3678 1917 ..., 4601 2744  735]
[False False False ..., False False False]
closest_y [4, 0]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4758 1162 4233 ..., 4601 3837 4271]
[False False False ..., False False False]
closest_y [6, 5]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[1853 4082 2014 ..., 3467 1387 4940]
[False False False ..., False False False]
closest_y [0, 5]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[4283  529 3970 ..., 1342 4601 2744]
[False False False ..., False False False]
closest_y [8, 6]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
[4398  765  349 ..., 4940 2412 3286]
[False False False ..., False False False]
closest_y [2, 6]
<type 'list'> <built-in method count of list object at 0x123dc4c20>
[4224 2875  933 ..., 4689 2744 4601]
[False False False ..., False False False]
closest_y [3, 0]
<type 'list'> <built-in method count of list object at 0x1139e0ab8>
[3979 3382 4645 ..., 1843 1387 4940]
[False False False ..., False False False]
closest_y [2, 6]
<type 'list'> <built-in method count of list object at 0x1139bc6c8>
Got 46 / 500 correct => accuracy: 0.092000

``````
``````

In [10]:

# Now lets speed up distance matrix computation by using partial vectorization
# with one loop. Implement the function compute_distances_one_loop and run the
# code below:
dists_one = classifier.compute_distances_one_loop(X_test)

# To ensure that our vectorized implementation is correct, we make sure that it
# agrees with the naive implementation. There are many ways to decide whether
# two matrices are similar; one of the simplest is the Frobenius norm. In case
# you haven't seen it before, the Frobenius norm of two matrices is the square
# root of the squared sum of differences of all elements; in other words, reshape
# the matrices into vectors and compute the Euclidean distance between them.
difference = np.linalg.norm(dists - dists_one, ord='fro')
print 'Difference was: %f' % (difference, )
if difference < 0.001:
print 'Good! The distance matrices are the same'
else:
print 'Uh-oh! The distance matrices are different'

``````
``````

Difference was: 0.000000
Good! The distance matrices are the same

``````
``````

In [11]:

# Now implement the fully vectorized version inside compute_distances_no_loops
# and run the code
dists_two = classifier.compute_distances_no_loops(X_test)

# check that the distance matrix agrees with the one we computed before:
difference = np.linalg.norm(dists - dists_two, ord='fro')
print 'Difference was: %f' % (difference, )
if difference < 0.001:
print 'Good! The distance matrices are the same'
else:
print 'Uh-oh! The distance matrices are different'

``````
``````

Difference was: 0.000000
Good! The distance matrices are the same

``````
``````

In [12]:

# Let's compare how fast the implementations are
def time_function(f, *args):
"""
Call a function f with args and return the time (in seconds) that it took to execute.
"""
import time
tic = time.time()
f(*args)
toc = time.time()

two_loop_time = time_function(classifier.compute_distances_two_loops, X_test)
print 'Two loop version took %f seconds' % two_loop_time

one_loop_time = time_function(classifier.compute_distances_one_loop, X_test)
print 'One loop version took %f seconds' % one_loop_time

no_loop_time = time_function(classifier.compute_distances_no_loops, X_test)
print 'No loop version took %f seconds' % no_loop_time

# you should see significantly faster performance with the fully vectorized implementation

``````
``````

500 5000
[[ 3803.92350081  4210.59603857  5504.0544147  ...,  4007.64756434
4203.28086142  4354.20256764]
[ 6336.83367306  5270.28006846  4040.63608854 ...,  4829.15334194
4694.09767687  7768.33347636]
[ 5224.83913628  4250.64289255  3773.94581307 ...,  3766.81549853
4464.99921613  6353.57190878]
...,
[ 5366.93534524  5062.8772452   6361.85774755 ...,  5126.56824786
4537.30613911  5920.94156364]
[ 3671.92919322  3858.60765044  4846.88157479 ...,  3521.04515734
3182.3673578   4448.65305458]
[ 6960.92443573  6083.71366848  6338.13442584 ...,  6083.55504619
4128.24744898  8041.05223214]]
Two loop version took 385.572062 seconds
One loop version took 373.968438 seconds
No loop version took 1.359446 seconds

``````

### Cross-validation

We have implemented the k-Nearest Neighbor classifier but we set the value k = 5 arbitrarily. We will now determine the best value of this hyperparameter with cross-validation.

``````

In [29]:

num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]

X_train_folds = []
y_train_folds = []
################################################################################
# TODO:                                                                        #
# Split up the training data into folds. After splitting, X_train_folds and    #
# y_train_folds should each be lists of length num_folds, where                #
# y_train_folds[i] is the label vector for the points in X_train_folds[i].     #
# Hint: Look up the numpy array_split function.                                #
################################################################################
X_train_folds = np.split(X_train,indices_or_sections=num_folds)
y_train_folds = np.split(y_train,indices_or_sections=num_folds)
#l = X_train.tolist()
#print l[0],len(l[0])
#print X_train_folds[0][0]
#print np.nonzero(X_train == X_train_folds[0][0])
#print X_train[0] == X_train_folds[0][0]
#print X_train[0]

#X_train[]
#print l.index(X_train_folds[0][0])
#print np.where(X_train == X_train_folds[0][0])[0].shape
# y_i = l.index(X_train_folds[0][0]) # i will return index of 2
#print y_train_folds[2][0]
#print y_train[2000]
#assert y_train_folds[0][0] == y_train[0]
pass
################################################################################
#                                 END OF YOUR CODE                             #
################################################################################

# A dictionary holding the accuracies for different values of k that we find
# when running cross-validation. After running cross-validation,
# k_to_accuracies[k] should be a list of length num_folds giving the different
# accuracy values that we found when using that value of k.
k_to_accuracies = {}

################################################################################
# TODO:                                                                        #
# Perform k-fold cross validation to find the best value of k. For each        #
# possible value of k, run the k-nearest-neighbor algorithm num_folds times,   #
# where in each case you use all but one of the folds as training data and the #
# last fold as a validation set. Store the accuracies for all fold and all     #
# values of k in the k_to_accuracies dictionary.                               #
################################################################################
for k in k_choices:
accuracies = []
for j in range(num_folds):
# train the classifier using each X_train fold with k
X_train_cv = np.vstack(X_train_folds[0:j]+ X_train_folds[j+1:])
X_test_cv = X_train_folds[j]

y_train_cv = np.hstack(y_train_folds[0:j]+ y_train_folds[j+1:])
y_test_cv = y_train_folds[j]

classifier.train(X_train_cv,y_train_cv)
dist_cv = classifier.compute_distances_no_loops(X_test_cv)
print dist_cv.shape
print "some list"
print dist_cv[0][0][0][0].shape
y_test_pred = classifier.predict_labels(dist_cv,k)
num_correct = np.sum(y_test_pred == y_test_cv)
accuracy = float(num_correct) / len(y_test)
print 'Got %d / %d correct => accuracy: %f %%' % (num_correct, num_test, accuracy*100.0)
accuracies.append(accuracy)
k_to_accuracies[k] = accuracies
# pass
# ################################################################################
# #                                 END OF YOUR CODE                             #
# ################################################################################

# Print out the computed accuracies
for k in sorted(k_to_accuracies):
for accuracy in k_to_accuracies[k]:
print 'k = %d, accuracy = %f' % (k, accuracy)

``````
``````

(1000, 4000)
some list
(1, 4000)
Got 263 / 500 correct => accuracy: 52.600000 %
(1000, 4000)
some list
(1, 4000)
Got 257 / 500 correct => accuracy: 51.400000 %
(1000, 4000)
some list
(1, 4000)
Got 264 / 500 correct => accuracy: 52.800000 %
(1000, 4000)
some list
(1, 4000)
Got 278 / 500 correct => accuracy: 55.600000 %
(1000, 4000)
some list
(1, 4000)
Got 266 / 500 correct => accuracy: 53.200000 %
(1000, 4000)
some list
(1, 4000)
Got 241 / 500 correct => accuracy: 48.200000 %
(1000, 4000)
some list
(1, 4000)
Got 249 / 500 correct => accuracy: 49.800000 %
(1000, 4000)
some list
(1, 4000)
Got 243 / 500 correct => accuracy: 48.600000 %
(1000, 4000)
some list
(1, 4000)
Got 273 / 500 correct => accuracy: 54.600000 %
(1000, 4000)
some list
(1, 4000)
Got 264 / 500 correct => accuracy: 52.800000 %
(1000, 4000)
some list
(1, 4000)
Got 258 / 500 correct => accuracy: 51.600000 %
(1000, 4000)
some list
(1, 4000)
Got 273 / 500 correct => accuracy: 54.600000 %
(1000, 4000)
some list
(1, 4000)
Got 281 / 500 correct => accuracy: 56.200000 %
(1000, 4000)
some list
(1, 4000)
Got 290 / 500 correct => accuracy: 58.000000 %
(1000, 4000)
some list
(1, 4000)
Got 272 / 500 correct => accuracy: 54.400000 %
(1000, 4000)
some list
(1, 4000)
Got 263 / 500 correct => accuracy: 52.600000 %
(1000, 4000)
some list
(1, 4000)
Got 288 / 500 correct => accuracy: 57.600000 %
(1000, 4000)
some list
(1, 4000)
Got 278 / 500 correct => accuracy: 55.600000 %
(1000, 4000)
some list
(1, 4000)
Got 285 / 500 correct => accuracy: 57.000000 %
(1000, 4000)
some list
(1, 4000)
Got 277 / 500 correct => accuracy: 55.400000 %
(1000, 4000)
some list
(1, 4000)
Got 265 / 500 correct => accuracy: 53.000000 %
(1000, 4000)
some list
(1, 4000)
Got 296 / 500 correct => accuracy: 59.200000 %
(1000, 4000)
some list
(1, 4000)
Got 278 / 500 correct => accuracy: 55.600000 %
(1000, 4000)
some list
(1, 4000)
Got 284 / 500 correct => accuracy: 56.800000 %
(1000, 4000)
some list
(1, 4000)
Got 286 / 500 correct => accuracy: 57.200000 %
(1000, 4000)
some list
(1, 4000)
Got 260 / 500 correct => accuracy: 52.000000 %
(1000, 4000)
some list
(1, 4000)
Got 294 / 500 correct => accuracy: 58.800000 %
(1000, 4000)
some list
(1, 4000)
Got 281 / 500 correct => accuracy: 56.200000 %
(1000, 4000)
some list
(1, 4000)
Got 282 / 500 correct => accuracy: 56.400000 %
(1000, 4000)
some list
(1, 4000)
Got 281 / 500 correct => accuracy: 56.200000 %
(1000, 4000)
some list
(1, 4000)
Got 255 / 500 correct => accuracy: 51.000000 %
(1000, 4000)
some list
(1, 4000)
Got 290 / 500 correct => accuracy: 58.000000 %
(1000, 4000)
some list
(1, 4000)
Got 281 / 500 correct => accuracy: 56.200000 %
(1000, 4000)
some list
(1, 4000)
Got 281 / 500 correct => accuracy: 56.200000 %
(1000, 4000)
some list
(1, 4000)
Got 276 / 500 correct => accuracy: 55.200000 %
(1000, 4000)
some list
(1, 4000)
Got 270 / 500 correct => accuracy: 54.000000 %
(1000, 4000)
some list
(1, 4000)
Got 281 / 500 correct => accuracy: 56.200000 %
(1000, 4000)
some list
(1, 4000)
Got 280 / 500 correct => accuracy: 56.000000 %
(1000, 4000)
some list
(1, 4000)
Got 282 / 500 correct => accuracy: 56.400000 %
(1000, 4000)
some list
(1, 4000)
Got 284 / 500 correct => accuracy: 56.800000 %
(1000, 4000)
some list
(1, 4000)
Got 271 / 500 correct => accuracy: 54.200000 %
(1000, 4000)
some list
(1, 4000)
Got 288 / 500 correct => accuracy: 57.600000 %
(1000, 4000)
some list
(1, 4000)
Got 278 / 500 correct => accuracy: 55.600000 %
(1000, 4000)
some list
(1, 4000)
Got 269 / 500 correct => accuracy: 53.800000 %
(1000, 4000)
some list
(1, 4000)
Got 266 / 500 correct => accuracy: 53.200000 %
(1000, 4000)
some list
(1, 4000)
Got 256 / 500 correct => accuracy: 51.200000 %
(1000, 4000)
some list
(1, 4000)
Got 270 / 500 correct => accuracy: 54.000000 %
(1000, 4000)
some list
(1, 4000)
Got 263 / 500 correct => accuracy: 52.600000 %
(1000, 4000)
some list
(1, 4000)
Got 256 / 500 correct => accuracy: 51.200000 %
(1000, 4000)
some list
(1, 4000)
Got 263 / 500 correct => accuracy: 52.600000 %
k = 1, accuracy = 0.526000
k = 1, accuracy = 0.514000
k = 1, accuracy = 0.528000
k = 1, accuracy = 0.556000
k = 1, accuracy = 0.532000
k = 3, accuracy = 0.482000
k = 3, accuracy = 0.498000
k = 3, accuracy = 0.486000
k = 3, accuracy = 0.546000
k = 3, accuracy = 0.528000
k = 5, accuracy = 0.516000
k = 5, accuracy = 0.546000
k = 5, accuracy = 0.562000
k = 5, accuracy = 0.580000
k = 5, accuracy = 0.544000
k = 8, accuracy = 0.526000
k = 8, accuracy = 0.576000
k = 8, accuracy = 0.556000
k = 8, accuracy = 0.570000
k = 8, accuracy = 0.554000
k = 10, accuracy = 0.530000
k = 10, accuracy = 0.592000
k = 10, accuracy = 0.556000
k = 10, accuracy = 0.568000
k = 10, accuracy = 0.572000
k = 12, accuracy = 0.520000
k = 12, accuracy = 0.588000
k = 12, accuracy = 0.562000
k = 12, accuracy = 0.564000
k = 12, accuracy = 0.562000
k = 15, accuracy = 0.510000
k = 15, accuracy = 0.580000
k = 15, accuracy = 0.562000
k = 15, accuracy = 0.562000
k = 15, accuracy = 0.552000
k = 20, accuracy = 0.540000
k = 20, accuracy = 0.562000
k = 20, accuracy = 0.560000
k = 20, accuracy = 0.564000
k = 20, accuracy = 0.568000
k = 50, accuracy = 0.542000
k = 50, accuracy = 0.576000
k = 50, accuracy = 0.556000
k = 50, accuracy = 0.538000
k = 50, accuracy = 0.532000
k = 100, accuracy = 0.512000
k = 100, accuracy = 0.540000
k = 100, accuracy = 0.526000
k = 100, accuracy = 0.512000
k = 100, accuracy = 0.526000

``````
``````

In [30]:

# plot the raw observations
for k in k_choices:
accuracies = k_to_accuracies[k]
plt.scatter([k] * len(accuracies), accuracies)

# plot the trend line with error bars that correspond to standard deviation
accuracies_mean = np.array([np.mean(v) for k,v in sorted(k_to_accuracies.items())])
accuracies_std = np.array([np.std(v) for k,v in sorted(k_to_accuracies.items())])
plt.errorbar(k_choices, accuracies_mean, yerr=accuracies_std)
plt.title('Cross-validation on k')
plt.xlabel('k')
plt.ylabel('Cross-validation accuracy')
plt.show()

``````
``````

``````
``````

In [31]:

# Based on the cross-validation results above, choose the best value for k,
# retrain the classifier using all the training data, and test it on the test
# data.
best_k =10

classifier = KNearestNeighbor()
classifier.train(X_train, y_train)
y_test_pred = classifier.predict(X_test, k=best_k)

# Compute and display the accuracy
num_correct = np.sum(y_test_pred == y_test)
accuracy = float(num_correct) / num_test
print 'Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy)

``````
``````

Got 139 / 500 correct => accuracy: 0.278000

``````
``````

In [ ]:

``````