代码之家 › 专栏 › 技术社区 › J. Mini

有没有更有效的匹配版本来搜索重复的数字排列?

match indexing optimization r

-1

J. Mini · 技术社区 · 5 年前

我有一个20行n列的数据集。我最初使用的是n=10000,但我发现我需要使用一个更大的数字,可能是这个数字的十倍多。此数据集的每一列都是独立于其他列生成的,并且包含从1到20的随机但有偏差的整数排列。我希望对整个数据集上每个数字的位置求和。换句话说,我想知道数字a在每个a和b的bth位置出现了多少次(即,我的最终结果是一个20*20的值表)。

我相信我已经有了实现这一目标的代码。例如,我的计算机在不到两分钟的时间内处理了整个n=10000的原因(即,它给出了每个a和b的计数)。然而,n=100000和较小的n=50000花费了如此长的时间,以至于我的耐心耗尽了。我的大多数代码都非常简单,我相信效率低下的原因在于 match 在以下行中( a , b 和 n 如上所述, data 是数据集):

list<-c()
  for(k in 1:n)
  {
    position<-match(a, data[,k])
    list<-c(list,position)
  }
  return(sum(list==b))

我如何改进这一点? 火柴 appears to be notoriously slow ,但我看到的所有解决方案( example )既不是一般解决方案,也不适用于这种情况。

如果希望对解决方案进行基准测试 replicate(n,sample(20)) 将生成与我的数据集类似的列表。

2 回复 | 直到 5 年前

Ronak Shah 5 年前

我认为主要的瓶颈是您正在增加循环中向量的大小。尝试在循环之前初始化它,并在向量中赋值。

list_vec <- numeric(length = n)

for(k in 1:n) {
  list_vec[k] <- match(a, data[,k])
}

或使用 sapply

sapply(data, function(x) match(a, x))

chinsoon12 5 年前

选项使用 data.table :

library(data.table)
DT <- data.table(ri=rep(1:20, n), v=as.vector(l))
dcast(DT, ri ~ v, length)

输出:

    ri   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
 1:  1 499 506 481 507 434 498 537 493 495 474 504 506 545 499 492 467 510 527 507 519
 2:  2 506 513 473 521 520 492 508 518 469 520 491 463 495 520 499 526 502 481 492 491
 3:  3 481 499 510 480 506 499 493 522 512 507 516 484 516 482 536 476 509 477 500 495
 4:  4 502 498 519 532 493 522 481 515 542 488 471 496 466 443 460 505 531 481 532 523
 5:  5 497 468 523 492 475 430 502 491 526 514 490 528 460 498 471 557 488 547 521 522
 6:  6 514 505 497 506 533 505 482 462 536 508 482 533 505 497 527 496 479 479 479 475
 7:  7 525 522 511 476 502 536 508 486 495 452 493 506 507 498 530 498 475 478 498 504
 8:  8 544 450 521 528 491 497 534 503 504 497 506 464 485 501 511 467 478 484 523 512
 9:  9 442 515 515 507 496 515 460 537 528 510 490 500 526 510 499 508 497 517 465 463
10: 10 513 505 497 517 486 483 518 483 503 491 495 514 507 483 485 514 516 501 498 491
11: 11 480 530 491 486 503 507 517 487 467 499 504 497 496 521 499 444 525 511 500 536
12: 12 507 464 506 537 516 489 480 500 450 507 490 539 482 484 508 483 522 519 471 546
13: 13 501 527 521 443 510 527 507 507 492 547 486 465 515 544 504 472 502 529 456 445
14: 14 478 494 502 464 495 515 503 504 514 475 522 471 529 487 509 548 500 505 510 475
15: 15 489 513 488 505 532 487 506 525 438 530 534 497 494 475 491 494 468 499 544 491
16: 16 520 484 467 516 480 498 508 503 512 472 535 503 533 526 505 508 495 477 460 498
17: 17 512 465 491 514 516 469 487 485 491 465 522 550 494 514 506 542 508 476 490 503
18: 18 505 526 503 499 502 518 484 489 508 513 476 491 505 478 482 523 500 461 555 482
19: 19 528 508 492 488 513 513 493 474 500 510 467 474 463 543 482 495 523 522 505 507
20: 20 457 508 492 482 497 500 492 516 518 521 526 519 477 497 504 477 472 529 494 522

数据:

set.seed(0L)
n <- 1e4
l <- replicate(n, sample(20))

eipi10 5 年前

这在我两岁的Macbook Pro上花了大约1.4秒(尽管@chinsoon12的data.table解决方案快得多——在我的机器上大约0.04秒):

library(tidyverse)

# Fake data matrix, 20 rows x 100,000 columns
n = 100000
set.seed(2)
d = replicate(n, sample(1:20))

# Convert to long data frame and count positions
d %>% 
  as_tibble() %>% 
  pivot_longer(cols=everything()) %>% 
  arrange(name) %>% 
  mutate(position = rep(1:20, n)) %>% 
  group_by(value, position) %>% 
  tally

   value position     n
   <int>    <int> <int>
 1     1        1  4901
 2     1        2  5031
 3     1        3  4980
 4     1        4  4997
 5     1        5  4959
 6     1        6  5004
 7     1        7  4888
 8     1        8  5021
 9     1        9  4970
10     1       10  4986
# â¦ with 390 more rows

Enrico Schumann 5 年前

如果我理解正确,这可以快速完成,无需任何软件包:

n <- 10000
k <- 20
data <- replicate(n, sample(k))


## The result: a k times k array.
## E.g. result[1, 5] tells you how often 
## 5 appears in row 1.

result <- array(NA, dim = c(k, k))


for (i in 1:k) {
    tmp <- data[seq(i, to = length(data), by = k)]
    for (j in 1:k)
        result[i, j] <- sum(tmp == j)
}

一百万个样本( n == 1e6 ),大约需要2秒左右。

Parfait 5 年前

避免在循环中增加对象,避免在初始化后将其指定给对象。考虑 sapply 或者稍微快一点, vapply (验证类型和长度返回):

myVec <- sapply(seq(n), function(k) match(a, data[,k]))
sum(myVec==b)

myVec <- vapply(seq(n), function(k) match(a, data[,k]), integer(1))
sum(myVec==b)