Normalisation of a dict of dicts

Question

actualarray = {
    'single_open_cost_1':{
        'cost_matrix': [
            {'a': 24,'b': 56,'c': 78},
            {'a': 3,'b': 98},
            {'a': 121,'b': 12121,'c': 12989121,'d':16171},
        ]
    },
    'single_open_cost_2':{
        'cost_matrix': [
            {'a': 123,'b': 1312,'c': 1231},
            {'a': 1011,'b': 1911},
            {'a': 1433,'b': 19829,'c': 1132,'d':1791},
        ]
    },
    'open_cost_1':{
        'cost_matrix': [
            34,
            56,
            98
        ]
    },
    'open_cost_2':{
        'cost_matrix': [
            1811,
            1211,
            1267
        ]
    }
}

I have code that works and is trying to effectively normalise everything in this dict of dicts by the values within it. For example, the cost_matrix of the dict single_open_cost_1 has every dict within it normalised to:

            {'a': 24-3/121-3,'b': 56-56/12121-56,'c': 78-78/12989121-78},
            {'a': 3-3/121-3,'b': 98-56/12121-56},
            {'a': 121-3/121-3,'b': 12121-56/12121-56,'c': 12989121-78/12989121-78,'d':16171-16171/16171-16171},#Note if division by zero I handle in the function below.

This is the output:

{
    'single_open_cost_2': {
        'cost_matrix': [
            {
                'a': 123,
                'c': 1231,
                'b': 1312
            },
            {
                'a': 1011,
                'b': 1911
            },
            {
                'a': 1433,
                'c': 1132,
                'b': 19829,
                'd': 1791
            }
        ],
        'normalised_matrix': [
            {
                'a': 0.0,
                'c': 1.0,
                'b': 0.0
            },
            {
                'a': 0.6778625954198473,
                'b': 0.03234865258951234
            },
            {
                'a': 1.0,
                'c': 0.0,
                'b': 1.0,
                'd': 1.0
            }
        ]
    },
    'single_open_cost_1': {
        'cost_matrix': [
            {
                'a': 24,
                'c': 78,
                'b': 56
            },
            {
                'a': 3,
                'b': 98
            },
            {
                'a': 121,
                'c': 12989121,
                'b': 12121,
                'd': 16171
            }
        ],
        'normalised_matrix': [
            {
                'a': 0.17796610169491525,
                'c': 0.0,
                'b': 0.0
            },
            {
                'a': 0.0,
                'b': 0.003481143804392872
            },
            {
                'a': 1.0,
                'c': 1.0,
                'b': 1.0,
                'd': 1.0
            }
        ]
    },
    'open_cost_2': {
        'cost_matrix': [
            1811,
            1211,
            1267
        ],
        'normalised_matrix': [
            1.0,
            0.0,
            0.09333333333333334
        ]
    },
    'open_cost_1': {
        'cost_matrix': [
            34,
            56,
            98
        ],
        'normalised_matrix': [
            0.0,
            0.34375,
            1.0
        ]
    }
}

Currently I achieve this by multiple looping of code:

def normalize(v0, v1, t):
    if v1-v0==0:
        return float(1)
    else:
        return float(t - v0) / float(v1 - v0)

dict_values= {}
array_values = {}

for outer_key,dict in actualarray.items():
    if outer_key.startswith("single"):
        dict_values[outer_key]= {}
        for inner_dict in dict['cost_matrix']:
            for key,value in inner_dict.items():
                if key not in dict_values[outer_key]:
                    dict_values[outer_key][key]= []
                dict_values[outer_key][key].append(value)
    else:
        array_values[outer_key]= []
        for value in dict['cost_matrix']:
            array_values[outer_key].append(value)

# print array_values
# print dict_values


for model,values in array_values.items():
    v_min, v_max = min(values), max(values)
    actualarray[model]['normalised_matrix'] = [normalize(v_min, v_max, item) for item in values]


for outer_key,main_dict in actualarray.items():
    if outer_key.startswith("single"):
        actualarray[outer_key]['normalised_matrix'] = []
        array_dict= dict_values[outer_key]
        for dict in main_dict['cost_matrix']:
            temp_dict = {}
            for key,value in dict.items():
                v_min, v_max = min(array_dict[key]), max(array_dict[key])
                temp_dict[key]=normalize(v_min, v_max, value)
            actualarray[outer_key]['normalised_matrix'].append(temp_dict)

print actualarray

However, in actual fact, within actualarray, for each of the single and the non-single cases, I have keys going up to single_open_cost_100, and the length of each cost_matrix is 15000, not 3 as below. Thus my code runs very slowly. How can I improve my code to automatically create these new normalised_matrix key value pairs within each dicts in my original dict of dicts?

Answer 1

It's confusing that your actualarray is not a list as one would expect, but is actually a dictionary. You would be better off dropping …array from the name and calling it something else, like costs.

So, you have a dictionary containing named dictionaries, each containing a 'cost_matrix'. Some of those 'cost_matrix' values are list of numbers, and others are lists of dictionaries. What makes the code hard to follow is that those two cases have completely different codepaths. The list-of-numbers cases is handled by the for outer_key,dict in actualarray.items(): else: and for model,values in array_values.items(): stanzas. The list-of-dictionaries case is handled by the for outer_key,dict in actualarray.items(): if: and for outer_key,main_dict in actualarray.items(): stanzas.

Since the goal is to normalize every item one way or another, I propose the following outline:

for name, value in costs.items():
    norm = normalize_dicts if name.startswith('single') else normalize_nums
    value['normalized_matrix'] = norm(value['cost_matrix'])

The trick to making the code elegant is to make liberal use of list comprehensions, dictionary comprehensions, and generator expressions. Here's what I came up with:

def apply_normalizations(costs):
    """Add a 'normalised_matrix' next to each 'cost_matrix' in the values of costs"""

    def min_max(lst):
        values = [v for v in lst if v is not None]
        return min(values), max(values)

    def normalize(v, least, most):
        return 1.0 if least == most else float(v - least) / (most - least)

    def normalize_nums(lst):
        span = min_max(lst)
        return [normalize(val, *span) for val in lst]

    def normalize_dicts(lst):
        keys = set.union(*(set(dic.iterkeys()) for dic in lst))
        spans = {key:min_max(dic.get(key) for dic in lst) for key in keys}
        return [
           {key: normalize(val, *spans[key]) for key, val in dic.iteritems()}
           for dic in lst
        ]

    for name, value in costs.items():
        norm = normalize_dicts if name.startswith('single') else normalize_nums
        value['normalised_matrix'] = norm(value['cost_matrix'])

It won't necessarily be much faster than your original code, though it may benefit from better cache locality. It's certainly clearer than the original code, in my opinion.