# Function figuring out which close-by value comes from which input value

I would like to optimize the below traceback function. This function is part of an elementary step of the program and is called a lot...

import numpy as np

def traceback(tuple_node, tuple_node_alt):
"""
Compute which value from tuple_node_alt comes from which value from tuple_node.
Return a dictionnary where the key are the values from tuple_node and the values are the idx at which
the value may be located in tuple_node_alt.
"""
# Compute the tolerances based on the node
tolerances = [0.1 if x <= 100 else 0.2 for x in tuple_node]

# Traceback
distance = dict()
alt_identification = dict()
for k, x in enumerate(tuple_node):
distance[k] = [abs(elt-1) for elt in [alt_x/x for alt_x in tuple_node_alt]]
alt_identification[x] = list(np.where([elt <= tolerances[k]+0.00001 for elt in distance[k]])[0])

# Controls the identification and corrects it
len_values = {key: len(val) for key, val in alt_identification.items()}

if all([x <= 1 for x in len_values.values()]):
return alt_identification
else:
for key, value in alt_identification.items():
if len(value) <= 1:
continue
else:
other_values = [val for k, val in alt_identification.items() if k != key]
if value in other_values:
continue
else:
for val in other_values:
set1 = set(value)
intersec = set1.intersection(set(val))
if len(intersec) == 0:
continue
else:
alt_identification[key] = [v for v in value if v not in intersec]

return alt_identification


The input is composed of 2 tuples which do not need to have the same size. e.g.

tuple_node = (40, 50, 60, 80)
tuple_node_alt = (87, 48, 59, 39)


The goal is to figure out which value from tuple_node_alt may come from which value from tuple_node. If the value from tuple_node_alt is within a 10% margin from a value from tuple_node, it is considered that it comes from this value.

e.g. 39 is within a 10% margin of 40. It comes from 40. This aprt is perform in the "Traceback" section, where a distance dictionnary is computed and where the idx are computed. With the example above, the output is:

Out[67]: {40: [3], 50: [1], 60: [2], 80: [0]}


However, because of a potential overlapping of the tolerance band, 3 scenarios exists:

Scenario 1: each value has been identified to one alternative value. That's the case above.

Scenario 2:

tuple_node = (40, 50, 60, 80)
tuple_node_alt = (42, 55, 54)


55 and 54 are both in the tolerance band of both 50 and 60. Thus, the output is:

Out[66]: {40: [0], 50: [1, 2], 60: [1, 2], 80: []}


Scenario 3:

tuple_node = (40, 50, 60)
tuple_node_alt = (42, 55, 59)


This is when the control part comes in play. With this input, alt_identification becomes: Out[66]: {40: [0], 50: [1], 60: [1, 2], 80: []}. However, the 55 can not come from 60 since 50 only has one possibility: 55. Thus, this number being already taken, the correct output which is provided through the control & correct section is:

Out[66]: {40: [0], 50: [1], 60: [2], 80: []}


I would really like to optimize this part and to make it a lot more quicker. At the moment, it takes:

# With an input which does not enter the control & correct part.
node = (40, 50, 60, 80)
node_alt = (39, 48, 59, 87)
%timeit traceback(node, node_alt)
22.6 µs ± 1.04 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# With an input which need correction
node = (40, 50, 60, 100)
node_alt = (42, 55, 59, 89)
%timeit traceback(node, node_alt)
28.1 µs ± 1.88 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


A couple of low-hanging fruit inefficiencies:

1. distance = dict(). The distance[k] value is computed in a loop, and only every used in the next statement of the loop. It does not need to be stored in a dictionary.
2. all([ ...list comprehension... ]): You are using list comprehension to build up a list, which you immediately pass to all(...). There is no need to actually create the list. Just use all(...list comprehension...).
3. set1 = set(value). This is inside a for val in other_values: loop, where value and set1 are not changed. Move the statement out of the for loop, to avoid recreating the same set each iteration.
4. len_values is only used in the afore mentioned all(...), and only the the values of len_values dictionary are used. As such, the len_value dictionary construction is also unnecessary, and the if statement can be written:

if all(len(val) <= 1 for val in alt_identification.values()):


Since you are returning alt_identification from the if statement, and after the if...else statement, you can invert the test, and remove one return statement:

if any(len(val) > 1 for val in alt_identification.values()):
for key, value in alt_identification.items():
# ... omitted for brevity ...

return alt_identification


Similarly, the two if condition: continue else: could be re-written if not condition:.

Other possible improvements:

• tolerances[k] is only used in next for k loop. The list can be removed and the calculations move into the loop.
• numpy is only used for a list(np.where([...])[0]) operation, which is fairly obfuscated. A simple list comprehension can be used instead.
• The values of alt_identification are of type list, and converted (repeatedly) into a set() in the "control & correct" code. They could be stored as set() to avoid repeated conversions.

Here is my rework of the code, with the changes based on above comments:

def traceback(tuple_node, tuple_node_alt):

def close_alternates(x):
tolerance = (0.1 if x <= 100 else 0.2) + 0.00001
return set( k for k, alt_x in enumerate(tuple_node_alt)
if abs(alt_x/x - 1) <= tolerance )

alt_identification = { x: close_alternates(x) for x in tuple_node }

if any(len(val) > 1 for val in alt_identification.values()):
for key, values in alt_identification.items():
if len(values) > 1:
other_values = [val for k, val in alt_identification.items() if k != key]
if values not in other_values:
for other in other_values:
alt_identification[key] -= other

return alt_identification


I'm getting up to a 2.8x speedup with the above code, on your test data set that require correction.