title: k-NN GridSearchCV taking extremely long time to execute
body: <p>I am attempting to use sklearn to train a KNN model on the MNIST classification task. When I try to tune my parameters using either sklearn's GridSearchCV or RandomisedSearchCV classes, my code is taking an extremely long time to execute.</p>
  <p>As an experiment, I created a KNN model using KNeighborsClassifier() with the default parameters and passed these same parameters to GridSearchCV. Afaik, this should mean GridSearchCV only has single set of parameters and so should effectively not perform a &quot;search&quot;. I then called the .fit() methods of both on the training data and timed their execution (see code below). The KNN model's .fit() method took about 11 seconds to run, whereas the GridSearchCV model took over 20 minutes.</p>
  <p>I understand that GridSearchCV should take slightly longer as it is performing 5-fold cross validation, but the difference in execution time seems too large for it to be explained by that.</p>
  <p>Am I doing something with my GridSearchCV call that it causing it to take such a long time to execute? And is there anything that I can do to accelerate it?</p>
  <pre class="lang-py prettyprint-override"><code>import sklearn
  import time 
  
  # importing models
  from sklearn.model_selection import StratifiedShuffleSplit
  from sklearn.model_selection import GridSearchCV
  from sklearn.neighbors import KNeighborsClassifier
  
  # Importing data
  from sklearn.datasets import fetch_openml
  mnist = fetch_openml(name='mnist_784')
  
  print(&quot;data loaded&quot;)
  
  # splitting the data into stratified train &amp; test sets
  X, y = mnist.data, mnist.target # mnist mj.data.shape is (n_samples, n_features)
  sss = StratifiedShuffleSplit(n_splits = 1, test_size = 0.2, random_state = 0)
  for train_index, test_index in sss.split(X,y):
      X_train, y_train = X[train_index], y[train_index]
      X_test, y_test = X[test_index], y[test_index]
  
  print(&quot;data split&quot;)
  
  # Data has no missing values and is preprocessed, so no cleaing needed.
  
  # using a KNN model, as recommended
  knn = KNeighborsClassifier()
  
  print(&quot;model created&quot;)
  
  
  print(&quot;training model&quot;)
  start = time.time()
  knn.fit(X_train, y_train)
  end = time.time()
  print(f&quot;Execution time for knn paramSearch was: {end-start}&quot;)
  
  # Parameter tuning.
  # starting by performing a broad-range search on n_neighbours to work out the 
  # rough scale the parameter should be on 
  print(&quot;beginning param tuning&quot;)
  params = {'n_neighbors':[5],
             'weights':['uniform'],
             'leaf_size':[30]
             }
  
  paramSearch = GridSearchCV(
      estimator = knn,
      param_grid = params,
      cv=5,
      n_jobs = -1)
  
  start = time.time()
  paramSearch.fit(X_train, y_train)
  end = time.time()
  print(f&quot;Execution time for knn paramSearch was: {end-start}&quot;)
  </code></pre>