循环遍历 R 中有序集的功能方法

Functional way to loop over ordered set in R

我正在尝试优化 R 中的算法,该算法运行一组有序的值并确定是否有值 'in the future'(在集合的下方)具有比给定值更低的值。

例如:

+-------+--------------------------------+
| Value | RestOfSeriesContainsLowerValue |
+-------+--------------------------------+
| 5     | true                           |
| 4     | true                           |
| 2     | true                           |
| 1     | false                          |
| 3     | true                           |
| 4     | true                           |
| 4     | true                           |
| 3     | true                           |
| 3     | true                           |
| 2     | false                          |
| 2     | false                          |
| 2     | false                          |
| 7     | false                          |
| 8     | false                          |
| 9     | false                          |
| ...   | ...                            |
+-------+--------------------------------+

局部最小值是值 1 和 2。因此,此集合中第一项的 RestOfSeriesContainsLowerValue 的值为真 - 因为集合中的值 (1) 更靠下,具有较低的值。

在值 1 之后 - 值 3 和值 4 的值为真,因为新的局部最小值(值 2)稍后会在集合中出现。

我们目前正在使用伪代码中运行在 - 上的 for 循环:

for (i in set) {
   if(value(i) <=  min(set[,i:end])) 
     RestOfSeriesContainsLowerValue(i) = true
   else
    RestOfSeriesContainsLowerValue(i) = false
}

但是这样效率不够。我正在寻找一种基于集合/功能的方法来用 R 编写它,但我无法理解它。我可以使用 lapply 来执行此操作吗?

您使用 lapply

在函数式 R 代码中的伪代码
f <-function(value) unlist(lapply(seq_along(value), function(i)if(value[i] <=  min(value[i:length(value)]))FALSE else TRUE))

实现相同目标的矢量化代码是

f1 <- function(value)value > rev(cummin(rev(value)))

根据样本大小,矢量化代码可以任意快。对于 n=100 它大约快 10 倍,对于 1000 大约快 100 倍,对于 10000

大约快 1000 倍
value <- sample(1:100, 1000, replace = TRUE)
microbenchmark::microbenchmark(f(value), f1(value), unit="relative")
#Unit: relative
#     expr      min       lq     mean   median       uq      max neval
# f(value) 172.3758 174.2449 124.1607 107.5502 104.8017 96.85548   100
#f1(value)   1.0000   1.0000   1.0000   1.0000   1.0000  1.00000   100