Недостаточно памяти в Cython

Question

Я пытаюсь реализовать алгоритм на Cython. Но у меня не хватает памяти на моей BitSet реализации. Я понятия не имею, почему, вот полезные снимки моего кода.

bitset.pyx

# distutils: language = c++
from libcpp.vector cimport vector


cdef class BitSet:

    def __cinit__(self, int size):
        self.vector = vector[bint](size)

    cpdef void inter(self, BitSet other) except *:
        # Do the intersection in place between two bitset

    cpdef void add(self, int element):
        if 0 <= element < self.vector.size():
            self.vector[element] = True

bitset.pxd

# distutils: language = c++
from libcpp.vector cimport vector


cdef class BitSet:
    cdef public vector[bint] vector
    cpdef void inter(self, BitSet other) except *
    cpdef void add(self, int element)

Мне нужно создать питона list из BitSet (около 12_000), каждый размером 1_000_000. Я бы сказал, что это должно занять 1_000_000 бит (для хранения типа bint) * 12000 = 1,5 ГБ

Но у меня очень быстро кончается память, вот картинка, чтобы объяснить больше

Самая низкая точка кривой составляет 1,5 ГБ, а самая высокая - 7 ГБ.

Я называю эту программу огромным списком, который может объяснить первый пик, второй, вероятно, тот, с которым я столкнулся.

Моей программе не хватает памяти только после 100_000 последовательностей.

Вот мой главный:

cdef class Main:
    def __cinit__(self):
        self.number_sequences # Int
        self.foo = [] # python list type

    def train(self, sequences):
        self.number_sequences = len(sequences)
        for id_seq, sequence in enumerate(sequences):
            for element in sequence:
                while not element < len(self.foo):
                    self.foo.append(BitSet(self.number_sequences))
                self.foo[element].add(id_seq)

Моя оценка использования памяти неверна? А почему?

Как я могу отследить свою память? Я не нашел никаких инструментов для Cython.

Есть ли какое-нибудь решение, чтобы оно поместилось в памяти? (Замена BitSet набором целых чисел python работает, но он намного медленнее и должен занимать больше места)

Answer 1

bint - это просто удобный целочисленный тип, который можно использовать для хранения значения true / false. Как и во всех других типах C, он должен иметь адрес, который можно измерять в целых байтах, и поэтому он занимает не менее 1 байта (на практике это выглядит как больше).

Для того, чтобы хранить буферы эффективным образом, вам нужно хранить целочисленные типы, а затем немного переключаться для доступа к отдельным элементам:

cdef uint8_t x = some_value
nth_element_is_true = bool(x & (1<<n)) # bitshift to get a suitable mask then bitwise and

Вы, очевидно, можете расширить это, чтобы использовать массивы для хранения нескольких элементов.

---

Существует несколько очевидных заранее созданных возможностей:

Сначала вы могли бы использовать numpy.packbits и unpackbits. Это генерирует достаточно дорогие временные переменные (например, unpackbits создаст массив в 8 раз больше).

Во-вторых, вы можете использовать std::vector<bool>, который уже оптимизирован для использования 1-битного на элемент:

from libcpp.vector cimport vector
from libcpp cimport bool
cdef vector[bool] vb = vector[bool](1000000)

Создание специализированного vector<bool>, которое не вполне ведет себя так же, как обычный vector считается плохой идеей в ретроспективе в C ++, но делает то, что вы хотите.