連接和存儲長位串的最有效方式是什麼？

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在大多數情況下只比int(''.join(bs))快50％。
2. int(''.join(bs))比爲3000 a更長的長度提出tomasz的shift方法快，而對於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) 

這比使用連接更快，並且不使用更多的內存但所需的整數。我敢打賭，你可以使用itertools中的幾種方法，將它們連接在一起並給周圍的人留下深刻印象，但我會堅持使用一種方法。我認爲你是對的，無法想象存儲它的更好方式比整數。