Numpy: Replacing values in a 2D array efficiently using a dictionary as a map

Question

I have a 2D Numpy array of integers like so:

a = np.array([[  3,   0,   2,  -1],
              [  1, 255,   1,   2],
              [  0,   3,   2,   2]])

and I have a dictionary with integer keys and values that I would like to use to replace the values of a with new values. The dict might look like this:

d = {0: 1, 1: 2, 2: 3, 3: 4, -1: 0, 255: 0}

I want to replace the values of a that match a key in d with the corresponding value in d. In other words, d defines a map between old (current) and new (desired) values in a. The outcome for the toy example above would be this:

a_new = np.array([[  4,   1,   3,   0],
                  [  2,   0,   2,   3],
                  [  1,   4,   3,   3]])

What would be an efficient way to implement this?

This is a toy example, but in practice the array will be large, its shape will be e.g. (1024, 2048), and the dictionary will have on the order of dozens of elements (34 in my case), and while the keys are integers, they are not necessarily all consecutive and they can be negative (like in the example above).

I need to perform this replacement on hundreds of thousands of such arrays, so it needs to be fast. However, the dictionary is known in advance and remains constant, so asymptotically, any time used to modify the dictionary or transform it into a more appropriate data structure doesn't matter.

I'm currently looping over the array entries in two nested for loops (over the rows and columns of a), but there has got to be a better way.

If the map didn't contain negative values (e.g. -1 like in the example), I would just create a list or an array from the dictionary once where the keys are the array indices and then use that for an efficient Numpy fancy indexing routine. But since there are negative values, too, this won't work.

Answer 1

Make a copy of the array then iterate over the dictionary items then use boolean indexing to assign the new values to the copy.

import numpy as np
b = np.copy(a)
for old, new in d.items():
    b[a == old] = new

Answer 2

Here's one way, provided you have a small dictionary/min and max values, this may be more efficient, you work around the negative index by adding the array min:

In [11]: indexer = np.array([d.get(i, -1) for i in range(a.min(), a.max() + 1)])

In [12]: indexer[(a - a.min())]
Out[12]:
array([[4, 1, 3, 0],
       [2, 0, 2, 3],
       [1, 4, 3, 3]])

Note: This moves the for loop to the lookup table, but if this is significantly smaller than the actual array this could be a lot faster.

Answer 3

This post solves for one-to-one mapping case between array and dictionary keys. The idea would be similar to proposed in @Andy Hayden's smart solution, but we will create a bigger array that incorporates Python's negative indexing thereby giving us the efficiency of simply indexing without any offsetting needed for incoming input arrays, which should be the noticeable improvement here.

To get the indexer, which would be a one-time usage as the dictionary stays the same, use this -

def getval_array(d):
    v = np.array(list(d.values()))
    k = np.array(list(d.keys()))
    maxv = k.max()
    minv = k.min()
    n = maxv - minv + 1
    val = np.empty(n,dtype=v.dtype)
    val[k] = v
    return val

val_arr = getval_array(d)

To get the final replacements, simply index. So, for an input array a, do -

out = val_arr[a]

Sample run -

In [8]: a = np.array([[  3,   0,   2,  -1],
   ...:               [  1, 255,   1, -16],
   ...:               [  0,   3,   2,   2]])
   ...: 
   ...: d = {0: 1, 1: 2, 2: 3, 3: 4, -1: 0, 255: 0, -16:5}
   ...: 

In [9]: val_arr = getval_array(d) # one-time operation

In [10]: val_arr[a]
Out[10]: 
array([[4, 1, 3, 0],
       [2, 0, 2, 5],
       [1, 4, 3, 3]])

Runtime test on tiled sample data -

In [141]: a = np.array([[  3,   0,   2,  -1],
     ...:               [  1, 255,   1, -16],
     ...:               [  0,   3,   2,   2]])
     ...: 
     ...: d = {0: 1, 1: 2, 2: 3, 3: 4, -1: 10, 255: 89, -16:5}
     ...: 

In [142]: a = np.random.choice(a.ravel(), 1024*2048).reshape(1024,2048)

# @Andy Hayden's soln
In [143]: indexer = np.array([d.get(i, -1) for i in range(a.min(), a.max() + 1)])

In [144]: %timeit indexer[(a - a.min())]
100 loops, best of 3: 8.34 ms per loop

# Proposed in this post
In [145]: val_arr = getval_array(d)

In [146]: %timeit val_arr[a]
100 loops, best of 3: 2.69 ms per loop

Answer 4

Numpy can create vectorized functions for performing mapping operations on arrays. I'm not sure which method here is going to have the best performance, so I've timed my approach with timeit. I would recommend trying out a couple of the other approached provided if you want to figure out what has the best performance.

# Function to be vectorized
def map_func(val, dictionary):
    return dictionary[val] if val in dictionary else val 

# Vectorize map_func
vfunc  = np.vectorize(map_func)

# Run
print(vfunc(a, d))

You can time this by doing:

from timeit import Timer
t = Timer('vfunc(a, d)', 'from __main__ import a, d, vfunc')
print(t.timeit(number=1000))

My result for this approach was about 0.014 s.

Edit: For kicks, I tried this out on (1024, 2048) size numpy array of random numbers from -10 to 10, with your same dictionary. It took about a quarter of a second for a single array. Unless you are running a lot of these arrays, it may not really be worth optimizing if that's an acceptable level of performance.

Answer 5

Another option, haven't benchmarked it:

    def replace_values(src: np.ndarray, new_by_old: Dict[int,int]) -> np.ndarray:
        dst = np.empty_like(src)
        for x in np.unique(src):
            dst[src==x] = new_by_old[x]
        return dst

This is similar to https://stackoverflow.com/a/46868897/2135504, but should be a bit faster due to

• using np.empty_like() instead of np.copy()
• using np.unique(src) instead of new_by_old.keys()