向量对间最小绝对差（贪心算法）

Question

给定一个数字向量，我想找到大小为2的组合中最小的绝对差异。然而，摩擦点伴随着使用comn来创建保持成对的矩阵。当矩阵/向量太大时，如何处理问题？

当使用combn得到的对数（列数）太大时，我得到以下错误：

矩阵中的错误（r，nrow=len.r，ncol=count）：无效的“ncol”值（太大或NA）

这篇文章指出，矩阵的大小限制大约是10亿行和两列。

这是我使用的代码。抱歉在我的函数输出中使用了cat——我正在解决HackerRank中数组贪婪算法问题中的最小绝对差，如果使用cat给出R输出，则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)

Answer 1

像这样的？

minimumAbsoluteDifference2 <- function(x){
  stopifnot(length(x) >= 2)
  n <- length(x)
  inx <- rep(TRUE, n)
  m <- NULL
  for(i in seq_along(x)[-n]){
    inx[i] <- FALSE
    curr <- abs(x[i] - x[which(inx)])
    m <- min(c(m, curr))
  }
  m
}
# This works fine
input0 <- c(3, -7, 0)

minimumAbsoluteDifference(input0)  #returns 3
minimumAbsoluteDifference2(input0) #returns 3


set.seed(2020)
input1 <- rpois(1e3, 1)
minimumAbsoluteDifference(input1)  #returns 0
minimumAbsoluteDifference2(input1) #returns 0

inputFail <- rpois(1e5, 1)
minimumAbsoluteDifference(inputFail)   # This fails
minimumAbsoluteDifference2(inputFail)  # This does not fail

Answer 2

不需要comn或类似的东西，只需：

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

找出每个可能组合之间的差异是O（n^2）。因此，当我们得到长度为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

没有必要检查任何其他元素。

这在baseR中很容易实现，如下所示：

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

我不打算使用rpois，因为对于任何大小合理的向量，将产生重复，这将简单地给出0作为答案。一个更明智的测试是使用runif或的示例（最小化ABSOSOLE差分2来自@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