CODEWITHSUNDEEP
pythonnumpyreduce
tbjohnston
tbjohnston

Reputation: 41

Can this double list comprehension go straight into an array (Is there a more Pythonic way?)

My goal is to write a function that performs modulo-2 multiplication of two arrays (multiplication = and, addition = xor). Here is the code I have now. Any suggestions about how to improve this gratefully received - in particular, should I / how can I have the list comprehension go straight into an array of the appropriate shape?

import numpy as np
import operator

def m2mult(a,b):

    c = np.ndarray([reduce(operator.xor, np.logical_and(a[x,:],b[:,y]))
         for x in range(0,a.shape[0]) for y in range (0, b.shape[1])])
    c.shape = (a.shape[0], b.shape[1])

    return c

Upvotes: 4

Views: 219

Answers (2)

tzelleke
tzelleke

Reputation: 15345

You can just do common matrix multiplication on ints, followed by modulo-2 reduction and then convert back to bool:

np.mod(np.dot(a.astype('u1'), b), 2).astype('bool')

It is faster than seberg's solution and Jaime's modification to it.

+---------------+---------+-----------+----------+
|               |  10x10  | 1000x1000 | 750x1250 |
+---------------+---------+-----------+----------+
| m2mult_tz     | 33 us   | 7.27 s    | 4.68 s   |
| m2mult_jaime  | 56.7 us | 20.4 s    | 14.2 s   |
| m2mult_seberg | 62.9 us | 20.5 s    | 14.3 s   |
+---------------+---------+-----------+----------+

This might be an issue for really large arrays or if your program does this operation a lot.
I timed this approach and the solutions of seberg and the modification to it suggested by Jaime.
Here's how I implemented the different functions:

import numpy as np

def create_ab(n, m):
    a = np.random.randint(0, 2, (n, m)).astype(bool)
    b = np.random.randint(0, 2, (m, n)).astype(bool)
    return a, b


def m2mult_tz(a, b):
    return np.mod(np.dot(a.astype('u1'), b), 2).astype(bool)


def m2mult_seberg(a, b):
    return np.logical_xor.reduce(
                np.logical_and(a[:,None,:], b.T[None,:,:]),
                axis=-1)


def m2mult_jaime(a, b):
    return np.logical_xor.reduce(
                np.logical_and(a[:, :, None], b),
                axis=1)

Here' a record of the 1000x1000 timings (I also checked that results are the same in all cases):

In [19]: a, b = create_ab(1000, 1000)

In [20]: timeit m2mult_tz(a, b)
1 loops, best of 3: 7.27 s per loop

In [21]: timeit m2mult_jaime(a, b)
1 loops, best of 3: 20.4 s per loop

In [22]: timeit m2mult_seberg(a, b)
1 loops, best of 3: 20.5 s per loop

In [23]: r_tz = m2mult_tz(a, b)

In [24]: r_jaime = m2mult_jaime(a, b)

In [25]: r_seberg = m2mult_seberg(a, b)

In [26]: np.all(r_tz == r_jaime)
Out[26]: True

In [27]: np.all(r_tz == r_seberg)
Out[27]: True

Upvotes: 2

seberg
seberg

Reputation: 8975

You shouldn't do it like that at all:

a = np.random.randint(0,2,(4,4))
b = np.random.randint(0,2,(4,4))

# Now note that this is true:
# (I will let you figure that out, its a lot of neat broadcasting.
# b.T would be enough as well, because of it)
np.multiply(a[:,None,:], b.T[None,:,:]).sum(-1) == np.dot(a,b)
# note also that .sum(-1) is the same as np.add.reduce(array, axis=-1)

# now we can do the same thing for your logical operations:
a = np.random.randint(0,2,(4,4)).astype(bool)
b = np.random.randint(0,2,(4,4)).astype(bool)

def m2mult(a, b):
    mult = np.logical_and(a[:,None,:], b.T[None,:,:])
    return np.logical_xor.reduce(mult, axis=-1)

And its fully vectorized, much faster and just numpy!

Upvotes: 4

Related Questions