Нахождение количества элементов в одном векторе, которые меньше, чем элемент в другом векторе

Question

Скажем, у нас есть пара векторов

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

Answer 1

При условии, что a слабо сортируется всё чаще, используй findInterval:

a <- sort(a)
## gives points less than or equal to b[i]
findInterval(b, a)
# [1] 1 3 3 4 5
## to do strictly less than, subtract a small bit from b
## uses .Machine$double.eps (the smallest distinguishable difference)
findInterval(b - sqrt(.Machine$double.eps), a)
# [1] 0 1 3 4 4

Answer 2

Если вы действительно оптимизируете этот процесс для больших N, то вы можете удалить повторяющиеся значения в b по крайней мере, сначала, а затем вы можете отсортировать и сопоставить:

bu <- sort(unique(b))
ab <- sort(c(a, bu))
ind <- match(bu, ab)
nbelow <- ind - 1:length(bu)

Когда мы объединили значения a и b в ab, match включает в себя все меньше, чем конкретное значение b вместе со всеми b, поэтому мы убираем кумулятивное число b в последней строке. Я подозреваю, что это может быть быстрее для больших наборов - это должно быть, если match внутренне оптимизирован для сортированных списков, что можно было бы ожидать. Это должно быть тривиальным вопросом, чтобы отобразить обратно nbelow к вашему первоначальному набору bs

Answer 3

Я не утверждаю, что это "лучший способ", но это способ. sapply применяет (анонимно) function к каждому элементу b,

 sapply(b, function(x) sum(a < x))
 # [1] 0 1 3 4 4