Warm tip: This article is reproduced from serverfault.com, please click

r-向量对之间的最小绝对差(贪婪算法)

(r - Minimum absolute difference between vector pairs (greedy algorithm))

发布于 2020-11-21 20:14:50

给定一个数值向量,我想找到大小2的组合中最小的绝对差。但是,摩擦点随使用combn来创建包含这些对的矩阵有关。当矩阵/向量太大时,如何处理问题?

当使用的结果对数(列数)combn太大时,出现以下错误:

矩阵中的错误(r,nrow = len.r,ncol = count):无效的'ncol'值(太大或不适用)

这篇文章指出,矩阵的大小限制大约为十亿行两列。

这是我使用的代码。cat在函数输出中使用的歉意-我正在解决HackerRank中的数组贪婪算法问题中最小绝对差值,并且如果使用cat以下命令给出R输出,则仅将它们视为正确

minimumAbsoluteDifference <- function(arr) {
  combos <- combn(arr, 2)
  
  cat(min(abs(combos[1,] - combos[2,])))
}

# This works fine
input0 <- c(3, -7, 0)

minimumAbsoluteDifference(input0) #returns 3

# This fails
inputFail <- rpois(10e4, 1)

minimumAbsoluteDifference(inputFail) 
  #Error in matrix(r, nrow = len.r, ncol = count) : 
  # invalid 'ncol' value (too large or NA)
Questioner
Chris Aguilar
Viewed
0
Joseph Wood 2020-12-01 06:41:30

TL; DR

不需要combn之类的,简单地:

min(abs(diff(sort(v))))

坚韧不拔

找到每种可能的组合之间的差异是O(n^2)因此,当我们到达length的向量时1e5,无论是在计算上还是在内存方面,任务都是繁重的。

我们需要一种不同的方法。

如何与邻居进行分类和区别处理?

通过首先排序,对于任何元素v j,差min | v j -v j-/ + 1 | 涉及v j的此类差异将是最小的例如,给定排序后的向量v

v = -9 -8 -6 -4 -2  3  8

的最小距离由-2下式给出:

|-2 - 3| = 5
|-4 - -2| = 2

无需检查任何其他元素。

可以很容易地R以如下方式实现:

getAbsMin <- function(v) min(abs(diff(sort(v))))

我不会将其rpois与任何大小合适的向量一起使用,将产生重复的结果,并给出简单0的答案。runifsample((minimumAbsoluteDifference2来自@RuiBarradas提供的答案)是一个更明智的测试

set.seed(1729)
randUnif100 <- lapply(1:100, function(x) {
    runif(1e3, -100, 100)
})

randInts100 <- lapply(1:100, function(x) {
    sample(-(1e9):(1e9), 1e3)
})

head(sapply(randInts100, getAbsMin))
[1]  586 3860 2243 2511 5186 3047

identical(sapply(randInts100, minimumAbsoluteDifference2),
          sapply(randInts100, getAbsMin))
[1] TRUE

options(scipen = 99)
head(sapply(randUnif100, getAbsMin))
[1] 0.00018277206 0.00020549633 0.00009834766 0.00008395873 0.00005299225 0.00009313226

identical(sapply(randUnif100, minimumAbsoluteDifference2),
          sapply(randUnif100, getAbsMin))
[1] TRUE

这也非常快:

library(microbenchmark)
microbenchmark(a = getAbsMin(randInts100[[50]]),
               b = minimumAbsoluteDifference2(randInts100[[50]]),
               times = 25, unit = "relative")
Unit: relative
expr      min       lq     mean   median       uq      max neval
   a   1.0000   1.0000   1.0000   1.0000  1.00000  1.00000    25
   b 117.9799 113.2221 105.5144 107.6901 98.55391 81.05468    25

即使对于非常大的向量,结果也是瞬间的。

set.seed(321)
largeTest <- sample(-(1e12):(1e12), 1e6)

system.time(print(getAbsMin(largeTest)))
[1] 3
 user  system elapsed 
0.083   0.003   0.087