4
\$\begingroup\$

I have a set of products(e.g. P0006, P0009, etc.) and a set of production lines (eg. L1H175, L2H175). A product can be produced on a subset of the lines set (and not necessarily all of them).

If we decide to produce a product on a production line(assuming that the line can actually produce it), we need to buy the appropriate raw materials (e.g. If we decide to produce P0009 on L1h175 we need to buy the set of the selected raw materials in the image). Each raw material has a price and a property(S or NS).

What I want the code to do:

  1. For each product, return where it can be produced. For example, to see where P0009 can be produced, I need to look at all the rows of the fist columns and whenever I find it, I add the appropriate line id to the set of lines that produce that product.

  2. Reversely, for each line, what are the products that it can produce.

  3. For each (p,l) couple store the set of all need raw materials, to produce product p on l, the property of each raw material(coded as 1 if it's S and 0 otherwise) and the total price (I don't need individual prices).

Here is how I am doing it now:

def process(x, y, recipes_df):
    raw_materials = {}
    total_cost = 0
    for product, line, rm, rm_type, rm_price in \
    recipes_df[['product','line', 'rm','rm_type','rm_price']].values:
        if (x,y) == (product,line):
            total_cost += float(rm_price)
            raw_materials[rm] = 1 if rm_type == 'S' else 0
    return (raw_materials, total_cost)

lines_set = set(recipes_df['line'])
lines = []

rm_data = {}
products_set = set()
for line in lines_set:
    for row in recipes_df.itertuples(index=False):
        # if the line_id in this row correspond to line in the outer loop
        if row[1] == line:
            # extract the raw material information by using the process function.
            rm_data[row[0]] = process(row[0],row[1], recipes_df)

            # add the product to the set of products that can be manufactured on the line
            products_set.add(row[0])

            # add the informations to lines list
            lines.append((rm_data, products_set))

The file has more than 3000 lines, my approach takes a lot of time.

Observations: 0. There is no assumption about how the file is sorted, meaning that, I can find P0009 in line 1 and in line 3000, for example, with a lot of other products in between. Same remark for the lines. 1. The process function search in all the file every time it's cold for a couple (p,l), which may be inefficient 2. For every line in lines_set we browse all the file.

enter image description here

Question: How to do all of this more efficiently?

Edit : I did only 2. and 3., the 1. is very similar to 2.

Edit2: recipes_df is a pandas data frame

Edit3: The link to the data

\$\endgroup\$
  • 5
    \$\begingroup\$ Please provide a copy of the Dataframe as text, or parseable format (csv), not an image. Not very many people are going to type it in to test their code. \$\endgroup\$ – RootTwo Feb 10 at 6:19
6
\$\begingroup\$

In general if you have relational data in a list-like data structure, you want to convert it into a more appropriate data structure before you do anything tricky with it. I'm not sure what the type of recipes_df so I'm just going to copy your code that iterates over it and go from there.

from collections import defaultdict
from typing import Dict, List, Set, Tuple

# For each product, return where it can be produced.
product_lines: Dict[str, Set[str]] = defaultdict(set)

# For each line, what are the products that it can produce.
line_products: Dict[str, Set[str]] = defaultdict(set)

# For each (p,l) couple store the set of all need raw materials 
# to produce product p on l, the property of each raw material
# (coded as 1 if it's S and 0 otherwise), and the total price
class Recipe:
    def __init__(self):
        self.raw_materials: List[Tuple[str, int]] = []
        self.total_price = 0.0
recipes: Dict[Tuple[str, str], Recipe] = defaultdict(Recipe)

# Loop over recipes_df and populate all these structures.
for product, line, rm, rm_type, rm_price in \
        recipes_df[['product','line', 'rm','rm_type','rm_price']].values:
    product_lines[product].add(line)
    line_products[line].add(product)
    recipes[(product, line)].raw_materials.append((rm, 1 if rm_type == 'S' else 0))
    recipes[(product, line)].total_price += rm_price

