Какой быстрый и эффективный подход к большим битовым полям с Python и numpy? - PullRequest
Новая
       76

Какой быстрый и эффективный подход к большим битовым полям с Python и numpy?

1 голос
/ 09 июля 2020

Я хотел бы использовать компактное и быстрое большое битовое поле в Python, в идеале без каких-либо зависимостей, кроме numpy. Операции, которые я хотел бы, были бы примерно эквивалентны: 

bits = new_bitfield(3000000)  # 3 million bits
bits.set_bit(n, 1)
bits.set_bit(n, 0)
bits.get_bit(n)

Я бы хотел, чтобы базовое хранилище для битов было очень сжатым / с низким уровнем накладных расходов. (В идеале, этот bits объект будет занимать всего лишь чуть больше 366,21 Кибибайта.)

Я бы хотел, чтобы операции получения и установки были очень быстрыми, с минимумом проверки типов / типов. принуждение накладных расходов - возможно, даже особенно быстро при использовании кода Cython- или Numba- c (или их соответствующих параметров встраивания).

Какой лучший способ приблизиться к C скорости / компактности, сохраняя при этом как Pythoni c внешний вид насколько это возможно?

1 Ответ

1 голос
/ 09 июля 2020

Развернуть его самостоятельно не должно быть слишком сложно, другой вариант - использовать существующие реализации. Хорошо это или плохо, но std::vector<bool> - это именно то, что вам нужно: он использует ровно 1 бит на значение (таким образом, параметр bool -template несколько вводит в заблуждение, поскольку bool имеет длину не менее 1 байта).

Используя Cython, это может выглядеть примерно так (оно скомпилировано как расширение c ++): 

%%cython -+
from libcpp.vector cimport vector
from libcpp cimport bool

cdef class Bitset:
    cdef vector[bool] bset;
    
    def __cinit__(self, size_t size):
        self.bset.resize(size, False);
        
    cpdef void set_bit(self, size_t pos, bint val) except *:        
        # self.bset[pos] = val would not check out of range
        # self.bset.at(pos) = val doesn't work with Cython
        if pos < self.bset.size():
            self.bset[pos] = val;
        else:
            raise IndexError("out of range access")    
            
    cpdef bint get_bit(self, size_t pos):
        return self.bset.at(pos)

Что может использоваться как 

mybitset = Bitset(10)
mybitset.set_bit(2, True)
mybitset.get_bit(1), mybitset.get_bit(2) #returns (False, True)

Также 

mybitset.set_bit(11, True) #throws
mybitset.get_bit(12, True) #throws

throw и не завершаться неопределенным поведением.

Очевидно, что для минимизации накладных расходов код, использующий Bitset -cdef-class, также должен быть написан на Cython, поэтому cdef -часть интерфейса может быть использована без необходимости преобразования в Python -объект, который необходим для Python -части интерфейса (как показано выше).

...