Более быстрый способ поиска ближайших дат вектора к элементу другого вектора - PullRequest
Новая
       23

Более быстрый способ поиска ближайших дат вектора к элементу другого вектора

0 голосов
/ 26 июня 2018

У меня есть несколько векторов времени с разными размерами и один вектор времени со второй выборкой.

Я пытался найти ближайшую точку к элементу $ i ^ {th} $, но этот метод безумно медленный. 

    for (i in 1:length(SamplingTime)){
which.min(abs(SamplingTime[i]-rTime1))
}

Кроме того, я хотел бы знать, знает ли кто-нибудь, как найти две самые близкие точки данных к элементу i SamplingTime. Мой оригинальный подход состоял в том, чтобы преобразовать формат posix в числовой и использовать пакет RANN с: 

closest <- nn2(data=mytimes, k=2)[[1]]

Но опять-таки это замедление.

Edit: 

    SampleTime                        rTime

2018-06-01 00:51:40   UTC    2018-06-01 00:51:37 UTC 
2018-06-01 00:51:41,2 UTC    2018-06-01 00:51:38 UTC 
2018-06-01 00:51:41,4 UTC    2018-06-01 00:51:39 UTC
2018-06-01 00:51:41,5 UTC    2018-06-01 00:51:40 UTC 
2018-06-01 00:51:41,9 UTC    2018-06-01 00:51:41 UTC 
2018-06-01 00:51:43   UTC    2018-06-01 00:51:42 UTC
2018-06-01 00:51:46   UTC    2018-06-01 00:51:43 UTC
2018-06-01 00:51:48   UTC            .
          .                          .
          .

Идея состоит в том, что каждый раз мне приходится оценивать, какие два значения rTime ближе к SampleTime [i]. Например, для SampleTime [3] = 2018-06-01 00:51:48 UTC, ближе rTime будет rTime [4] = 2018-06-01 00:51:40 UTC и rTime [5] = 2018-06- 01 00:51:41 UTC

1 Ответ

0 голосов
/ 02 июля 2018

Опубликованный вопрос содержит два вопроса. Первый запрашивает более быстрый метод поиска ближайшего значения в rTime для каждого значения, указанного в SampleTime.

Цикл for OP "печатает" индексы ближайшего значения в rTime. (Ну, на самом деле фрагмент кода OP возвращает ничто без оператора print() или сохранения значений.)

Приведенный ниже код возвращает индексы, используя скользящее соединение с ближайшим , которое доступно в пакете data.table. 

# reproduce OP's data
SampleTime <- 
  structure(c(1527814300, 1527814301.2, 1527814301.4, 1527814301.5, 
              1527814301.9, 1527814303, 1527814306, 1527814308), 
            class = c("POSIXct", "POSIXt"), tzone = "UTC")
rTime <- 
  structure(c(1527814297, 1527814298, 1527814299, 1527814300, 1527814301, 
              1527814302, 1527814303), 
            class = c("POSIXct", "POSIXt"), tzone = "UTC")

library(data.table)
sDT <- data.table(SampleTime)
rDT <- data.table(rTime)
# rolling join to nearest
rDT[sDT, on = .(rTime = SampleTime), roll = "nearest", which = TRUE]

[1] 4 5 5 5 6 7 7 7

Если вместо индексов требуются значения: 

sDT[, rTime := rDT[sDT, on = .(rTime = SampleTime), roll = "nearest", x.rTime]][]

            SampleTime               rTime
1: 2018-06-01 00:51:40 2018-06-01 00:51:40
2: 2018-06-01 00:51:41 2018-06-01 00:51:41
3: 2018-06-01 00:51:41 2018-06-01 00:51:41
4: 2018-06-01 00:51:41 2018-06-01 00:51:41
5: 2018-06-01 00:51:41 2018-06-01 00:51:42
6: 2018-06-01 00:51:43 2018-06-01 00:51:43
7: 2018-06-01 00:51:46 2018-06-01 00:51:43
8: 2018-06-01 00:51:48 2018-06-01 00:51:43

Обратите внимание, что дробные секунды и информация о часовом поясе по умолчанию опускаются при печати объектов POSIXct. Чтобы показать оба, необходимо указать формат: 

sDT[, rTime := rDT[sDT, on = .(rTime = SampleTime), roll = "nearest", x.rTime]][
  , lapply(.SD, format, format = "%F %H:%M:%OS1 %Z")]

                  SampleTime                     rTime
1: 2018-06-01 00:51:40.0 UTC 2018-06-01 00:51:40.0 UTC
2: 2018-06-01 00:51:41.2 UTC 2018-06-01 00:51:41.0 UTC
3: 2018-06-01 00:51:41.4 UTC 2018-06-01 00:51:41.0 UTC
4: 2018-06-01 00:51:41.5 UTC 2018-06-01 00:51:41.0 UTC
5: 2018-06-01 00:51:41.9 UTC 2018-06-01 00:51:42.0 UTC
6: 2018-06-01 00:51:43.0 UTC 2018-06-01 00:51:43.0 UTC
7: 2018-06-01 00:51:46.0 UTC 2018-06-01 00:51:43.0 UTC
8: 2018-06-01 00:51:48.0 UTC 2018-06-01 00:51:43.0 UTC

Benchmark

В тесте сравниваются три различных метода

  • цикл for, используемый ОП, но измененный для возврата вектора индексов
  • более краткое переписывание с использованием sapply() и
  • a подвижное соединение с ближайшим

Все три возвращают вектор индексов.

Контрольные данные состоят из 1000 выборок, что является довольно небольшим контрольным примером. 

library(data.table)
library(magrittr)
# create benchmark data
n <- 1000L
set.seed(1L)
SampleTime <- lubridate::as_datetime("2018-06-01") + cumsum(rnorm(n, 1)) %>% 
  sort()

rTime <- seq(lubridate::floor_date(min(SampleTime), "min"),
             lubridate::ceiling_date(max(SampleTime), "min"),
             by = "sec")

# perform benchmark
microbenchmark::microbenchmark(
  loop = {
    idx <- integer(length(SampleTime))
    for (i in 1:length(SampleTime)){
      idx[i] <- (which.min(abs(SampleTime[i] - rTime)))
    }
    idx
  },
  sapply = {
    sapply(
      seq_along(SampleTime), 
      function(i) which.min(abs(SampleTime[i] - rTime))
    )
  },
  roll_join = {
    sDT <- data.table(SampleTime)
    rDT <- data.table(rTime)
    rDT[sDT, on = .(rTime = SampleTime), roll = "nearest", which = TRUE]
  },
  times = 100L
)

Скользящее соединение - самый быстрый метод в 50 раз, даже для этого сравнительно небольшого тестового случая: 

Unit: milliseconds
      expr       min        lq      mean    median        uq        max neval cld
      loop 51.467338 53.365061 57.174145 54.722276 57.270950 214.442708   100   c
    sapply 49.833166 51.244187 53.600532 52.424695 55.126666  64.886196   100  b 
 roll_join  1.093099  1.355139  1.462512  1.408001  1.496544   5.411494   100 a
...