Сравнение между numpy.all и побитовым '&' для двоичной последовательности

Question

У меня проблема с выполнением побитового '&' между двумя большими двоичными последовательностями одинаковой длины, и мне нужно найти индексы, где появляются цифры 1.

Я использовал numpy, чтобы сделать это, и вотмой код:

>>> c = numpy.array([[0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1]]) #initialize 2d array
>>> c = c.all(axis=0)
>>> d = numpy.where(c)[False] #returns indices

Я проверил время для этого.

>>> print("Time taken to perform 'numpy.all' : ",timeit.timeit(lambda :c.all(axis=0),number=10000))
>>> Time taken to perform 'numpy.all' :  0.01454929300234653

Эта операция была медленнее, чем я ожидал.

Затем, для сравнения, я выполнил базовую побитовую операцию '&':

>>> print("Time taken to perform bitwise & :",timeit.timeit('a = 0b0000000001111111111100000001111111111; b = 0b0000000001111111111100000001111111111; c = a&b',number=10000))

>>> Time taken to perform bitwise & : 0.0004252859980624635

Это намного быстрее, чем numpy

Я использую numpy, потому что это позволяетчтобы найти индексы там, где у него 1, но оператор numpy.all намного медленнее.

Мои исходные данные будут списком массивов, как в первом случае.Будет ли повторение, если я преобразую этот список в двоичное число, а затем выполню вычисления, как во втором случае?

Answer 1

Фактор, который вы наблюдаете, является прямым следствием того факта, что c=numpy.array([[0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1]]) является массивом на int, а int кодируется в 32 битах

, поэтому, когда вы переходите в c.all (), вывыполняем операцию на 37 * 32 = 1184 битах

Однако a = 0b0000000001111111111100000001111111111 состоит из 37 битов, поэтому при выполнении a&b операция выполняется на 37 битах.

, поэтому вы делаетечто-то в 32 раза дороже с массивом numpy.

Давайте проверим, что

import timeit
import numpy as np
print("Time taken to perform bitwise & :",timeit.timeit('a=0b0000000001111111111100000001111111111; b = 0b0000000001111111111100000001111111111; c = a&b',number=320000))
a = 0b0000000001111111111100000001111111111
b = 0b0000000001111111111100000001111111111
c=np.array([a,b])
print("Time taken to perform 'numpy.all' : ",timeit.timeit(lambda :c.all(axis=0),number=10000))

операцию & я выполняю 320000 раз, а операцию all() - 10000 раз.

Time taken to perform bitwise & : 0.01527938833025152
Time taken to perform 'numpy.all' :  0.01583387375572265

Это то же самое!

Теперь вернемся к исходной проблеме, вы хотите знать индексы, где биты равны 1 в большом двоичном числе.

Возможно, вы могли бы попробоватьвещи, предоставляемые модулем bitarray

a = bitarray.bitarray('0000000001111111111100000001111111111')
b = bitarray.bitarray('0000000001111111111100000001111111111')
i=0
data = list()
for c in a&b:
    if(c):
        data.append(i)
    i=i+1
print (data)

выходы

[9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]

Answer 2

Я не думаю, что вы можете превзойти скорость a&b (фактические вычисления - это просто набор элементарных операций ЦП, я уверен, что результат ваших timeit -> 99% накладных расходов).Например:

>>> from timeit import timeit
>>> import numpy as np
>>> import random
>>> 
>>> k = 2**17-2
>>> a = random.randint(0, 2**k-1) + 2**k
>>> b = random.randint(0, 2**k-1) + 2**k
>>> timeit('a & b', globals=globals())
2.520026927930303

Это> 100 тыс. Бит и занимает всего ~ 2,5 мкс.

В любом случае стоимость & будет меньше стоимости генерации списка или массива.индексов.

numpy идет со значительными накладными расходами, поэтому для такой простой операции, как ваша, нужно проверить, стоит ли она того.

Итак, давайте сначала попробуем чисто Python-решение:

>>> c = a & b
>>> timeit("[x for x, y in enumerate(bin(c), -2) if y=='1']", globals=globals(), number=1000)
7.905808186973445

Это ~ 8 мс и, как и ожидалось, на несколько порядков больше, чем операция &.

Како numpy?

Давайте сначала переместим понимание списка:

>>> timeit("np.where(np.fromstring(bin(c), np.uint8)[2:] - ord('0'))[0]", globals=globals(), number=1000)
1.0363857130287215

Так что в этом случае мы получаем ~ 8-кратное ускорение.Это сокращается в ~ 4 раза, если мы требуем, чтобы результат был списком:

>>> timeit("np.where(np.fromstring(bin(c), np.uint8)[2:] - ord('0'))[0].tolist()", globals=globals(), number=1000)
1.9008758360287175

Мы также можем позволить numpy выполнять двоичное преобразование, что дает еще одно небольшое ускорение:

>>> timeit("np.where(np.unpackbits(np.frombuffer(c.to_bytes(k//8+1, 'big'), np.uint8))[1:])[0]", globals=globals(), number=1000)
0.869781385990791

В итоге:

• numpy не всегда быстрее, лучше оставить & для чистого Python
• поиск ненулевых битов кажется достаточно быстрым в numpy, чтобы компенсировать стоимость преобразования между спискамии массив

Обратите внимание, что все это идет с оговоркой, что мой чистый код Python не обязательно является оптимальным.Например, используя таблицу поиска, мы можем получить немного быстрее:

>>> lookup = [(np.where(i)[0]-1).tolist() for i in np.ndindex(*8*[2])]
>>> timeit("[(x<<3) + z for x, y in enumerate(c.to_bytes(k//8+1, 'big')) for z in lookup[y]]", globals=globals(), number=1000)
4.687953414046206

Answer 3

>>> c = numpy.random.randint(2, size=(2, 40)) #initialize
>>> c
array([[1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1,
        0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0],
       [1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
        0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1]])

Доступ к этому дает два замедления:

• Вам необходимо получить доступ к двум строкам, тогда как в вашем побитовом тесте константы легко доступны в регистрах.
• Вы выполняете серию из 40 and операций, которые могут включать в себя приведение от полного целого к логическому.

Вы серьезно затруднили тест all;результат не является сюрпризом (больше).