Implementation of KNN in R I have implemented the K-Nearest Neighbor algorithm with Euclidean distance in R. It works fine but takes tremendously huge time than the library function (get.knn). Please point out the possibility of improvement.

knn&lt;-function(list,k){
  n=nrow(list)
  if (n&lt;=k) stop("k can not be more than n-1")
  neigh&lt;- matrix(0,nrow=n,ncol=k)
  for(i in 1:n){
    dist&lt;-matrix(0,ncol=2,nrow=n)
    for (j in 1:n){
      dist[j,1]&lt;-j
      dist[j,2]&lt;-sum((list[i,]-list[j,])^2)
      #dist[j,2]&lt;-dtw(list[i,],list[j,])$distance
    }
    sorted&lt;-dist[order(dist[,2]),]
    neigh[i,]&lt;-sorted[2:(k+1),1]
  }
  return(neigh)
}
You can improve your code by using vectorization to speed up the computation of Euclidean distances in the inner loop. The code would be:

knn &lt;- function(mat, k){
   n &lt;- nrow(mat)
   if (n &lt;= k) stop("k can not be more than n-1")
   neigh &lt;- matrix(0, nrow = n, ncol = k)
   for(i in 1:n) {
      euc.dist &lt;- colSums((mat[i, ] - t(mat)) ^ 2)  
      neigh[i, ] &lt;- order(euc.dist)[2:(k + 1)]
   }
   return(neigh)
}


Notice that I also made a few changes:


list is a function in R so calling your object list is a pretty bad idea. Also, in the R language, a "list" refers to a very specific data structure, while your code seems to be using a matrix. So calling that input mat seemed more appropriate.
Similarly, there is a dist function in R so it is a bad idea to name your variable this way. I chose euc.dist since you were computing an euclidean distance.
order already returns an index, so the whole idea of column-biding your indices and distances was not necessary: you just need a vector of distances.


The code above might still be a bit too slow because of the computations inside the for loop. If the dimensions of your matrix are not astronomical, you could compute the matrix of distances at first using a compiled function. I once tested about a dozen of packages and found that fields::rdist (written in Fortran) was the fastest. If you do not wish to install it, you can use the base::dist function. The code would look like this:

knn &lt;- function(mat, k){
   n &lt;- nrow(mat)
   if (n &lt;= k) stop("k can not be more than n-1")
   neigh &lt;- matrix(0, nrow = n, ncol = k)
   library(fields)
   dist.mat &lt;- rdist(mat, mat)
   for(i in 1:n) {
      euc.dist &lt;- dist.mat[i, ]
      neigh[i, ] &lt;- order(euc.dist)[2:(k + 1)]
   }
   return(neigh)
}


If my first suggestion is still too slow and your matrix is so large that my second solution cannot be used, you might want to use a mix between the two approaches, where you loop on chunks of rows, i.e. rely on rdist(chunk_of_rows_from_mat, mat). But I'll leave that to you as an exercise :-)

Finally, I will point out that if you are interested, you could search CRAN or the internet for a package that does exactly what you are after. KNN is a  very common tool and there must be packages (compiled from C) that already do it much faster than this code will do. But not much to be learnt there...