Numpy normalization code is strangely slow

Question

I'm putting together some basic python code that takes in a dictionary of labels mapped to lists of matrices (the matrices represent categorized images), I'm just trying to subtract the average image from everything and then center the data on a 0 - 1 scale. For some reason this code seems to run awkwardly slow. When iterating over just 500 48x48 images it takes about 10 second to run, which won't really scale to the number of images I'm working with. After looking at the cProfile results it looks like most of the time is spent in the _center function.

I feel like I'm probably not using numpy to its fullest here and was wondering if someone more experienced than myself had some tricks to speed this up some, or could point out something silly that I'm doing here. Code posted below:

def __init__(self, master_dict, normalization = lambda x: math.exp(x)):
    """
    master_dict should be a dictionary mapping classes to lists of matrices

    example = {
        "cats": [[[]...], [[]...]...],
        "dogs": [[[]...], [[]...]...]
    }

    have to be python lists, not numpy arrays

    normalization represents the 0-1 normalization scheme used. Defaults to simple linear
    """
    normalization = np.vectorize(normalization)
    full_tensor = np.array(reduce(operator.add, master_dict.values()))
    centering = np.sum(np.array(reduce(operator.add, master_dict.values())), axis=0)/len(full_tensor)
    self.data = {key: self._center(np.array(value), centering, normalization) for key,value in master_dict.items()}
    self.normalization = normalization

def _center(self, list_of_arrays, centering_factor, normalization_scheme):
    """
    Centering scheme for arrays
    """
    arrays = list_of_arrays - centering_factor
    normalize = lambda a: (a - np.min(a)) / (np.max(a) - np.min(a))
    return normalization_scheme([normalize(array) for array in arrays])

Also, before you ask, I don't have a huge amount of control over the input format, but I could probably figure something out if that were really the limiting factor here.

Answer 1

Starting with @sethMMorton's changes, I was able to gain nearly another factor of two in speed. Mainly from vectorizing your normalize function (inside of _center), so that you can call _center on the entire list_of_arrays instead of just putting it inside a list comprehension. This also gets rid of an extra conversion from numpy array to list and back.

def normalize(a):
    a -= a.min(1, keepdims=True).min(2, keepdims=True)
    a /= a.max(1, keepdims=True).max(2, keepdims=True)
    return a

Note, I wouldn't define normalize inside of the _center call, but leave it separate as shown in this answer. So then, in _center, just call normalize on the entire list_of_arrays:

def _center(self, list_of_arrays, centering_factor, normalization_scheme):
    """
    Centering scheme for arrays
    """
    list_of_arrays -= centering_factor
    return normalization_scheme(normalize(list_of_arrays))

In fact, you could call normalize and _center on the entire full_tensor at the very beginning, and never have to loop through, but the tricky part is splitting it back up into the dict of lists of arrays again. I'll work on that next :P

---

As mentioned in my comment, you can replace:

full_tensor = np.array(reduce(operator.add, master_dict.values()))

with

full_tensor = np.concatenate(master_dict.values())

which may not be faster, but it's more clear and the standard way to do it.

In the end, here are the timings:

>>> timeit slater_init(example)
1 loops, best of 3: 1.42 s per loop

>>> timeit seth_init(example)
1 loops, best of 3: 489 ms per loop

>>> timeit my_init(example)
1 loops, best of 3: 281 ms per loop

Below is my full code for timing. Note that I replaced self.data = ... with return ... so that I could save and compare the outputs to make sure all our code does returns the same data :) Of course, you should test your version against mine as well!

import operator
import math
import numpy as np

#example dict has N keys (integers), each value is a list of n random HxW 'arrays', in list form:
test_shape = 10, 2, 4, 4          # small example for testing
timing_shape = 100, 5, 48, 48     # bigger example for timing
N, n, H, W = timing_shape
example = dict(enumerate(np.random.rand(N, n, H, W).tolist()))

def my_init(master_dict, normalization=np.exp):
    full_tensor = np.concatenate(master_dict.values())
    centering = np.mean(full_tensor, 0)
    return {key: my_center(np.array(value), centering, normalization)
                     for key,value in master_dict.iteritems()} #use iteritems here
    #self.normalization = normalization

