在 list/vector 中按索引选择最近的 x 元素

Question

如果我有一个向量，例如 x <-c(1,2,3,4,5,6,7,8,9)，我想要一个函数 f 使得 f(vector,index,num) 它获取向量并给我 num "closest" 索引中那个元素的元素例子： f(x,3,4) = c(1,2,4,5) f(x,1,5) = c(2,3,4,5,6) f(x,8,3) = c(6,7,9)

因为还有一个问题，如果我们有奇数，我们需要根据对称性来选择是选择左侧还是右侧，我们就选择左侧吧（但右侧也可以）即 f(x,4,5) = c(1,2,3,5,6) and f(x,7,3) = c(5,6,8)

我希望我的问题很清楚，谢谢任何help/responses！

edit: c(1:9) 的原始向量是任意的，向量可以是字符串向量，也可以是长度为 1000 的带有随机数字和重复等的向量。

即c(1,7,4,2,3,7,2,6,234,56,8)

Answer 1

num_closest_by_indices <- function(v, idx, num) {
  # Try the base case, where idx is not within (num/2) of the edge
  i <- abs(seq_along(x) - idx)
  i[idx] <- +Inf # sentinel

  # If there are not enough elements in the base case, incrementally add more
  for (cutoff_idx in seq(floor(num/2), num)) {
    if (sum(i <= cutoff_idx) >= num) {
      # This will add two extra indices every iteration. Strictly if we have an even length, we should add the leftmost one first and `continue`, to break ties towards the left.
      return(v[i <= cutoff_idx])
    }
  }
}

下面是该算法的示例：我们按照合意程度对索引进行排序，然后选择最低的 num 合法索引：

> seq_along(x)
  1 2 3 4 5 6 7 8 9
> seq_along(x) - idx
  -2 -1  0  1  2  3  4  5  6
> i <- abs(seq_along(x) - idx)
   2  1  0  1  2  3  4  5  6
> i[idx] <- +Inf # sentinel to prevent us returning the element itself
   2   1 Inf   1   2   3   4   5   6

现在我们只能找到 num 个具有最小值的元素（任意打破平局，除非您有偏好（左））。我们的第一个猜测是所有索引 <= (num/2) ；如果 index 在 start/end 的 (num/2) 范围内，这可能还不够。

> i <= 2
  TRUE  TRUE FALSE  TRUE  TRUE FALSE FALSE FALSE FALSE
> v[i <= 2]
  1 2 4 5

因此，调整@dash2 的代码来处理某些索引非法（非正数，或 > length(x)）的极端情况，即 ! %in% 1:L。那么 min(elems) 就是我们不能选择的非法索引的数量，因此我们必须选择 abs(min(elems)) 。

备注：

最终代码更简单，更快地通过三个分段的情况来处理它。哇哦
如果我们选择 (num+1) 个索引，然后在返回答案之前删除 idx，这实际上似乎简化了事情。使用 result[-idx] 删除它。

Answer 2

像这样：

f <- function (vec, elem, n) {
  elems <- seq(elem - ceiling(n/2), elem + floor(n/2))
  if (max(elems) > length(vec)) elems <- elems - (max(elems) - length(vec))
  if (elems[1] < 1) elems <- elems + (1 - elems[1])
  elems <- setdiff(elems, elem)
  vec[elems]
}

给出结果：

> f(1:9, 1, 5)
[1] 2 3 4 5 6
> f(1:9, 9, 5)
[1] 4 5 6 7 8
> f(1:9, 2, 5)
[1] 1 3 4 5 6
> f(1:9, 4, 5)
[1] 1 2 3 5 6
> f(1:9, 4, 4)
[1] 2 3 5 6
> f(1:9, 2, 4)
[1] 1 3 4 5
> f(1:9, 1, 4)
[1] 2 3 4 5
> f(1:9, 9, 4)
[1] 5 6 7 8

Answer 3

首先使用变量参数 x 启动一个函数，然后

之后引用 table 和 n

.nearest_n <- function(x, table, n) {

该算法假定 table 是数字，没有任何重复项，并且所有值都是有限的； n 必须小于或等于 table

的长度

    ## assert & setup
    stopifnot(
        is.numeric(table), !anyDuplicated(table), all(is.finite(table)),
        n <= length(table)
    )

对 table 排序，然后 'clamp' 最大值和最小值

    ## sort and clamp
    table <- c(-Inf, sort(table), Inf)
    len <- length(table)

找到table中出现x的区间； findInterval() 使用高效搜索。使用区间索引作为初始下索引，上索引加1，确保在范围内。

    ## where to start?
    lower <- findInterval(x, table)
    upper <- min(lower + 1L, len)

通过将下索引和上索引距离与 x 进行比较，找到最近的 n 邻居，记录最接近的值，并适当增加下索引或上索引，并确保保持在-界限

    ## find
    nearest <- numeric(n)
    for (i in seq_len(n)) {
        if (abs(x - table[lower]) < abs(x - table[upper])) {
            nearest[i] = table[lower]
            lower = max(1L, lower - 1L)
        } else {
            nearest[i] = table[upper]
            upper = min(len, upper + 1L)
        }
    }

然后return解决方案并完成功能

    nearest
}

代码可能看起来冗长，但实际上相对高效，因为在整个向量（sort()、findInterval()）上唯一的操作在 R 中有效实现。

这种方法的一个特别优点是它可以在它的第一个参数中被向量化，计算使用 lower (use_lower = ...) 作为向量的测试并使用 pmin() / pmax() 作为夹子。

.nearest_n <- function(x, table, n) {
    ## assert & setup
    stopifnot(
        is.numeric(table), !anyDuplicated(table), all(is.finite(table)),
        n <= length(table)
    )

    ## sort and clamp
    table <- c(-Inf, sort(table), Inf)
    len <- length(table)

    ## where to start?
    lower <- findInterval(x, table)
    upper <- pmin(lower + 1L, len)

    ## find
    nearest <- matrix(0, nrow = length(x), ncol = n)
    for (i in seq_len(n)) {
        use_lower <- abs(x - table[lower]) < abs(x - table[upper])
        nearest[,i] <- ifelse(use_lower, table[lower], table[upper])
        lower[use_lower] <- pmax(1L, lower[use_lower] - 1L)
        upper[!use_lower] <- pmin(len, upper[!use_lower] + 1L)
    }

    # return
    nearest
}

例如

> set.seed(123)
> table <- sample(100, 10)
> sort(table)
 [1]  5 29 41 42 50 51 79 83 86 91
> .nearest_n(c(30, 20), table, 4)
     [,1] [,2] [,3] [,4]
[1,]   29   41   42   50
[2,]   29    5   41   42

通过获取任何参数并使用参考查找 table table0 和其中的索引将其强制转换为所需的形式来概括这一点 table1

nearest_n <- function(x, table, n) {
    ## coerce to common form
    table0 <- sort(unique(c(x, table)))
    x <- match(x, table0)
    table1 <- match(table, table0)

    ## find nearest
    m <- .nearest_n(x, table1, n)

    ## result in original form
    matrix(table0[m], nrow = nrow(m))
}

举个例子...

> set.seed(123)
> table <- sample(c(letters, LETTERS), 30)
> nearest_n(c("M", "Z"), table, 5)
     [,1] [,2] [,3] [,4] [,5]
[1,] "o"  "L"  "O"  "l"  "P" 
[2,] "Z"  "z"  "Y"  "y"  "w"

在 list/vector 中按索引选择最近的 x 元素

Choose closest x elements by index in a list/vector

r

vector

closest

indices