寻找向量元素第一个变化的索引。

Question

我有一个向量v，我想在R中找到向量元素第一次改变的索引。我该怎么做？例如：

v = c(1, 1, 1, 1, 1, 1, 1, 1.5, 1.5, 2, 2, 2, 2, 2)

- rose

Answer 1

rle 是一个不错的想法，但如果你只需要变化点的索引，只需执行以下操作：

```R diff(x) != 0 ```

c(1,1+which(diff(v)!=0))
## 1 8 10

- Ben Bolker

---

如果我有一个字符向量，即“买”和“卖”交替出现，该怎么办？ - Abdul Basit Khan

这个问题的基于 rle 的答案应该适用于字符向量。 - Ben Bolker

Answer 2

您正在寻找 rle：

rle(v)
## Run Length Encoding
##   lengths: int [1:3] 7 2 5
##   values : num [1:3] 1 1.5 2

这意味着值会在第7个位置+1、第7个位置+2+1（而第7个位置+2+5+1将是元素“离开结尾”）处发生变化。

- Matthew Lundberg

---

如果我有一个字符向量，即“买”和“卖”交替出现，该怎么办？解决方案是什么？ - Abdul Basit Khan

换句话说，head(cumsum(c(1, rle(v)$lengths)), -1) 就可以实现这个功能。 - Ben Bolker

换句话说，head(cumsum(c(1, rle(v)$lengths)), -1) 就可以了。 - undefined

Answer 3

data.table包内部（意味着尚未导出）使用一个名为uniqlist的函数（在dev 1.8.11中），或者替代地使用duplist（在当前的1.8.10 @CRAN中），它正好可以满足您的要求。它应该非常快速。这是一个基准测试：

require(data.table)
set.seed(45)
# prepare a huge vector (sorted)
x <- sort(as.numeric(sample(1e5, 1e7, TRUE)))

require(microbenchmark)
ben <- function(v) c(1,1+which(diff(v)!=0))
matthew <- function(v) rle(v)
matteo <- function(v) firstDiff(v)
exegetic <- function(v) first.changes(v)
# if you use 1.8.10, replace uniqlist with duplist
dt <- function(v) data.table:::uniqlist(list(v))

microbenchmark( ans1 <- ben(x), matthew(x), matteo(x), 
                exegetic(x), ans2 <- dt(x), times=10)

# Unit: milliseconds
#            expr       min         lq     median         uq        max neval
#  ans1 <- ben(x)  1181.808  1229.8197  1313.2646  1357.5026  1553.9296    10
#      matthew(x)  1456.918  1496.0300  1581.0062  1660.4067  2148.1691    10
#       matteo(x) 28609.890 29305.1117 30698.5843 32706.3147 34290.9864    10
#     exegetic(x)  1365.243  1546.0652  1576.8699  1659.5488  1886.6058    10
#   ans2 <- dt(x)   113.712   114.7794   143.9938   180.3743   221.8386    10

identical(as.integer(ans1), ans2) # [1] TRUE

我对Rcpp不是很熟悉，但似乎解决方案还有很大的改进空间。

编辑：有关Rcpp时序的信息，请参考Matteo的更新答案。

- Arun

---

感谢您进行实际比较。我已经编辑了我的代码，现在它能够充分发挥Rcpp的作用。问题在于我在NumericVector上使用了push.back()，而不是C++ std::list。 - Matteo Fasiolo

Answer 4

如果你需要快速操作，你可以使用Rcpp包从R调用C++:

library(Rcpp)
library(data.table)
library(microbenchmark)

# Rcpp solution
cppFunction('
NumericVector firstDiff(NumericVector & vett)
{
  const int N = vett.size();

  std::list<double> changes;
  changes.push_back(1.0);

  NumericVector::iterator iterH = vett.begin() + 1;
  NumericVector::iterator iterB = vett.begin();

  int count = 2;
  for(iterH = vett.begin() + 1; iterH != vett.end(); iterH++, iterB++)
  {
    if(*iterH != *iterB) changes.push_back(count);
    count++;
  }

  return wrap(changes);
 }
')

# Data table
dt <- function(input) data.table:::uniqlist(list(input))

# Comparison
set.seed(543)
x <- sort(as.numeric(sample(1e5, 1e7, TRUE)))
microbenchmark(ans1 <- firstDiff(x), which(diff(x) != 0)[1], rle(x),
               ans2 <- dt(x), times = 10) 

Unit: milliseconds
                   expr       min        lq    median        uq       max neval
    ans1 <- firstDiff(x)  50.10679  50.12327  50.14164  50.16343  50.28475    10
  which(diff(x) != 0)[1] 545.66478 547.58388 556.15550 561.78275 617.40281    10
                  rle(x) 664.53262 687.04316 709.84949 714.91528 721.37204    10
                   dt(x)  60.60317  82.30181  82.70207  86.13330  94.07739    10

identical(as.integer(ans1), ans2)
#[1] TRUE

Rcpp比data.table稍微快一点，比其他替代方案要快得多。

- Matteo Fasiolo

---

我非常确定这是由于 list(input) 中的复制造成的。如果你这样做：k = list(input)，然后计时 uniqlist(k)，我猜结果会一样。从 R v3.1 开始，list(.) 不再进行复制。所以，这是一个非常受欢迎的改变！ - Arun

很好！您说得完全正确，如果您事先将x转换为列表，则几乎可以获得完全相同的时间。 - Matteo Fasiolo

Answer 5

> v <- c(1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6)

first.changes <- function(d) {
  p <- cumsum(rle(d)$lengths) + 1
  p[-length(p)]
}

> first.changes(v)
[1]  4  6 11 12 14

或者，使用您的数据，

> v = c(1, 1, 1, 1, 1, 1, 1, 1.5, 1.5, 2, 2, 2, 2, 2)

> first.changes(v)
[1]  8 10

- datawookie