Нахождение индексов ближайших значений

У меня есть два набора координат и пытаюсь найти наиболее близкие совпадения координат. Учитывая, что один набор данных состоит из 1 миллиона записей, а другой - почти полмиллиона записей, он ищет лучший способ выполнить эту задачу и требует предложений.

dput первого набора данных

structure(list(longitude = c(-2.5168477762, -2.5972432832, -2.5936692407, 
-2.5943475677, -2.5923214528, -2.5919014869, -2.5913454553, -2.5835739992, 
-2.5673150195, -2.5683356381), latitude = c(51.4844052488, 51.45278562, 
51.4978889752, 51.4979844501, 51.4983813479, 51.4982126232, 51.4964350456, 
51.4123728037, 51.4266239227, 51.4265740193)), .Names = c("longitude", 
"latitude"), row.names = c(NA, 10L), class = "data.frame")

dput второго набора данных

structure(list(longitude = c(-3.4385392589, -3.4690321528, -3.2723981534, 
-3.3684012246, -3.329625956, -3.3093349806, 0.8718409198, 0.8718563602, 
0.8643998472, 0.8644153057), latitude = c(51.1931124311, 51.206897181, 
51.1271423704, 51.1618047221, 51.1805971356, 51.1663567178, 52.896084336, 
52.896092955, 52.9496082626, 52.9496168824)), .Names = c("longitude", 
"latitude"), row.names = 426608:426617, class = "data.frame")

Я посмотрел на приближение и нашел функции Interval в R, но не понял их полностью, как они работают. То, что я пытаюсь сделать, это взять координаты из набора данных1 и сопоставить их со всеми координатами в наборе данных2, чтобы найти наиболее близкое соответствие. В настоящее время я использую два forloops, но это занимает вечность из-за размера данных.

Код, который я пробовал, приведен ниже:

cns <- function(x,y)
{
 a = NULL
 b = NULL

for(i=1:nrow(x))  
{
  for(j=1:nrow(y)) 
  { 
      a[j]  = distm(c(x$longitude[i],x$latitude[i]),
                c(y$longitude[j],y$latitude[j]),
                fun = distVincentyEllipsoid)

  } 
  b[i] = which(a == min(a))
}
  return(y[b,])
}

Вышеуказанные функции берут одну точку из набора данных 1 и вычисляют расстояние, используя все точки в наборе данных 2, затем находят минимальное расстояние и возвращают координаты этого расстояния.

Поиск может быть параллельной обработки, чтобы выполнить эту задачу в подходящее время. Любые предложения приветствуются.

С Уважением,

Источник

1 ответ

1. Попробуйте векторизовать ваш код

Векторизация часто более эффективна в R, чем в циклах:

  cns2 <- function(x,y){
  b <- numeric(length(nrow(y)))
  for(i in 1:nrow(x)){
    a<- distm(x=x[i,],
                    y=y,
                    fun = distVincentyEllipsoid)

       b[i] = which.min(a)
    }
   return(y[b,])
  }

Давайте оценим разницу:

library(microbenchmark)
microbenchmark(cns(x,y), ###where x is your first dataframe, y the second
               cns2(x,y)
               )

Результаты:

  Unit: milliseconds
       expr      min       lq     mean   median       uq      max neval
  cns(x, y) 42.46518 45.16829 46.61517 46.45560 47.09023 80.25171   100
 cns2(x, y) 26.09484 27.33122 28.21505 28.07837 29.10225 30.74004   100

Вы уже сократили свое время вдвое, без параллельных вычислений. Можем ли мы увеличить его еще больше?

cns3 <- function(x,y){
  b <- numeric(length = nrow(y))

  a<- distm(x=x,
              y=y,
              fun = distVincentyEllipsoid)

  b<-apply(X = a,MARGIN =  1, which.min) 
  return(y[b,])
}

Тест возвращается:

    Unit: milliseconds
       expr      min       lq     mean   median       uq       max neval
  cns(x, y) 43.38928 45.69135 48.72223 46.70839 48.56951 135.80555   100
 cns2(x, y) 25.96674 27.15066 28.86999 28.43569 29.99138  35.86383   100
 cns3(x, y) 23.90187 24.84592 26.68738 25.87950 27.99075  34.71469   100

Таким образом, cns3 кажется немного быстрее, но cns2 можно легко распараллелить, заменив на foreach.

Это правильно? Три метода дают одинаковый результат.

> cns(x,y)
         longitude latitude
426613   -3.309335 51.16636
426613.1 -3.309335 51.16636
426613.2 -3.309335 51.16636
426613.3 -3.309335 51.16636
426613.4 -3.309335 51.16636
426613.5 -3.309335 51.16636
426613.6 -3.309335 51.16636
426613.7 -3.309335 51.16636
426613.8 -3.309335 51.16636
426613.9 -3.309335 51.16636
> cns2(x,y)
         longitude latitude
426613   -3.309335 51.16636
426613.1 -3.309335 51.16636
426613.2 -3.309335 51.16636
426613.3 -3.309335 51.16636
426613.4 -3.309335 51.16636
426613.5 -3.309335 51.16636
426613.6 -3.309335 51.16636
426613.7 -3.309335 51.16636
426613.8 -3.309335 51.16636
426613.9 -3.309335 51.16636
> cns3(x,y)
         longitude latitude
426613   -3.309335 51.16636
426613.1 -3.309335 51.16636
426613.2 -3.309335 51.16636
426613.3 -3.309335 51.16636
426613.4 -3.309335 51.16636
426613.5 -3.309335 51.16636
426613.6 -3.309335 51.16636
426613.7 -3.309335 51.16636
426613.8 -3.309335 51.16636
426613.9 -3.309335 51.16636

2. Как часто, когда вас спрашивают о минимальных значениях, что вы хотите делать, когда есть связи?

С тем, как вы это написали, вы сохраняете все связи, что может быть проблемой, потому что b может быть принудительно приведен к списку.

Источник
Другие вопросы по тегам