def my_normalize(a):
    a -= a.min(1, keepdims=True).min(2, keepdims=True)
    a /= a.max(1, keepdims=True).max(2, keepdims=True)
    return a

def my_center(arrays, centering_factor, normalization_scheme):
    """
    Centering scheme for arrays
    """
    arrays -= centering_factor
    return normalization_scheme(my_normalize(arrays))

#### sethMMorton's original improvement ####

def seth_init(master_dict, normalization = np.exp):
    """
    master_dict should be a dictionary mapping classes to lists of matrices

    example = {
        "cats": [[[]...], [[]...]...],
        "dogs": [[[]...], [[]...]...]
    }

    have to be python lists, not numpy arrays

    normalization represents the 0-1 normalization scheme used. Defaults to simple linear
    """
    full_tensor = np.array(reduce(operator.add, master_dict.values()))
    centering = np.sum(full_tensor, axis=0)/len(full_tensor)
    return {key: seth_center(np.array(value), centering, normalization) for key,value in master_dict.items()}
    #self.normalization = normalization

def seth_center(list_of_arrays, centering_factor, normalization_scheme):
    """
    Centering scheme for arrays
    """
    def seth_normalize(a):
        a_min = np.min(a)
        return (a - a_min) / (np.max(a) - a_min)
    arrays = list_of_arrays - centering_factor
    return normalization_scheme([seth_normalize(array) for array in arrays])

#### Original code, by slater ####

def slater_init(master_dict, normalization = lambda x: math.exp(x)):
    """
    master_dict should be a dictionary mapping classes to lists of matrices

    example = {
        "cats": [[[]...], [[]...]...],
        "dogs": [[[]...], [[]...]...]
    }

    have to be python lists, not numpy arrays

    normalization represents the 0-1 normalization scheme used. Defaults to simple linear
    """
    normalization = np.vectorize(normalization)
    full_tensor = np.array(reduce(operator.add, master_dict.values()))
    centering = np.sum(np.array(reduce(operator.add, master_dict.values())), axis=0)/len(full_tensor)
    return {key: slater_center(np.array(value), centering, normalization) for key,value in master_dict.items()}
    #self.normalization = normalization

def slater_center(list_of_arrays, centering_factor, normalization_scheme):
    """
    Centering scheme for arrays
    """
    arrays = list_of_arrays - centering_factor
    slater_normalize = lambda a: (a - np.min(a)) / (np.max(a) - np.min(a))
    return normalization_scheme([slater_normalize(array) for array in arrays])

Answer 2

In addition to the math.exp -> np.exp suggestion that seemed to work, I also suggest a few other modifications. First, you are doing the calculation np.array(reduce(operator.add, master_dict.values())) twice, so in the rework below I suggest reusing the data instead of doing the work twice. Second, I modified your normalize lambda to be a proper function so that you can pre-calculate the min of the array. This saves calculating that twice.

def __init__(self, master_dict, normalization = np.exp):
    """
    master_dict should be a dictionary mapping classes to lists of matrices

    example = {
        "cats": [[[]...], [[]...]...],
        "dogs": [[[]...], [[]...]...]
    }

    have to be python lists, not numpy arrays

    normalization represents the 0-1 normalization scheme used. Defaults to simple linear
    """
    full_tensor = np.array(reduce(operator.add, master_dict.values()))
    centering = np.sum(full_tensor, axis=0)/len(full_tensor)
    self.data = {key: self._center(np.array(value), centering, normalization) for key,value in master_dict.items()}
    self.normalization = normalization

def _center(self, list_of_arrays, centering_factor, normalization_scheme):
    """
    Centering scheme for arrays
    """
    def normalize(a):
        a_min = np.min(a)
        return (a - a_min) / (np.max(a) - a_min)
    arrays = list_of_arrays - centering_factor
    return normalization_scheme([normalize(array) for array in arrays])

I regards to your comment about needing to do python specific things so you can't convert to arrays before manipulating the data, there is nothing stopping you from calling (for example) reduce on a numpy array. Numpy arrays are iterable, so anywhere you would use a list you can use a numpy array (OK, not anywhere, but in most cases). However, I have not completely familiarized myself with your algorithm and maybe this case is one of the exceptions.