«рекурсивное» самостоятельное объединение в data.table - PullRequest
Новая
       24

«рекурсивное» самостоятельное объединение в data.table

4 голосов
/ 30 июня 2019

У меня есть список компонентов, состоящий из 3 столбцов: продукт, компонент и количество использованного компонента: 

a <- structure(list(prodName = c("prod1", "prod1", "prod2", "prod3", 
"prod3", "int1", "int1", "int2", "int2"), component = c("a", 
"int1", "b", "b", "int2", "a", "b", "int1", "d"), qty = c(1L, 
2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L)), row.names = c(NA, -9L), class = c("data.table", 
"data.frame"))

  prodName component qty
1    prod1         a   1
2    prod1      int1   2
3    prod2         b   3
4    prod3         b   4
5    prod3      int2   5
6     int1         a   6
7     int1         b   7
8     int2      int1   8
9     int2         d   9

Продукты с названиями, начинающимися с prod, являются конечными продуктами, названия которых похожиint являются промежуточными продуктами, а те, что с буквами, являются сырьем.

Мне нужен полный список компонентов конечных продуктов с использованием только сырьякомпоненты .То есть я хочу преобразовать любой int в сырье.

  • Промежуточные продукты могут состоять из сырья и других промежуточных продуктов, поэтому я ссылаюсь на "рекурсивный".
  • Я не могу заранее знать уровень вложенности / рекурсии промежуточного продукта (в данном примере 2 уровня, больше фактических данных - 6).

Для этого примера мой ожидаемый результат - (я явно указал вычисление полученного числа): 

prodName  |component  |qty
prod1     |a          |1+2*6 = 13
prod1     |b          |0+2*7 = 14
prod2     |b          |3
prod3     |b          |4+5*8*7 = 284
prod3     |a          |0+5*8*6 = 240
prod3     |d          |0+5*9 = 45

Что я сделал:

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

#load data.table
library(data.table)

# split the tables between products and different levels of intermediate
a1 <- a[prodName %like% "prod",]
b1 <- a[prodName %like% "int1",]
c1 <- a[prodName %like% "int2",]

# convert int2 to raw materials
d1 <- merge(c1, 
            b1, 
            by.x = "component", 
            by.y = "prodName", 
            all.x = TRUE)[
              is.na(component.y),
              component.y := component][
                is.na(qty.y),
                qty.y := 1][,
                                .(prodName, qty = qty.x*qty.y),
                                by = .(component = component.y)]

# Since int1 is already exploded into raw materials, rbind both tables:
d1 <- rbind(d1, b1)

# convert all final products into raw materials, except that the raw mats that go directly into the product won't appear:
e1 <- merge(a1, 
            d1, 
            by.x = "component", 
            by.y = "prodName", 
            all.x = TRUE)

# rbind the last calculated raw mats (those coming from intermediate products) with those coming _directly_ into the final product:
result <- rbind(e1[!is.na(qty.y), 
                   .(prodName, qty = qty.x * qty.y), 
                   by = .(component = component.y)], 
                e1[is.na(qty.y), 
                   .(prodName, component, qty = qty.x)])[, 
                                                         .(qty = sum(qty)), 
                                                         keyby = .(prodName, component)]

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

Существует ли более простой / лучший способ сделать этот вид рекурсивныхприсоединиться

Ответы [ 3 ]

4 голосов
/ 30 июня 2019

По сути, ваши данные представляют собой взвешенный крайний список в ориентированном графе.Приведенный ниже код напрямую вычисляет сумму расстояний (продукта) по каждому простому пути из необработанного компонента -> конечного продукта с использованием библиотеки igraph: 

library(igraph)

## transform edgelist into graph
graph <- graph_from_edgelist(as.matrix(a[, c(2, 1)])) %>%
  set_edge_attr("weight", value = unlist(a[, 3]))

## combinations raw components -> final products
out <- expand.grid(prodname = c("prod1", "prod2", "prod3"), component = c("a", "b", "d"), stringsAsFactors = FALSE)

## calculate quantities
out$qty <- mapply(function(component, prodname) {

  ## all simple paths from component -> prodname
  all_paths <- all_simple_paths(graph, from = component, to = prodname)

  ## if simple paths exist, sum over product of weights for each path
  ifelse(length(all_paths) > 0,
         sum(sapply(all_paths, function(path) prod(E(graph, path = path)$weight))), 0)

}, out$component, out$prodname)

out
#>   prodname component qty
#> 1    prod1         a  13
#> 2    prod2         a   0
#> 3    prod3         a 240
#> 4    prod1         b  14
#> 5    prod2         b   3
#> 6    prod3         b 284
#> 7    prod1         d   0
#> 8    prod2         d   0
#> 9    prod3         d  45
3 голосов
/ 30 июня 2019

