在一个向量中找到比另一个向量中的元素小的元素数量

Question

假设我们有一些向量。

a <- c(1, 2, 2, 4, 7)
b <- c(1, 2, 3, 5, 7)

对于 b 中的每个元素 b[i]，我想找到 a 中小于 b[i] 的元素数量，或者等价地说，我想知道 c(b[i], a) 中的 b_i 的排名。

有一些朴素的方法，例如执行以下任意一个操作 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

- kevinykuo

---

提供一个小巧、易于复制的玩具数据集和你尝试过的代码，这将获得额外的加分。为了让那些希望帮助你的人更容易地检查他们的代码是否产生了正确的结果，请同时发布你期望的输出。干杯！ - Henrik

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

- Blue Magister

---

以前不知道这个函数，所以谢谢！但愿它能在?match的“另请参阅”部分中。 - Gavin Kelly

@GavinKelly 它在 另请参阅 部分中，与 pmatch、charmatch 和 match.arg 一起。 - Blue Magister

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值的a和所有b，因此我们在最后一行删除b的累计计数。我怀疑这对于大型数据集来说可能更快-如果match内部针对排序列表进行了优化，希望如此。然后将nbelow映射回您原始的b集合应该是一个微不足道的问题。

- Gavin Kelly

---

+1：这个解决方案依赖于快速排序 - 也就是说，总体复杂度为n*log(n)，而不是n²。 - Jealie

Answer 3

我不声称这是“最佳方式”，但这是一种方法。 sapply 将（匿名）函数 应用于 b 的每个元素。

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

- Henrik