Python: Самый быстрый способ упаковки двухмерного массива двоичных значений в массив UINT64 - PullRequest
Новая
       35

Python: Самый быстрый способ упаковки двухмерного массива двоичных значений в массив UINT64

2 голосов
/ 07 февраля 2020

У меня есть 2D UINT8 numpy массив размером (149797, 64) . Каждый из элементов имеет значение 0 или 1. Я хочу упаковать эти двоичные значения в каждой строке в значение UINT64 , чтобы в результате я получил массив UINT64 формы 149797. Я попробовал следующий код с использованием функции numpy bitpack. 

test = np.random.randint(0, 2, (149797, 64),dtype=np.uint8)
col_pack=np.packbits(test.reshape(-1, 8, 8)[:, ::-1]).view(np.uint64)

Для выполнения функции packbits требуется около 10 мс . Простое изменение формы самого этого массива, похоже, занимает около 7 мс . Я также попытался перебрать массив 2d numpy, используя операции сдвига для достижения того же результата; но не было никакого улучшения скорости.

Наконец, я также хочу скомпилировать его, используя numba для процессора. 

@njit
def shifting(bitlist):
    x=np.zeros(149797,dtype=np.uint64)  #54
    rows,cols=bitlist.shape
    for i in range(0,rows):             #56
      out=0
      for bit in range(0,cols):
         out = (out << 1) | bitlist[i][bit] # If i comment out bitlist, time=190 microsec
      x[i]=np.uint64(out)  # Reduces time to microseconds if line is commented in njit
    return x

Это занимает около 6 мс используя njit .

Вот параллельная версия njit 

@njit(parallel=True)
def shifting(bitlist): 
    rows,cols=149797,64
    out=0
    z=np.zeros(rows,dtype=np.uint64)
    for i in prange(rows):
      for bit in range(cols):
         z[i] = (z[i] * 2) + bitlist[i,bit] # Time becomes 100 micro if i use 'out' instead of 'z[i] array'

    return z

Это немного лучше с 3,24 мс время выполнения (google colab dual core 2.2Ghz) В настоящее время лучшим решением является решение python с swapbytes (Paul's) , то есть 1,74 мс .

Как мы можем ускорить процесс это преобразование? Есть ли возможность использовать векторизацию (или распараллеливание), bitarrays et c, для достижения ускорения?

Ref: numpy packbits pack в массив uint16

На 12-ядерном компьютере (процессор Intel Xeon® R E5-1650 v2 @ 3,50 ГГц),

метод Паулса: 1595,0 микросекунд (это делает я полагаю, не использовать многоядерный)

Код Numba: 146.0 микросекунд (вышеупомянутая параллельная-numba)

т.е. около 10-кратного ускорения !!!

Ответы [ 2 ]

2 голосов
/ 08 февраля 2020

Вы можете получить значительное ускорение, используя byteswap вместо изменения формы et c.: 

test = np.random.randint(0, 2, (149797, 64),dtype=np.uint8)

np.packbits(test.reshape(-1, 8, 8)[:, ::-1]).view(np.uint64)
# array([ 1079982015491401631,   246233595099746297, 16216705265283876830,
#        ...,  1943876987915462704, 14189483758685514703,
       12753669247696755125], dtype=uint64)
np.packbits(test).view(np.uint64).byteswap()
# array([ 1079982015491401631,   246233595099746297, 16216705265283876830,
#        ...,  1943876987915462704, 14189483758685514703,
       12753669247696755125], dtype=uint64)

timeit(lambda:np.packbits(test.reshape(-1, 8, 8)[:, ::-1]).view(np.uint64),number=100)
# 1.1054180909413844

timeit(lambda:np.packbits(test).view(np.uint64).byteswap(),number=100)
# 0.18370431219227612
1 голос
/ 09 февраля 2020

Немного решения Numba (версия 0.46 / Windows).

Код 

import numpy as np
import numba as nb

#with memory allocation
@nb.njit(parallel=True)
def shifting(bitlist):
    assert bitlist.shape[1]==64
    x=np.empty(bitlist.shape[0],dtype=np.uint64)

    for i in nb.prange(bitlist.shape[0]):
        out=np.uint64(0)
        for bit in range(bitlist.shape[1]):
            out = (out << 1) | bitlist[i,bit] 
        x[i]=out
    return x

#without memory allocation
@nb.njit(parallel=True)
def shifting_2(bitlist,x):
    assert bitlist.shape[1]==64

    for i in nb.prange(bitlist.shape[0]):
        out=np.uint64(0)
        for bit in range(bitlist.shape[1]):
            out = (out << 1) | bitlist[i,bit] 
        x[i]=out
    return x

Время 

test = np.random.randint(0, 2, (149797, 64),dtype=np.uint8)

#If you call this function multiple times, only allocating memory 
#once may be enough
x=np.empty(test.shape[0],dtype=np.uint64)

#Warmup first call takes significantly longer
res=shifting(test)
res=shifting_2(test,x)

%timeit res=shifting(test)
#976 µs ± 41.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit res=shifting_2(test,x)
#764 µs ± 63 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit np.packbits(test).view(np.uint64).byteswap()
#8.07 ms ± 52.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit np.packbits(test.reshape(-1, 8, 8)[:, ::-1]).view(np.uint64)
#17.9 ms ± 91 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
...