At this point you've done a single pass through the entirety of recipes_df and you've completely populated the dictionaries that will let you find all the information you're looking for in constant time. From here you can convert those dictionaries into whatever other output format you need.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer! recipes_df is a pandas data frame \$\endgroup\$ – user218022 Feb 10 at 5:56
  • \$\begingroup\$ Why did you used a class for the recipe? What is the "intuition" behind, i.e what makes you think of using a class? \$\endgroup\$ – user218022 Feb 10 at 6:01
  • \$\begingroup\$ I want it to be a collection so I can have it as the value in a single dict, I want it to be well-typed (so a list is out, since all of a list's items are typed the same), and I want it to be mutable so I can build it as I iterate through the DF (so a tuple is out). That leaves a standard class as the easiest choice. \$\endgroup\$ – Samwise Feb 10 at 6:18
  • \$\begingroup\$ It's also convenient to be able to define a constructor that sets up both the empty list and the 0.0 value, and then pass that constructor to defaultdict. \$\endgroup\$ – Samwise Feb 10 at 6:21
3
\$\begingroup\$

Python is rather slow for iterations. If your data is in a pandas Dataframe, try to do things as vectorised as possible. You even iterate over the complete dataset for each row of your dataset, for each separate line. This is very inefficient.

If you need to iterate over all unique values of a column, and do operations on all relevant row, groupby is your friend. You can even group by 2 columns at the same time

from collections import defaultdict

lines2 = defaultdict(dict)
product_lines = defaultdict(set)
line_products = defaultdict(set)

for (product, line), data in recipes_df.groupby(["product", "line"]):

This sets up our data holders and starts iterating over the product, line combinations. A dict containing the lines as keys and the products that can be made on the line in a set, and vice versa. The lines2 is a dict with the line as key, and a seconds dict as value. This second dict has the product as key, and the extra info as values

    product_lines[product].add(line)
    line_products[line].add(product)

This second is now filled with the data in the group, so no need to iterate over the complete dataset for each row, but only the limited, relevant rows.

    lines2[line][product] = {
        "raw_materials": {
            row.rm: row.rm_type == "S" for row in data.itertuples()
        },
        "cost": data["rm_price_per_ton"].sum(),
    }
{'L2H175': {'P00004': {'raw_materials': {'RM00071': True,
    'RM00055': True,
    'RM00058': True,
    'RM00054': True,
    'RM00175': False,
    'RM00149': False,
    'RM00029': False,
    'RM00148': False,
    'RM00152': False,
    'RM00088': False,
    'RM00065': False,
    'RM00097': False},
   'cost': 62.02},
  'P00005': {'raw_materials': {'RM00030': True,
    'RM00055': True,
    'RM00058': True,
    'RM00054': True,
    'RM00175': False,
    'RM00029': False,
    'RM00149': False,
    'RM00152': False,
    'RM00088': False,
    'RM00064': False,
    'RM00097': False},
   'cost': 75.07},
   ...

Instead of 1 and 0, I use True and False as flag here, since that better expresses the boolean nature. If you need 1 and 0, you can surround the row.rm_type == 'S' with int(...)

Or you can work with some dict comprehensions:

product_lines = {
    line: set(data["product"].unique())
    for line, data in recipes_df.groupby(["line"])
}
line_products = {
    product: set(data["line"].unique())
    for product, data in recipes_df.groupby(["product"])
}

If you want a tuple as key, you can do:

lines3 = {
    (product, line): {
        "raw_materials": {
            row.rm: row.rm_type == "S" for row in data.itertuples()
        },
        "cost": data["rm_price_per_ton"].sum(),
    }
    for (product, line), data in recipes_df.groupby(["product", "line"])
}

If you want it nested, like lines2 you can do 2 nested groupbys

lines4 = {
    line: {
        product: {
            "raw_materials": {
                row.rm: row.rm_type == "S" for row in data.itertuples()
            },
            "cost": data["rm_price_per_ton"].sum(),
        }
        for product, data in line_data.groupby(["product"])
    }
    for line, line_data in recipes_df.groupby(["line"])
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Could you explain a little bit more on when to use goupby, If I am getting you right, it's useful when we have repetitions. Am I right? \$\endgroup\$ – user218022 Feb 10 at 21:45
1
\$\begingroup\$

Pass through the data just once, building up the desired data as you go:

import pandas as pd
import numpy as np

from collections import defaultdict

recipies_df = pd.read_csv('/home/mike/Downloads/recipes.csv', sep=';')

# maps products to the lines that can make it    
lines_by_product = defaultdict(set)

# maps lines to the products it can make
products_by_line = defaultdict(set)

# maps (product, line) to raw materials and cost
rms_by_product_line = defaultdict(lambda:[defaultdict(int),0])


for row in recipies_df.itertuples(index=False):
    lines_by_product[row.product].add(row.line)

    products_by_line[row.line].add(row.product)

    rms,cost = rms_by_product_line[row.product, row.line]
    rms[row.rm] = 1 if row.rm_type == 'S' else 0
    cost += float(row.rm_price_per_ton)
    rms_by_product_line[row.product, row.line] = rms,cost
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy