Нахождение количества элементов в одном векторе, которые меньше, чем элемент в другом векторе
Скажем, у нас есть пара векторов
a <- c(1, 2, 2, 4, 7)
b <- c(1, 2, 3, 5, 7)
Для каждого элементаb[i]
вb
Я хочу найти количество элементов вa
это меньше чемb[i]
или, эквивалентно, я хочу знать ранг b_i вc(b[i], a)
.
я могу придумать пару наивных способов, например, делать одно из следующихlength(b)
раз:
min_rank(c(b[i], a))
sum(a < b[i])
Какой лучший способ сделать это, еслиlength(a)
= length(b)
= N где N большое?
РЕДАКТИРОВАТЬ:
Чтобы прояснить, мне интересно, есть ли более вычислительно эффективный способ сделать это, то есть, смогу ли я сделать лучше, чем квадратичное время в этом случае.
Хотя векторизация всегда крутая;), спасибо @Henrik!
Продолжительность
a <- rpois(100000, 20)
b <- rpois(100000, 10)
system.time(
result1 <- sapply(b, function(x) sum(a < x))
)
# user system elapsed
# 71.15 0.00 71.16
sw <- proc.time()
bu <- sort(unique(b))
ab <- sort(c(a, bu))
ind <- match(bu, ab)
nbelow <- ind - 1:length(bu)
result2 <- sapply(b, function(x) nbelow[match(x, bu)])
proc.time() - sw
# user system elapsed
# 0.46 0.00 0.48
sw <- proc.time()
a1 <- sort(a)
result3 <- findInterval(b - sqrt(.Machine$double.eps), a1)
proc.time() - sw
# user system elapsed
# 0.00 0.00 0.03
identical(result1, result2) && identical(result2, result3)
# [1] TRUE