Вот моя попытка использовать ваш набор данных.

Используется проверка цикла while, чтобы увидеть, есть ли какие-либо components, которые также находятся в поле prodName.Цикл всегда должен иметь одинаковые поля, поэтому вместо добавления столбца для рекурсивных множителей (т. Е. 5 * 8 * 7 в конце) интегрируются итерационные множители.То есть 5 * 8 * 7 становится 5 * 56 в конце. 

library(data.table)

a[, qty_multiplier := 1]
b <- copy(a)

while (b[component %in% prodName, .N] > 0) {
  b <- b[a
         , on = .(prodName = component)
         , .(prodName = i.prodName
             , component = ifelse(is.na(x.component), i.component, x.component)
             , qty = i.qty
             , qty_multiplier = ifelse(is.na(x.qty), 1, x.qty * qty_multiplier)
         )
         ]
}

b[prodName %like% 'prod', .(qty = sum(qty * qty_multiplier)), by = .(prodName, component)] 

   prodName component qty
1:    prod1         a  13
2:    prod1         b  14
3:    prod2         b   3
4:    prod3         b 284
5:    prod3         a 240
6:    prod3         d  45
1 голос
/ 30 июня 2019

Я думаю, вам лучше представлять информацию в виде набора матриц смежности, которые сообщают вам «Как много из этого сделано из этого». Вам нужно 4 матрицы, соответствующие всем возможным отношения. Например, вы помещаете связь между конечным продуктом и промежуточным продуктом в матрицу из 3 строк. и 2 столбца, как это: 

QPI <- matrix(0,3,2)
row.names(QPI) <- c("p1","p2","p3")
colnames(QPI) <- c("i1","i2")

QPI["p1","i1"] <- 2
QPI["p3","i2"] <- 5

   i1 i2
p1  2  0
p2  0  0
p3  0  5

это говорит о том, что для получения одной единицы конечного продукта требуется 2 единицы промежуточного продукта i1 p1.

Аналогично вы определяете другие матрицы: 

QPR <- matrix(0,3,3)
row.names(QPR) <- c("p1","p2","p3")
colnames(QPR) <- c("a","b","d")

QPR["p1","a"] <- 1
QPR["p2","b"] <- 3
QPR["p3","b"] <- 4

QIR <- matrix(0,2,3)
row.names(QIR) <- c("i1","i2")
colnames(QIR) <- c("a","b","d")

QIR["i1","a"] <- 6
QIR["i1","b"] <- 7
QIR["i2","d"] <- 9

QII <- matrix(0,2,2)
row.names(QII) <- colnames(QII) <- c("i1","i2")

Например, глядя на QIR, мы видим, что для производства одной единицы промежуточного продукта i1 требуется 6 единиц сырья a. Получив это таким образом, вы суммируете все возможные пути перехода от сырья к финалу. произведение с использованием умножения матриц.

У вас есть 3 условия: вы можете перейти непосредственно от исходного к окончательному [QPR] QPR или перейти от исходного к промежуточному в финал [QPI%*%QIR] или из исходного в промежуточное звено в другое промежуточное в финальное [QPI%*%QII%*%QIR]

Ваш результат в конце представлен матрицей 

result <- QPI%*%QIR + QPI%*%QII%*%QIR + QPR

Я собрал весь код ниже. Если вы запустите его, вы увидите, что результат выглядит так: 

     a   b  d
p1  13  14  0
p2   0   3  0
p3 240 284 45

, который говорит то же самое, что и 

prodName  |component  |qty
prod1     |a          |1+2*6 = 13
prod1     |b          |0+2*7 = 14
prod2     |b          |3
prod3     |b          |4+5*8*7 = 284
prod3     |a          |0+5*8*6 = 240
prod3     |d          |0+5*9 = 45

надеюсь, это поможет 

QPI <- matrix(0,3,2)
row.names(QPI) <- c("p1","p2","p3")
colnames(QPI) <- c("i1","i2")

QPI["p1","i1"] <- 2
QPI["p3","i2"] <- 5

QPR <- matrix(0,3,3)
row.names(QPR) <- c("p1","p2","p3")
colnames(QPR) <- c("a","b","d")

QPR["p1","a"] <- 1
QPR["p2","b"] <- 3
QPR["p3","b"] <- 4

QIR <- matrix(0,2,3)
row.names(QIR) <- c("i1","i2")
colnames(QIR) <- c("a","b","d")

QIR["i1","a"] <- 6
QIR["i1","b"] <- 7
QIR["i2","d"] <- 9

QII <- matrix(0,2,2)
row.names(QII) <- colnames(QII) <- c("i1","i2")


QII["i2","i1"] <- 8

result <- QPI%*%QIR + QPI%*%QII%*%QIR + QPR
print(result)
...