Building a Bill of Materials

I have this loop that builds a BOM but it is so slow as I scale it out to even modest data. All the data resides in two database tables. I am pulling the data in as list of lists and then iterating over them.

The orders table contains the product serial number and the top level root part numbers that are ordered for that serial number. The parts_h (hierarchy) table contains every parent - child relationship for every part defined where I work. I am trying to build one master table by marrying them together.

Here is some sample data:

order = [['ABC1200','1234567'],['ABC1300','1234567'],['ABC1400','2456693']]
# format is [serial number, top level part]

parts_h = [['1234567','3445678'],['3445678','5K9091'],['2456693','4J5689'],
             ['4J5689','09981'],['4J5689','09982'],['09981','2K5050']]
# format is [parent, child]

def bom_build(o,p):
    '''
    This function builds the bill of material for a serial number.
    It takes two inputs.
    1.  O which is a list of lists with each element of a list
    containing the serial number, root part number
    2. P which is a list of lists with each element of a list containing
    the parent part and child part as defined in Parts master
    '''

    bom=[]
    for product in o:
        for part in p:
            if product[1] == part[0]:
                # build first level of BOM
                bom.append([product[0],product[1],part[1],"/"+product[1]+"/"+part[1]])

    # build children
    for part in p:
        for row in bom:
            if row[2] == part[0]:
               bom.append([row[0],part[0],part[1],row[3]+"/"+part[1]])
        continue
    return bom

This is the output, which is correct but slow:

```
[['ABC1200', '1234567', '3445678', '/1234567/3445678'],
['ABC1300', '1234567', '3445678', '/1234567/3445678'],
['ABC1400', '2456693', '4J5689', '/2456693/4J5689'],
['ABC1200', '3445678', '5K9091', '/1234567/3445678/5K9091'],
['ABC1300', '3445678', '5K9091', '/1234567/3445678/5K9091'],
[

Some time is lost by having to traverse the p list for each product. For large data, you could preprocess the p list, and create a dict that is keyed by the part, and which provides a list of sub parts for it. Then the lookup for a given product will be faster.

Secondly, the second part of the code will find deeper nested parts, but will fail to find them all when the nesting is deeper.

Here is suggested improvement:

def bom_build(o,p):
    # Create a hash keyed by parts, providing their sub parts as list
    d = dict()
    for [part, subpart] in parts_h:
        if part in d:
            d[part].append(subpart)
        else:
            d[part] = [subpart]

    bom = []

    def recurse(bom, d, serial, part, path, required):
        if part in d:
            for subpart in d[part]:
                nextpath = path + '/' + subpart
                bom.append([serial, part, subpart, nextpath])
                recurse(bom, d, serial, subpart, nextpath, False)
        elif required: # when there are no sub parts
            bom.append([serial, part, None, path])

    for [serial, part] in order:
        recurse(bom, d, serial, part, part, True)

    return bom

See it run on repl.it

Alternative: Breadth First Search

As an alternative you could also use a BFS algorithm -- the first part is the same:

def bom_build_bfs(o,p):
    # Create a hash keyed by parts, providing their sub parts as list
    d = dict()
    for [part, subpart] in parts_h:
        if part in d:
            d[part].append(subpart)
        else:
            d[part] = [subpart]

    # add start elements to bom, which later will be removed
    bom = [[serial, None, part, part] for [serial, part] in order]
    i = 0
    # treat it as a queue, adding to it while looping
    while i < len(bom):
        [serial, parent, part, path] = bom[i]
        i += 1
        if part in d:
            for subpart in d[part]:
                bom.append([serial, part, subpart, path + '/' + subpart])
        elif i < len(order): # when there are no sub parts
            bom.append([serial, part, None, path])

    # return the part without the starter elements
    return bom[len(order):]

In my limited tests this ran slower than the DFS solution, but it might depend on how the input data is distributed and how deeply nested it is.

StackExchange Code Review Q#159484, answer score: 4