给定一个数字向量,我想找到大小为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)
像这样的?
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
不需要comn
或类似的东西,只需:
min(abs(diff(sort(v))))
找出每个可能组合之间的差异是O(n^2)
。因此,当我们得到长度为1e5
的向量时,这项任务在计算和内存方面都很繁重。
我们需要不同的方法。
如何排序和采取的差异只与它的邻居?
通过第一次排序,对于任何元素vj,差异min|vj-vj-/1|将是涉及vj的最小此类差异。例如,给定排序向量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
主要内容:贪心算法的实际应用《 算法是什么》一节讲到,算法规定了解决问题的具体步骤,即先做什么、再做什么、最后做什么。贪心算法是所有算法中最简单,最易实现的算法,该算法之所以“贪心”,是因为算法中的每一步都追求最优的解决方案。 举个例子,假设有 1、2、5、10 这 4 种面值的纸币,要求在不限制各种纸币使用数量的情况下,用尽可能少的纸币拼凑出的总面值为 18。贪心算法的解决方案如下: 率先选择一张面值为 10 的纸币,可以
输入是实数x1、x2、…、x2n的序列。我们想把这些数字配对成n对。对于第i对(i=1,2,…,n),让Si表示该对中的数字之和。(例如,如果将x(2i−1) 并且x2i作为第i对,Si=x(2i−1) x2i)。我们希望将这些数字配对,以使Maxi[Si]最小化。设计一个贪婪算法来解决这个问题。 这就是问题所在;我的解决方案是简单地对数字进行排序,并将前一个元素与后一个元素配对,加一个/减一个索
本文向大家介绍Python贪心算法实例小结,包括了Python贪心算法实例小结的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python贪心算法。分享给大家供大家参考,具体如下: 1. 找零钱问题:假设只有 1 分、 2 分、五分、 1 角、二角、 五角、 1元的硬币。在超市结账 时,如果 需要找零钱, 收银员希望将最少的硬币数找给顾客。那么,给定 需要找的零钱数目,如何求得最少的硬币数
本文向大家介绍google-chrome-extension 绝对最小manifest.json,包括了google-chrome-extension 绝对最小manifest.json的使用技巧和注意事项,需要的朋友参考一下 示例 manifest.json提供有关扩展的信息,例如最重要的文件和扩展可能使用的功能。在扩展支持的清单字段中,以下三个是必需的。
我正在学习贪婪算法,遇到了一个我不知道如何解决的问题。给定一组开始时间为a,结束时间为b的区间(a,b),给出一个贪婪算法,该算法返回该集合中每隔一个区间重叠的最小区间数。例如,如果我有: (1,4) (2,3) (5,8) (6,9) (7,10) 我将返回(2,3)和(7,8),因为这两个区间覆盖了集合中的每个区间。我现在得到的是: 通过增加结束时间对间隔进行排序 将结束时间最小的间隔推到堆栈
本文向大家介绍使用NumPy的绝对偏差和绝对均值偏差,包括了使用NumPy的绝对偏差和绝对均值偏差的使用技巧和注意事项,需要的朋友参考一下 在统计分析中对样本中数据变异性的研究表明,给定数据样本中的值有多分散。计算变异性的两个重要方法是绝对偏差和 均值绝对偏差。 绝对偏差 在这种方法中,我们首先找到给定样本的平均值,然后计算每个值与样本平均值之间的差,称为每个数据样本的绝对偏差值。因此,对于高于平