[Numpy-discussion] short circuit != ?

[Zachary Pincus]

This is silly: the structure of the python language prevents  
meaningful short-circuiting in the case of
np.any(a!=b)

While it's true that np.any itself may short-circuit, the 'a!=b'  
statement itself will be evaluated in its entirety before the result  
(a boolean array) is passed to np.any. This is just how python (like  
most other languages) works. This means that the big-O complexity  
isn't reduced any: all elements of a and b have to be examined. If any  
short-circuits, then at least all the elements don't need to be  
examined twice!

If performance actually matters here (unlikely?), a quick bit of  
cython code could do this easily enough in the simple case where a and  
b are the same shape (so no broadcasting required). Note that the  
below hard-codes the dtype also.

import cython
cimport numpy
import numpy

TYPE_T = numpy.int64_t
TYPE = numpy.int64

@cython.boundscheck(False)
def equal(a, b):
   cdef:
     numpy.ndarray[TYPE, ndim=1, negative_indices=False] a_flat =  
a.astype(TYPE).flatten()
     numpy.ndarray[TYPE, ndim=1, negative_indices=False] b_flat =  
b.astype(TYPE).flatten()
     unsigned int i, l
   assert a_flat.shape[0] == b_flat.shape[0]
   l = a_flat.shape[0]
   for i in range(l):
     if a_flat[i] != b_flat[i]:
       return False
   return True

Zach



On Oct 27, 2010, at 9:44 AM, Skipper Seabold wrote:

> On Wed, Oct 27, 2010 at 9:37 AM, Johann Cohen-Tanugi
> <cohen at lpta.in2p3.fr> wrote:
>>
>>
>> On 10/27/2010 03:31 PM, Neal Becker wrote:
>>> Johann Cohen-Tanugi wrote:
>>>
>>>
>>>> how about np.any(a!=b)  ??
>>>>
>>>> On 10/27/2010 12:25 PM, Neal Becker wrote:
>>>>
>>>>> Is there a way to get a short circuit != ?
>>>>>
>>>>> That is, compare 2 arrays but stop as soon as the first element
>>>>> comparison fails?
>>>>>
>>>>> I'm assuming that np.all (a != b) will _not_ do this, but will  
>>>>> first
>>>>> compare all elements.
>>>>>
>>>>> _______________________________________________
>>>>> NumPy-Discussion mailing list
>>>>> NumPy-Discussion at scipy.org
>>>>> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>>>>>
>>>>>
>>>>>
>>> I don't think that will do short ciruit, will it?  I think that  
>>> will compare
>>> each element, returning a bool array, then short-circuit eval that  
>>> bool
>>> array.
>>>
>>>
>> In [3]: a=np.array([2,3,
>>
>> In [4]: b=np.array([2,5,
>>
>> In [5]: np.any(a!=b)
>> Out[5]: True
>>
>> it does not return a bool array, it seems. I do not see how you would
>> "broadcast" the notion of "any".... along axes maybe?
>>
>
> Not definitive by any means, but
>
> In [28]: a = np.arange(1,10000000)
>
> In [29]: b = np.arange(1,10000000)
>
> In [30]: timeit np.any(a!=b)
> 10 loops, best of 3: 37.8 ms per loop
>
> In [31]: a[0] = 10.
>
> In [32]: timeit np.any(a!=b)
> 10 loops, best of 3: 24.7 ms per loop
>
> In [33]: a[0] = 1
>
> In [34]: a[-1] = 1
>
> In [35]: timeit np.any(a!=b)
> 10 loops, best of 3: 37.7 ms per loop
>
> It seems to at least take less time when the difference is at the
> "beginning," though I'm sure there could be exceptions.
>
> Skipper
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion