У меня переменная, зависящая от времени, представлена в виде двух векторов: вектора времен (отсортированный) и вектора значений в те времена. Я хочу пересчитать эту переменную в разное время, указанное другим отсортированным вектором раз.
На другом языке я бы одновременно проходил два отсортированных вектора времени. т. е. линейный поиск от начала старого вектора времени до тех пор, пока я не найду время, наиболее близкое к первому элементу в новом векторе времени, затем продолжим с этой точки в старом векторе, чтобы найти время, наиболее близкое ко второму элементу в новом векторе и т. д. Это дает решение, которое O (n).
Ключевым моментом здесь является то, что два вектора времени не имеют одинаковую длину, и элементы не связаны друг с другом, поэтому что-то вроде map2 или walk2 не то, что я хочу.
Я могу реализовать одновременную прогулку с циклом for (см. Код ниже), и это работает, но медленно. У меня также есть другое решение, которое более R-кодовое, но это O (n ^ 2), поэтому оно также оказывается медленным. Есть ли способ сделать это R, который использует внутренние реализации R для решения с O (n)?
В качестве альтернативы, есть ли функция R, которая может заменить мой get_closest () бинарным поиском, так что по крайней мере это будет O (nlogn)?
Из моих поисков я подозреваю, что ответ будет "написать функцию C, которую вы вызываете из R", но я довольно плохо знаком с R, поэтому я хотел проверить, что я ничего не пропускаю.
EDIT:
Я должен был прояснить, что значения в new_times могут не существовать в old_times. Я хочу найти индекс в old_times, где время ближе к каждой записи в new_times. В моем реальном приложении я буду выполнять линейную интерполяцию, но этот вопрос касается поиска ближайшего соседа.
library(tidyverse)
# input values given
old_times <- c(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)
old_values <- c(3, 7, 6, 7, 8, 9, 7, 6, 4, 6)
new_times <- c(4.1, 9.6, 12.3, 17.8)
Желаемый вывод
new_values <- c(7, 8, 9, 4)
Моя попытка
new_values <- rep(NA, length(new_times))
old_index <- 1
for (new_index in 1:length(new_times)) {
while (old_index < length(old_times) &&
old_times[old_index] < new_times[new_index]) {
old_index <- old_index + 1
}
# I could now do interpolation if the value of new_times is in between
# two values in old_times. The key is I have a correspondence that
# new_times[new_index] is close in time to old_times[old_index].
new_values[new_index] <- old_values[old_index]
}
# Here's an alternative way to do it that uses more R internals,
# but winds up being O(n^2).
# Get the index in old_times closest to new_time.
# This is O(n).
get_closest <- function(new_time, old_times) {
return(which.min(abs(new_time - old_times)))
}
# Call get_closest on each element of new_times.
# This is O(n^2).
new_indices <- unlist(map(new_times, get_closest, old_times))
# Slice the list of old values to get new values.
new_values2 <- old_values[new_indices]