给定一个数值向量,我想找到大小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)
不需要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
的答案。runif
或sample
((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