有效地找到子集的独特组（例如独特的购物篮）

Question

我有一个数据框，其中一栏代表购物篮的索引。对于每个购物篮，我还有另一列标识该购物篮中的物品。在数据集中查找唯一篮子的最有效方法是什么？

这是一个利用示例dplyr：

outer_num <- 10000
tmp_df <-
    data.frame(basket_index = rep(1:(8*outer_num), each = 2),
               items_purchased = rep(rep(c(1, 1, 2, 2, 1, 1, 3, 3), 2), outer_num))

items_purchased_df <-
    data.frame(items_purchased = 1:3, 
               item_name = c("shampoo", "soap", "conditioner"))

tmp_df_2 <-
    tmp_df %>%
    inner_join(items_purchased_df) %>%
    select(basket_index, items_purchased = item_name) 

head(tmp_df_2, 16)
#    basket_index items_purchased
# 1             1         shampoo
# 2             1         shampoo
# 3             2            soap
# 4             2            soap
# 5             3         shampoo
# 6             3         shampoo
# 7             4     conditioner
# 8             4     conditioner
# 9             5         shampoo
# 10            5         shampoo
# 11            6            soap
# 12            6            soap
# 13            7         shampoo
# 14            7         shampoo
# 15            8     conditioner
# 16            8     conditioner

在此示例中，我们看到只有三个唯一的篮子，每个篮子有两个项目。通常，篮子可能没有相同数量的物品，可能有也可能没有重复的物品，在某些情况下，篮子中物品的出现顺序很重要。

以下函数产生可接受的输出：

tmp_fn <- function(tmp_df) {
    tmp_df %>%
        group_by(basket_index) %>%
        mutate(collapsed_purchases = paste0(items_purchased, collapse = ',')) %>%
        group_by(collapsed_purchases) %>%
        filter(basket_index == min(basket_index)) %>%
        ungroup
}

以便

tmp_fn(tmp_df_2)
#   basket_index items_purchased collapsed_purchases    
#           <int> <fct>           <chr>                  
# 1            1 shampoo         shampoo,shampoo        
# 2            1 shampoo         shampoo,shampoo        
# 3            2 soap            soap,soap              
# 4            2 soap            soap,soap              
# 5            4 conditioner     conditioner,conditioner
# 6            4 conditioner     conditioner,conditioner

这不是很省时。将项目因子转换为整数（并假设这是一个瞬时过程！）可以将其提高近两个数量级，但是即使在这个小的数据集上也要花费半秒的时间：

tmp_df_3 <-
    tmp_df_2 %>%
    mutate(items_purchased_old = items_purchased,
           items_purchased = as.integer(factor(items_purchased)))

microbenchmark::microbenchmark(tmp_fn(tmp_df_2), times = 10)
# Unit: seconds
#            expr     min       lq     mean   median       uq      max neval
# tmp_fn(tmp_df_2) 20.6301 20.93541 21.98261 22.24193 22.43473 23.77921    10

microbenchmark::microbenchmark(tmp_fn(tmp_df_3), times = 10)
# Unit: milliseconds
#       expr      min       lq     mean   median       uq      max neval
# tmp_fn(tmp_df_3) 348.3901 358.0814 507.7983 363.7639 387.2384 1566.903    10

Answer 1

更新：我的结果是stringsAsFactors = F. 如果没有这个，与 OP 的功能相比，就没有显着的性能提升tmp_fn()。

据我所知，group_by + mutate而且group_by + filter很慢。这是避免这种情况的方法 -

# for outer_num <- 10000
system.time(
  res <- tmp_df_2 %>%
    group_by(basket_index) %>%
    summarize(collapsed_purchases = paste0(items_purchased, collapse = ',')) %>%
    filter(!duplicated(collapsed_purchases)) 
    # summarize drops one (in this case, the only) grouping level
    # so filter is on ungrouped data which is good; also duplicated() is fast enough
)

# user  system elapsed 
# 4.35    0.00    4.41 

res
# A tibble: 3 x 2
#   basket_index collapsed_purchases    
#          <int> <chr>                  
# 1            1 shampoo,shampoo        
# 2            2 soap,soap              
# 3            4 conditioner,conditioner

# get desired result
tmp_df_2 %>% 
  inner_join(res, by = "basket_index")

#   basket_index items_purchased     collapsed_purchases
# 1            1         shampoo         shampoo,shampoo
# 2            1         shampoo         shampoo,shampoo
# 3            2            soap               soap,soap
# 4            2            soap               soap,soap
# 5            4     conditioner conditioner,conditioner
# 6            4     conditioner conditioner,conditioner

注意： 使用data.table可能会提供更快的速度。