大二进制数如何减法？

Question

我想比较学生在多项答案测试中的回答，看看哪些学生仅偏离一个答案。我已经将答案（例如 ABCDE）转换为命中或未命中（例如 00101）。该测试有 45 个问题，因此答案和命中字符串非常长（例如 100000000000000010000010010001001000000000100）。由于浮点错误，Base R 甚至无法将这些字符串作为数字处理。

我有

texts_1

的答案，答对了 n 个问题，

texts_2

的答案答对了 n+1 个问题。然后我将

texts_1

中的每一行与

texts_2

中的每一行进行比较，以查找具有一个字符不同的字符串。

实现此目的的一种方法是使用

adist

。

if (adist(texts_1[line_1], texts_2[line_2]) == 1) { ... }

如果结果是 1，我知道文本中只有一处不同。这可行，但问题是

adist

非常慢，而且我有数千次比较要做。花了 4 个小时进行 20000 x 30000 次比较。

我的想法是将命中和未命中的字符串视为一个数字，然后将它们相减。如果答案是 10 的幂，我就知道只有一个问题不同。例如1101 - 1001 是 10 的幂。但是，R 无法处理这么大的数字。有没有一个包可以让我处理这么大的二进制数？减法和除法？另外，一些二进制数将以零开头。

tl;博士：如何在R中减去001111111111111101111011111111111111111111111 - 001111111111111101111011111111111110111111111？然后检查答案是否是10的幂？

Answer 1

如果我正确理解问题，这可能会有所帮助

如果这些是你的测试

set.seed(42)
stud_tests1 <- replicate(20, paste(sample(0:1, 45, replace=T), collapse=""))
stud_tests2 <- replicate(20, paste(sample(0:1, 45, replace=T), collapse=""))

stud_tests2[6] <- "010010110110101001110110111010110111110110011"

获得仅相差一个的测试

one <- strsplit(stud_tests1, "")
two <- strsplit(stud_tests2, "")

res <- sapply(one, \(x) sapply(two, \(y) sum(x != y) == 1))

获取测试号码

cbind(one = ceiling(which(res) / length(one)), two = which(res) %% length(two))
     one two
[1,]  18   6

Answer 2

您可以将

strsplit

放入

"numeric"

矩阵，使用

dist

，最后使用

which()

arr.ind=TRUE

。这大约快了 80 倍。

长度为 1e3 的向量的示例：

> ## using `adist`
> system.time({
+   ad <- adist(a) |> as.matrix()
+   ares <- which(ad == 1, arr.ind=TRUE)
+ })
   user  system elapsed 
  8.642   0.000   8.633 
> 
> ## using `dist`
> system.time({
+   b <- strsplit(a, '') |> do.call(what='rbind') |> `mode<-`('numeric')
+   bd <- dist(b) |> as.matrix()
+   bres <- which(bd == 1, arr.ind=TRUE)
+ })
   user  system elapsed 
  0.098   0.011   0.109 
> 
> stopifnot(all.equal(ares, bres, check.attributes=FALSE))
> 
> head(bres)
    row col
342 342   4
475 475  29
587 587  62
373 373 131
650 650 156
710 710 174

让我们查看随机结果。

> set.seed(42)
> a[bres[sample.int(nrow(bres), 1L), ]] |> as.data.frame()
          a[bres[sample.int(nrow(bres), 1L), ]]
1 101111011111110111111111111111111111111111111
2 101111011111110111111111111111111111101111111
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^

---

数据：

set.seed(42)
> a <- replicate(1e3, sample(0:1, 45, replace=TRUE, prob=c(6, 39)) |> 
+                  paste(collapse=''))