Каков наиболее эффективный способ объединения и хранения длинных битовых строк?

Question

Я работаю с набором данных, который включает в себя десятки тысяч цепочек битов переменной длины вплоть до 32768.

Данные создаются в виде списка, который я затем объединяю в несколько двоичных цепочек битов, которые, в свою очередь, преобразуются в INT.

Чтобы продемонстрировать мой метод:

import array

a = array.array('B', [4,5,13,4,4,9,12,13])
d = dict()

for i in set(a):
    d[i] = int('0b' + ''.join([str(int(i is b)) for b in a]), 2)

print d

Мой вопрос: есть ли более эффективный способ сделать это, не создавая строку длиной ~ 32000, а затем добавляя '0b', чтобы привести ее к INT? (Я предполагаю, что мой метод использует как минимум 32000 байтов в дополнение к списку источников для операции)

Кроме того, является ли INT самым дешевым способом их хранения, если я хочу сохранить их в форме, разрешающей побитовые операции?

Answer 1

Если вам нужна максимальная эффективность, один пакет, который должен приблизить вас, - bitarray.Он написан на c, поэтому молниеносно.

Чтобы создать bitarray, вы можете передать конструктору bitarray любую последовательность логических значений.Например:

>>> bitarray.bitarray([1, 1, 0, 1])
bitarray('1101')
>>> bitarray.bitarray([True, True, False, True])
bitarray('1101')
>>> bitarray.bitarray([range(3), [5.829048], [], ['can', 'I', 'help', 'you?']])
bitarray('1101')

Я сделал несколько таймингов, и действительно bitarray самый быстрый для более длинных строк.Но было несколько неожиданностей:

1. bitarray только на 50% быстрее, чем int(''.join(bs)) в большинстве случаев.
2. int(''.join(bs)) быстрее, чем предложенный метод shiftна tomasz для длин a больше 3000 и в порядке быстрее для длин a больше 30000.
3. даже для маленьких len(a),использование метода shift происходит всего в несколько раз быстрее.Асимптотическое повышение производительности, которое ''.join() обеспечивает для более длинных строк, составляет порядка секунд или десятков секунд, в то время как метод shift обеспечивает усиление только порядка миллисекунд для небольших строк.Таким образом, использование ''.join() здесь является явным победителем.

Так что, если вы не хотите использовать стороннюю библиотеку, то использование ''.join(), как вы делали выше, является лучшим решением!И действительно, польза от использования сторонней библиотеки в этом случае минимальна;так что, в конце концов, я бы не советовал, в конце концов - если вы в основном не хотите экономить память.

Наконец , одно небольшое замечание: вам не нужно добавлять '0b' к строке, как вы делали выше.Просто позвоните int(bitstring, 2) - базовый аргумент (2) делает '0b' избыточным.

