有效识别长向量中的高/低命中

Question

我有一个向量

x

，并且想知道该向量 (

i

) 中的每个元素

x[i]

后续数字序列是否首先命中

x[i] + con

或

x[i] - con

（其中

con

是持续的）。每当首先击中

x[i] + con

时，我希望得到 1，否则得到 0。

我会使用 R 来完成此操作，如下面的最小工作示例所示：

x   <- cumsum(rnorm(1000000))
con <- 10

hit <- NULL
for (i in 999000:length(x)) {
  hithi  <- min(which(x[i:length(x)] >= x[i] + con))
  hithi  <- ifelse(is.infinite(hithi), 1000000, hithi)
  hitlo  <- min(which(x[i:length(x)] <= x[i] - con))
  hitlo  <- ifelse(is.infinite(hitlo), 1000000, hitlo)
  hit[i] <- ifelse(hithi < hitlo, 1, 0)
  if (i %% 1000 == 0) {
    print(i)
  }
}

但是，您会发现这非常慢，因此我想知道是否有更快的方法来获得结果。你会怎么做？

提前非常感谢！

Answer 1

我不懂 R，所以我用 PHP 编写了这个脚本。希望 R 程序员能够将其作为伪代码来阅读。它遍历数组并在输入数组中构建数组值及其索引的查找表。它最初将“hilo”值分配为零，这意味着 hilo 状态尚未确定。如果数组值 + 常量值首先出现在后续数组中，则 hil0 值将设置为 +1（如果尚未确定）。同样，如果数组值 - 常量值首先出现在后续元素中，则它会设置为 -1。从您的描述中我不确定这是否正是您想要的，但总体思路应该适用于您的输出要求。这有点类似于编码练习中经常出现的著名的“2 Sum”问题。

当它遍历输入数组时，它会设置存储在查找表中的先前元素的 hilo 值，在本例中是一个 PHP 数组。如果输入数组中有很多重复条目，则由于每次都对索引进行线性搜索，效率会变得很低。因此，如果您有 0 到 999 之间的一百万个输入数组值，那么平均而言，数组值将有 1000 个重复项，并且对于每个重复项，每次都必须搜索最多 1000 个值。因此，时间复杂度类似于 O(sum(k_i^2))，其中 k_i 是输入数组中第 i 个不同值的出现次数。可能有更好的方法，但它对于简单的程序来说效果很好，除非你对重复值的数量感到愚蠢。

<?php
// https://stackoverflow.com/questions/78161294/efficient-identification-of-high-low-hits-in-a-long-vector

function printhilos($input, $values) {
  $valuesperline = 10;
  $valuesthisline = 0;
  foreach($input as $key => $value) {
    $indexes = $values[$value];
    echo "(".$value.",".$values[$value][$key].") ";
    $valuesthisline++;
    if ($valuesthisline >= $valuesperline) {
      echo "\n";
      $valuesthisline = 0;
    }
  }
  echo "\n";
}

function randominput($size) {
  $input = array();
  for ($i=0; $i<$size; $i++) $input[$i] = (rand() % 198) - 99;
  return $input;
}

  //$input = array(3, 27, 13, 37, 17, 3);
  $input = randominput($argv[1]);
  $const = 10;
  $values = array();
  $indexes = array();
  foreach($input as $key => $value) {
    $values[$value][$key] = 0;
    if (Array_Key_Exists($value + $const, $values)) {
      $indexes = $values[$value + $const];
      foreach($indexes as $index => $hilo) {
        if ($hilo === 0) $values[$value + $const][$index] = -1;
      }
    }
    if (Array_Key_Exists($value - $const, $values)) {
      $indexes = $values[$value - $const];
      foreach($indexes as $index => $hilo) {
        if ($hilo === 0) $values[$value - $const][$index] = 1;
      }
    }
  }
  printhilos($input, $values);

?>

php hiorlo1st.php 100 的输出示例

(-21,-1) (23,0) (-53,-1) (94,-1) (-84,-1) (-67,1) (12,0) (-93,1) (55,0) (84,1) 
(19,1) (29,0) (-63,1) (70,-1) (-20,-1) (-16,1) (-88,0) (53,0) (86,0) (-72,0) 
(-66,1) (86,0) (30,1) (-66,1) (-6,0) (21,1) (68,0) (-53,-1) (-72,0) (-73,1) 
(-57,0) (64,1) (-31,-1) (40,0) (94,0) (16,-1) (57,0) (-54,0) (-48,0) (-52,0) 
(-17,1) (-89,0) (-5,1) (-26,0) (-34,0) (6,0) (-7,1) (74,-1) (53,0) (27,1) 
(-52,0) (37,-1) (60,0) (-73,1) (64,1) (-32,0) (-53,-1) (-33,1) (74,0) (-48,0) 
(5,0) (46,0) (-3,1) (-56,0) (-63,0) (-23,0) (51,1) (-81,0) (-41,0) (-41,0) 
(-30,-1) (-59,1) (12,0) (-49,0) (-56,0) (-94,0) (-35,0) (71,-1) (-81,0) (1,-1) 
(29,0) (61,0) (7,0) (7,0) (57,0) (14,0) (-76,0) (3,0) (-40,0) (-63,0) 
(81,0) (95,0) (10,0) (-11,0) (-40,0) (-14,0) (27,0) (-83,0) (31,0) (-9,0)