将 data.table 分成大致相等的部分

Question

为了并行化一个任务，我需要将一个大 data.table 分成大致相等的部分，将由列定义的组保持在一起，id。假设：

N是数据的长度

k 是 id

的不同值的数量

M是想要的零件数

想法是 M << k << N，所以按 id 拆分是不好的。

library(data.table)
library(dplyr)

set.seed(1)
N <- 16 # in application N is very large
k <- 6  # in application k << N
dt <- data.table(id = sample(letters[1:k], N, replace=T), value=runif(N)) %>%
      arrange(id)
t(dt$id)

#     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16]
# [1,] "a"  "b"  "b"  "b"  "b"  "c"  "c"  "c"  "d"  "d"   "d"   "e"   "e"   "f"   "f"   "f"

在此示例中，M=3 所需的拆分是 {{a,b}, {c,d}, {e,f}} M=4 是 {{a,b}, {c}, {d,e}, {f}}

更一般地说，如果 id 是数字，则截止点应该是
quantile(id, probs=seq(0, 1, length.out = M+1), type=1) 或类似的分成大致相等的部分。

执行此操作的有效方法是什么？

Answer 1

如果 id 的分布没有病态偏斜，最简单的方法就是这样：

split(dt, as.numeric(as.factor(dt$id)) %% M)

它使用 factor-value mod number-of buckets 将 id 分配给 bucket。

对于大多数应用程序来说，获得相对均衡的数据分布就足够了。不过，您应该小心输入时间序列等。在这种情况下，您可以在创建因子时简单地强制执行随机级别顺序。为 M 选择质数是一种更可靠的方法，但很可能不太实用。

Answer 2

初步评论

我建议阅读 the main author of data.table has to say 关于并行化的内容。

不知道你对data.table有多熟悉，但你可能忽略了它的by论点...？从下面引用@eddi 的评论...

Instead of literally splitting up the data - create a new "parallel.id" column, and then call
dt[, parallel_operation(.SD), by = parallel.id] 

回答，假设你不想使用by

按大小对 ID 进行排序：

ids   <- names(sort(table(dt$id)))
n     <- length(ids)

重新排列，以便我们在大 ID 和小 ID 之间交替，following Arun's interleaving trick:

alt_ids <- c(ids, rev(ids))[order(c(1:n, 1:n))][1:n]

按顺序拆分id，每组的id数量大致相同（如）：

gs  <- split(alt_ids, ceiling(seq(n) / (n/M)))

res <- vector("list", M)
setkey(dt, id)
for (m in 1:M) res[[m]] <- dt[J(gs[[m]])] 
# if using a data.frame, replace the last two lines with
# for (m in 1:M) res[[m]] <- dt[id %in% gs[[m]],]

检查尺寸是否太差：

# using the OP's example data...

sapply(res, nrow)
# [1] 7 9              for M = 2
# [1] 5 5 6            for M = 3
# [1] 1 6 3 6          for M = 4
# [1] 1 4 2 3 6        for M = 5

虽然我在顶部强调了 data.table，但它应该也可以与 data.frame 一起使用。

Answer 3

如果k足够大，可以用这个思路对数据进行分组：

首先，让我们找出每个 ID 的大小

group_sizes <- dt[, .N, by = id]

然后创建 2 个长度为 M 的空列表，用于检测组的大小以及它们将包含哪些 ID

grps_vals <- list()
grps_vals[1 : M] <- c(0)

grps_nms <- list()
grps_nms[1 : M] <- c(0)

（这里我特地添加了零值，以便能够创建大小为 M 的列表）

然后在每次迭代中使用循环将值添加到最小组。它将使组大致相等

for ( i in 1:nrow(group_sizes)){
   sums <- sapply(groups, sum) 
   idx <- which(sums == min(sums))[1]
   groups[[idx]] <- c(groups[[idx]], group_sizes$N[i])
   }

最后，从名称列表中删除第一个零元素:)

grps_nms <- lapply(grps_nms, function(x){x[-1]})

> grps_nms
[[1]]
[1] "a" "d" "f"

[[2]]
[1] "b"

[[3]]
[1] "c" "e"

Answer 4

只是使用 dplyr 的替代方法。运行逐步链接的脚本，以可视化数据集在每个步骤中的变化情况。这是一个简单的过程。

    library(data.table)
    library(dplyr)

    set.seed(1)
    N <- 16 # in application N is very large
    k <- 6  # in application k << N
    dt <- data.table(id = sample(letters[1:k], N, replace=T), value=runif(N)) %>%
      arrange(id)



dt %>% 
  select(id) %>%
  distinct() %>%                   # select distinct id values
  mutate(group = ntile(id,3)) %>%  # create grouping 
  inner_join(dt, by="id")          # join back initial information

PS：根据之前的回答，我学到了很多有用的东西。

将 data.table 分成大致相等的部分

Split data.table into roughly equal parts

parallel-processing

r

data.table