在data.table中对integer64进行二进制搜索

Question

我有一个integer64索引的data.table对象：

library(data.table)
library(bit64)

some_data = as.integer64(c(1514772184120000026, 1514772184120000068, 1514772184120000042, 1514772184120000078,1514772184120000011, 1514772184120000043, 1514772184120000094, 1514772184120000085,
1514772184120000083, 1514772184120000017, 1514772184120000013, 1514772184120000060, 1514772184120000032, 1514772184120000059, 1514772184120000029))

#
n <- 10
x <- setDT(data.frame(a = runif(n)))
x[, new_col := some_data[1:n]]
setorder(x, new_col)

然后，我需要在原始data.table对象(x)的索引中进行二进制搜索，以查找许多其他integer64：

search_values <- some_data[(n+1):length(some_data)]

如果这些是本机整数，我可以使用findInterval()来解决这个问题：

values_index  <- findInterval(search_values, x$new_col)

但是当findInterval的参数为integer64时，我得到：

Warning messages:
1: In as.double.integer64(vec) :
  integer precision lost while converting to double
2: In as.double.integer64(x) :
  integer precision lost while converting to double

和错误的索引：

> values_index
[1] 10 10 10 10 10

例如，search_values的条目都大于x$new_col的所有条目的说法是不正确的。

编辑：

所需输出：

print(values_index)
9 10  6 10  1

为什么？：

value_index有和search_values一样多的条目。对于search_values的每个条目，value_index中的相应条目提供了search_values条目在插入到x$new_col中时所具有的等级。因此，value_index的第一个条目是9，因为search_values (1514772184120000045)的第一个条目在x$new_col的条目中具有排名9。

Answer 1

也许你想要这样的东西：

findInterval2 <- function(y, x) {
  toadd <- y[!(y %in% x$new_col)] # search_values that is not in data
  x2 <- copy(x)
  x2[, i := .I] # mark the original data set
  x2 <- rbindlist(list(x2, data.table(new_col = toadd)),
                  use.names = T, fill = T) # add missing search_values
  setkey(x2, new_col) # order
  x2[, index := cumsum(!is.na(i))]
  x2[match(y, new_col), index]
}
# x2 is:
#              a             new_col  i index
#  1: 0.56602278 1514772184120000011  1     1
#  2:         NA 1514772184120000013 NA     1
#  3: 0.29408237 1514772184120000017  2     2
#  4: 0.28532378 1514772184120000026  3     3
#  5:         NA 1514772184120000029 NA     3
#  6:         NA 1514772184120000032 NA     3
#  7: 0.66844754 1514772184120000042  4     4
#  8: 0.83008829 1514772184120000043  5     5
#  9:         NA 1514772184120000059 NA     5
# 10:         NA 1514772184120000060 NA     5
# 11: 0.76992760 1514772184120000068  6     6
# 12: 0.57049677 1514772184120000078  7     7
# 13: 0.14406169 1514772184120000083  8     8
# 14: 0.02044602 1514772184120000085  9     9
# 15: 0.68016024 1514772184120000094 10    10
findInterval2(search_values, x)
# [1] 1 5 3 5 3

如果没有，那么您可以根据需要更改代码。

更新

查看此整数示例，可以看到此函数与基本findInterval给出相同的结果

now <- 10
n <- 10
n2 <- 10
some_data = as.integer(now + sample.int(n + n2, n + n2))
x <- setDT(data.frame(a = runif(n)))
x[, new_col := some_data[1:n]]
setorder(x, new_col)
search_values <- some_data[(n + 1):length(some_data)]

r1 <- findInterval2(search_values, x)
r2 <- findInterval(search_values, x$new_col)
all.equal(r1, r2)

Answer 2

如果我得到了您想要的东西，那么一个快速的解决方法可能是：

toadd <- search_values[!(search_values %in% x$new_col)] # search_values that is not in data
x[, i := .I] # mark the original data set
x <- rbindlist(list(x, data.table(new_col = toadd)),
               use.names = T, fill = T) # add missing search_values
setkey(x, new_col) # order
x[, index := new_col %in% search_values] # mark where the values are
x[, index := cumsum(index)] # get indexes
x <- x[!is.na(i)] # remove added rows
x$index # should contain your desired output