时间戳

首页 > 解决方案 > 在 R 中创建有序结构并从中检索值的最快方法

r - 在 R 中创建有序结构并从中检索值的最快方法

问题描述

我正在尝试在 R 中创建一个有序的“结构”，以便第一个（或最后一个）元素始终是最小的。目前，我正在通过以下方式进行处理：

我有一个升序数值的排序向量，并在其中输入新值，以便保持排序。然后当我想要下一个元素（意思是最小的一个）时，我只取第一个元素并将其从向量中删除。 

# Input the new element
point <- Position(function(v) v < ins, ordVec, right = TRUE)
if (is.na(point)) {point <- 0}
ordVec <- append(ordVec, ins, after = point)
# Get the smallest element
value <- ordVec[1]
ordVec <- ordVec[-1]

哪里ordVec是有序向量，ins是我要输入的值。
例如，我有ordVec <- c(1, 2, 3, 4, 5)and ins <- 2.5，输入后ins我得到c(1, 2, 2.5, 3, 4, 5). 然后，value是1和得到的向量是c(2, 2.5, 3, 4, 5)。

我这样做是作为while循环的一部分，当ordVec它很长时，它需要很长时间。

是否存在更快的方法，无论是使用所描述的过程以外的东西来获得有序的“结构”，还是修改所描述的过程和元素检索？

标签： roptimization

解决方案

我认为问题出在 Position 函数上。由于您的矢量已经排序，因此您不需要它。如果您查看代码，它实际上会循环遍历向量，这意味着如果向量很长，它将随波逐流：

Position
function (f, x, right = FALSE, nomatch = NA_integer_) 
{
    ind <- if (right) 
        rev(seq_along(x))
    else seq_along(x)
    for (i in ind) if (f(x[[i]])) 
        return(i)
    nomatch
}

所以让我们尝试一些解决方案：

f_position = function(ordVec,ins){
point <- Position(function(v) v < ins, ordVec, right = TRUE)
ordVec <- append(ordVec, ins, after = point)
return(c(ordVec[1],ordVec[-1]))
}

f_which = function(ordVec,ins){
point <- max(which(ordVec < ins))
ordVec <- append(ordVec, ins, after = point)
return(c(ordVec[1],ordVec[-1]))
}

f_interval = function(ordVec,ins){
point <- findInterval(ins,ordVec)
ordVec <- append(ordVec, ins, after = point)
return(c(ordVec[1],ordVec[-1]))
}

看看他们的时间，我使用了一个预排序的向量和 1 个插入值：

set.seed(111)
VEC = sort(runif(10000))
INS = 0.5
microbenchmark(f_position(VEC,INS),times=1000,unit="ms")
Unit: milliseconds
                 expr      min       lq     mean   median       uq     max
 f_position(VEC, INS) 2.525094 2.667763 3.040159 2.769987 2.923979 29.5144
 neval
  1000

microbenchmark(f_which(VEC,INS),times=1000,unit="ms")
Unit: milliseconds
              expr      min       lq      mean   median       uq      max neval
 f_which(VEC, INS) 0.148981 0.182694 0.3350992 0.197149 0.396787 28.04375  1000

microbenchmark(f_interval(VEC,INS),times=1000,unit="ms")
Unit: milliseconds
                 expr      min      lq      mean  median       uq      max
 f_interval(VEC, INS) 0.121805 0.15208 0.2851541 0.16236 0.201172 30.68901
 neval
  1000

我认为你最好使用 max(which()) 或 findInterval()，你只需要弄清楚如何初始化但不应该是一个问题。

推荐阅读