# 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'],
['ABC1400', '4J5689', '09981', '/2456693/4J5689/09981'],
['ABC1400', '4J5689', '09982', '/2456693/4J5689/09982'],
['ABC1400', '09981', '2K5050', '/2456693/4J5689/09981']]


I'm then going to write this to an Impala table.

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

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.

• Thank you, this is significantly faster! Is it possible to parallelize this code? It is an order of magnitude faster when I ran it on my production data, however it still takes 5-8 seconds per serial number to build the list. I'm just wondering how much more I can expect to gain. Thank you for the help! – travBoog Apr 3 '17 at 16:11
• I added a BFS alternative, but it depends on your data whether that will bring any gain. In fact on the small sample data it performs a tad slower. I think the code is indeed a good candidate for parallel programming, but unfortunately I have no experience with it. – trincot Apr 3 '17 at 17:09
• Thank you for your help. In my testing the BFS was consistently ~ 40-50 percent slower than your original post. – travBoog Apr 3 '17 at 19:19

The continue as the last statement of the for loop is pointless. You should remove it.