Эффективное совпадение / поиск в R

Question

Начиная с 2 объектов: 1 кадр данных атрибутов заказа - Номера заказов, Веса и Объемы, и 1 список - комбинации строк номеров Заказа.

attr <- data.frame(Order.No = c(111,222,333), Weight = c(20,75,50), Volume = c(10,30,25))
combn <- list(111, 222, 333, c(111,222), c(111,333), c(222,333), c(111,222,333))

Цель состоит в том, чтобы найти общий вес и куб для каждой строки заказов и сохранить только те комбинации, которые находятся в пределах ограничений как веса, так и куба.

В настоящее время я использую следующее -

# Lookup weights for each Order.No in the attr table
# Add up total weight for the combination and keep it if it's in the range
wgts <- lapply(combn, function(x) {
    temp <- attr$Weight[match(x, attr$Order.No)]
    temp <- sum(temp)
    temp[temp <= 50 & temp >= 20]
})
> wgts
[[1]]
[1] 20

[[2]]
numeric(0)

[[3]]
[1] 50

[[4]]
numeric(0)

[[5]]
numeric(0)

[[6]]
numeric(0)

[[7]]
numeric(0)

# Lookup volumes for each Order.No in the attr table
# Add up total volume for the combination and keep it if it's in the range
vols <- lapply(combn, function(x) {
    temp <- attr$Volume[match(x, attr$Order.No)]
    temp <- sum(temp)
    temp[temp <= 50 & temp >= 10]
})
> vols
[[1]]
[1] 10

[[2]]
[1] 30

[[3]]
[1] 25

[[4]]
[1] 40

[[5]]
[1] 35

[[6]]
numeric(0)

[[7]]
numeric(0)

Затем используйте mapply, чтобы объединить два списка весов и объемов.

# Find and keep only the rows that have both the weights and volumes within their ranges  
which(lapply(mapply(c, wgts, vols), function(x) length(x)) == 2)

# Yields position 1 and 3 which meet the subsetting conditions    
> value value 
    1     3

Приведенный выше код просматривает веса и кубы отдельных заказов, суммирует их все вместе, проверяет, чтобы убедиться, что они находятся в пределах каждого предела диапазона, объединяет оба списка и сохраняет только те, которые имеют вес и кубы в допустимых диапазонах.

Мое текущее решение, которое успешно завершает задачу, очень медленно по объему производства и плохо масштабируется с миллионами записей. Для поиска комбинаций порядка 11 ММ этот процесс занимает ~40 минут, что недопустимо.

Я ищу более эффективный метод, который значительно сократит время выполнения, необходимое для получения того же результата.

Answer 1

# changing names, assigning indices to order list
atdf  = data.frame(Order.No = c(111,222,333), Weight = c(20,75,50), Volume = c(10,30,25))
olist = list(111, 222, 333, c(111,222), c(111,333), c(222,333), c(111,222,333))
olist <- setNames(olist,seq_along(olist))

# defining filtering predicate:

sel_orders = function(os, mins=c(20,10), maxs=c(50,50)) {
    tot = colSums(atdf[match(os, atdf$Order.No), c("Weight","Volume")])
    all(maxs >= tot & tot >= mins)
}

# Filtering orders

olist[sapply(olist, sel_orders)]
# or 
Filter(x = olist, f = sel_orders)

оба из которых дают

# $`1`
# [1] 111
# 
# $`3`
# [1] 333

Чтобы изменить максимумы и минуты...

olist[ sapply(olist, sel_orders, mins = c(0,0), maxs = c(70,70)) ]

# $`1`
# [1] 111
# 
# $`3`
# [1] 333
# 
# $`5`
# [1] 111 333

Answer 2

Не знаю, насколько быстрее это будет, но вот решение dplyr/tidyr.

library(dplyr)
library(tidyr)

combination = 
  data_frame(Order.No = combn) %>%
  mutate(combination_ID = 1:n()) %>%
  unnest(Order.No)

acceptable = 
  combination %>%
  left_join(attr) %>%
  group_by(combination_ID) %>%
  summarize(total_weight = sum(Weight),
         total_volume = sum(Volume)) %>%
  filter(total_weight %>% between(20, 50) &
           total_volume %>% between(10, 50) )