R语言 最快验证元素对的排序向量,直到它们无序配对

qmb5sa22  于 2023-02-06  发布在  其他
关注(0)|答案(3)|浏览(111)

我有一个长度为N的未排序向量。向量中的每个元素恰好出现两次(向量长度为偶数)。我有一个自定义排序算法,目标是迭代,直到向量达到每个元素都与其副本相邻的状态。
Unsorted vector = {A,F,J,E,F,A,J,E}
A valid sorted state = {A,A,J,J,E,E,F,F}
Another valid sorted state = {J,J,A,A,F,F,E,E}
所以我的问题在于,检查排序状态是否有效的最快方法是什么,这样我就可以加快迭代速度,对于长向量,这将决定我的大部分缩放能力。

e4yzc0pl

e4yzc0pl1#

一些快速和肮脏的,但我不知道它会永远工作:

all(duplicated(x) == c(FALSE,TRUE))

这依赖于两个相同的值总是彼此相邻的事实,一个不重复,下一个重复。似乎与测试集一起工作:

x <- c("A", "F", "J", "E", "F", "A", "J", "E")
s1 <- c("A", "A", "J", "J", "E", "E", "F", "F")
s2 <- c("J", "J", "A", "A", "F", "F", "E", "E")

all(duplicated(x) == c(FALSE,TRUE))
#[1] FALSE

all(duplicated(s1) == c(FALSE,TRUE))
#[1] TRUE

all(duplicated(s2) == c(FALSE,TRUE))
#[1] TRUE

它非常快,在我的机器上,用百分之五秒的时间浏览一百万个长度的向量:

x <- rep(1:1e6, each=2)
system.time(all(duplicated(x) == c(FALSE,TRUE)))
#   user  system elapsed 
#   0.04    0.00    0.05
dgsult0t

dgsult0t2#

其中一个选项涉及将vector(因为lengtheven,并且某个元素恰好出现两次)转换为两行矩阵,获取unique并测试行数是否为1。如果重复的值相邻,则在将dim属性与matrix相加时,第二行将与第一行完全相同

f1 <- function(x)
{
nrow(unique(matrix(x, nrow = 2))) == 1
}
  • 测试
> v1 <- c("A", "F", "J", "E", "F", "A", "J", "E")
> v2 <- c("A", "A", "J", "J", "E", "E", "F", "F")
> v3 <- c("J", "J", "A", "A", "F", "F", "E", "E")
> f1(v1)
[1] FALSE
> f1(v2)
[1] TRUE
> f1(v3)
[1] TRUE

或者稍微快一点

f2 <- function(x) 
  {
  sum(duplicated(matrix(x, nrow = 2))) == 1
}
  • 测试
> f2(v1)
[1] FALSE
> f2(v2)
[1] TRUE
> f2(v3)
[1] TRUE
  • 基准
#thelatemail
> f3 <- function(x) all(duplicated(x) == c(FALSE,TRUE))
#TarJae
> f4 <- function(x) {rle_obj <- rle(x); all(rle_obj$lengths > 1)}

> x1 <- rep(1:1e8, each = 2)
> system.time(f1(x1))
   user  system elapsed 
  2.649   0.456   3.111 
> system.time(f2(x1))
   user  system elapsed 
  2.258   0.433   2.694 
> system.time(f3(x1))
   user  system elapsed 
  9.972   1.272  11.233 
> system.time(f4(x1))
   user  system elapsed 
  7.051   3.281  10.333
e4eetjau

e4eetjau3#

另一个选项是使用rle函数:

v1 <- c("A", "F", "J", "E", "F", "A", "J", "E")
v2 <- c("A", "A", "J", "J", "E", "E", "F", "F")
v3 <- c("J", "J", "A", "A", "F", "F", "E", "E")

rle_obj <- rle(v3)
all(rle_obj$lengths > 1)

试验:

> rle_obj <- rle(v1)
> all(rle_obj$lengths > 1)
[1] FALSE

> rle_obj <- rle(v2)
> all(rle_obj$lengths > 1)
[1] TRUE

> rle_obj <- rle(v3)
> all(rle_obj$lengths > 1)
[1] TRUE
>

相关问题