>>> import array
>>> import random
>>> import bitarray
>>> 
>>>        #### Definitions: ####
>>> 
>>> def a_mask_join(a):
.....     d = dict()
.....     for i in set(a):
.....         d[i] = int(''.join([str(int(i is b)) for b in a]), 2)
.....     return d
..... 
>>> def mask(values, x):
.....     m = 0
.....     for v in values:
.....         m = (m << 1) + (v == x)
.....     return m
..... 
>>> def a_mask_shift(a):
.....     d = dict()
.....     for i in set(a):
.....         d[i] = mask(a, i)
.....     return d
..... 
>>> def a_mask_bitarray1(a):
.....     d = dict()
.....     for i in set(a):
.....         d[i] = bitarray.bitarray([int(i is b) for b in a])
.....     return d
..... 
>>> def a_mask_bitarray2(a):
.....     d = dict()
.....     for i in set(a):
.....         d[i] = int(bitarray.bitarray([int(i is b) for b in a]).to01(), 2)
.....     return d
..... 
>>> a = array.array('B', [4,5,13,4,4,9,12,13])
>>> 
>>>        #### Test: ####
>>> 
>>> dicts = (f(a) for f in (a_mask_join, a_mask_shift1, a_mask_shift2, a_mask_bitarray2))
>>> sorted_results = (sorted(int(v) for v in d.values()) for d in dicts)
>>> all(r == sorted(a_mask1(a).values()) for r in sorted_results)
True
>>> 
>>>        #### Timing: ####
>>> 
>>> for size in (int(10 ** (e / 2.0)) for e in range(2, 11)):
.....     print size
.....     a = array.array('B', [random.randrange(0, 30) for _ in range(size)])
.....     %timeit a_mask_join(a)
.....     %timeit a_mask_shift(a)
.....     %timeit a_mask_bitarray1(a)
.....     %timeit a_mask_bitarray2(a)
..... 
10
10000 loops, best of 3: 61.2 us per loop
100000 loops, best of 3: 17.5 us per loop
10000 loops, best of 3: 38.4 us per loop
10000 loops, best of 3: 46.7 us per loop
31
1000 loops, best of 3: 343 us per loop
10000 loops, best of 3: 97.9 us per loop
1000 loops, best of 3: 212 us per loop
1000 loops, best of 3: 242 us per loop
100
1000 loops, best of 3: 1.45 ms per loop
1000 loops, best of 3: 486 us per loop
1000 loops, best of 3: 825 us per loop
1000 loops, best of 3: 870 us per loop
316
100 loops, best of 3: 4.53 ms per loop
100 loops, best of 3: 2.46 ms per loop
100 loops, best of 3: 2.53 ms per loop
100 loops, best of 3: 2.65 ms per loop
1000
100 loops, best of 3: 14.5 ms per loop
100 loops, best of 3: 10.8 ms per loop
100 loops, best of 3: 7.78 ms per loop
100 loops, best of 3: 8.04 ms per loop
3162
10 loops, best of 3: 47.4 ms per loop
10 loops, best of 3: 71.8 ms per loop
10 loops, best of 3: 24.1 ms per loop
10 loops, best of 3: 25.6 ms per loop
10000
10 loops, best of 3: 137 ms per loop
1 loops, best of 3: 425 ms per loop
10 loops, best of 3: 75.7 ms per loop
10 loops, best of 3: 78 ms per loop
31622
1 loops, best of 3: 430 ms per loop
1 loops, best of 3: 3.25 s per loop
1 loops, best of 3: 241 ms per loop
1 loops, best of 3: 246 ms per loop
100000
1 loops, best of 3: 1.37 s per loop
1 loops, best of 3: 29.7 s per loop
1 loops, best of 3: 805 ms per loop
1 loops, best of 3: 800 ms per loop

Answer 2

Взгляните на библиотеку bitstring . Вы можете манипулировать отдельными битами BitArray (в следующем примере показаны неизменные Bits экземпляры):

from bitstring import Bits

def bitLen(int_type):
    length = 0
    while (int_type):
        int_type >>= 1
        length += 1
    return(length)

intList = [4,5,13,4,4,9,12,13]
intSet = set(intList)
for i in intSet:
   print i, Bits(int=i, length=bitLen(i)+1).bin

Что обеспечивает:

9 0b01001
4 0b0100
5 0b0101
12 0b01100
13 0b01101

Вы можете использовать Bits.int для преобразования представления бита в int и Bits.len для получения длины. Я оставлю это для вас, чтобы включить это в словарную форму, которую вы ожидаете.

Answer 3

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

def mask(values, x):
  m = 0
  for v in values:
     m = (m << 1) + (v == x) # shift left and flip the lowest bit if needed
  return m

И в действии:

for i in set(a):
  d[i] = mask(a, i)

Это намного быстрее, чем использовать join и нет использовать дополнительную память, но желаемое целое число.Могу поспорить, что вы можете использовать несколько методов из itertools, соединить их вместе и произвести впечатление на окружающих, но я бы просто придерживался метода.И я думаю, что вы правы, не можете представить себе лучший способ хранения, чем целое число.