Python nhanh chóng băm đối tượng có thể thay đổi

Question

Tôi có một mã vạch mà tôi cần sử dụng làm khóa cho từ điển. Lý tưởng nhất là tôi muốn làm điều này mà không làm một bản sao của bộ nhớ kích thước của bytearray. Có anyway để làm điều này? Về cơ bản,

b = some bytearray 
d[byte(b)] = x 

Có cách nào nhanh hơn để thực hiện việc này không? byte (b) là một hoạt động O (len (bytearray)) không mong muốn.

Answer 1

Bất kỳ thuật toán băm nào thực sự thực hiện công việc của nó một cách chính xác sẽ sử dụng thời gian O (len (b)). Vì vậy, câu trả lời cho "là có cách nào nhanh hơn để làm điều này" là không.

Nếu mối quan tâm thực tế của bạn là sử dụng bộ nhớ, sau đó, về nguyên tắc, bạn có thể thêm phương thức __hash__ vào một lớp con của dấu gạch ngang. Nhưng đó là một ý tưởng khá tồi. Hãy xem điều gì xảy ra:

>>> class HashableBytearray(bytearray): 
...  def __hash__(self): 
...   return hash(str(self)) 
... 
>>> h = HashableBytearray('abcd') 
>>> hash(h) 
-2835746963027601024 
>>> h[2] = 'z' 
>>> hash(h) 
-2835746963002600949 

Vì vậy, cùng một đối tượng có thể băm thành hai điểm khác nhau trong từ điển, điều này không được phép xảy ra. Và nó trở nên tồi tệ hơn:

>>> d = dict() 
>>> hb1 = HashableBytearray('abcd') 
>>> hb2 = HashableBytearray('abcd') 
>>> d[hb1] = 0 
>>> d[hb2] = 1 
>>> d 
{bytearray(b'abcd'): 1} 

Ok, cho đến nay, rất tốt. Các giá trị bằng nhau, vì vậy chỉ nên có một mục trong từ điển. Mọi thứ đều hoạt động như mong đợi. Bây giờ chúng ta hãy xem những gì sẽ xảy ra khi chúng ta thay đổi hb1:

Xem cách mặc dù hb2 không thay đổi chút nào, nó tạo ra một cặp khóa-giá trị mới trong từ điển thời gian này?

Mỗi lần tôi chuyển một khóa đến d, khóa đó bằng 'abcd'. Nhưng vì giá trị của khóa đầu tiên đã thay đổi sau khi thêm vào từ điển, Python không thể biết rằng giá trị của khóa mới giống với khóa cũ đã được thêm vào khi nó được thêm vào. Bây giờ có hai cặp khóa-giá trị trong từ điển, khi chỉ nên có một cặp.

Đây chỉ là một trong nhiều cách sử dụng các giá trị có thể thay đổi làm khóa có thể dẫn đến hành vi không thể đoán trước và rất sai. Chỉ cần chuyển đổi bytearray thành loại không thay đổi được hoặc hoạt động với các loại bất biến ngay từ đầu.

---

Và đối với sự tò mò: chắc chắn, buffer lưu trữ băm đầu tiên, nhưng điều đó không giúp gì cả. Chỉ có hai giá trị quan trọng, vì vậy đây sẽ tạo ra chỉ có hai mục dict:

>>> a, b, c = bytearray('abcd'), bytearray('abcd'), bytearray('abzd') 
>>> a_buf, b_buf, c_buf = buffer(a), buffer(b), buffer(c) 
>>> d = {b_buf:1, c_buf:2} 
>>> b[2] = 'z' 
>>> d[a_buf] = 0 

Nhưng nó tạo ra ba:

>>> d 
{<read-only buffer for 0x1004a2300, size -1, offset 0 at 0x100499cb0>: 1, 
<read-only buffer for 0x1004a2420, size -1, offset 0 at 0x100499cf0>: 0, 
<read-only buffer for 0x1004a22d0, size -1, offset 0 at 0x100499c70>: 2} 

Answer 2

Nếu bạn lo lắng về thời gian, và chìa khóa mà bạn đang sử dụng luôn luôn là như nhau đối tượng, bạn có thể sử dụng nó id (vị trí trong bộ nhớ) là chìa khóa trong từ điển của bạn:

b = some byte array 
d[id(b)] = x 

Nếu bạn liên quan đến bộ nhớ, bạn có thể sử dụng hàm băm mật mã tốt trên mảng byte của mình và có thể bạn sẽ không bao giờ gặp phải va chạm (ví dụ: sử dụng sha1 và có somediscussions trên số internet về khả năng có được một vụ va chạm sha1 vô ý).Nếu bạn đang okay với nguy cơ vô cùng nhỏ, bạn có thể:

b = some byte array 
d[hashlib.sha1(b).hexdigest()] = x 

Đó sẽ là O (n) trong kích thước của mảng byte của bạn trong thời gian (mỗi khi bạn tính toán hash), nhưng bạn 'd có thể có một mảng byte khác đọc vào một thời điểm sau đó, nhưng đại diện cho cùng một chuỗi các byte, mà sẽ băm vào cùng một khóa từ điển.

Và @senderle hoàn toàn đúng; bạn không muốn sử dụng một đối tượng thực sự có thể thay đổi được, khi sử dụng nó theo giá trị (trái với một hàm bất biến của nó, như là id()) làm khóa cho từ điển. Hàm băm của đối tượng được sử dụng làm khóa từ điển không được thay đổi; nó vi phạm một bất biến của những gì đối tượng từ điển mong đợi trong một hàm băm.

Answer 3

Tôi nghĩ rằng điều này có thể gần với những gì bạn muốn. Đó là tương đối nhanh và không sao chép bộ nhớ kích thước của bytearray, tuy nhiên nó là O (len (bytearray)) - như tôi không thể nghĩ ra bất kỳ cách nào để tránh điều đó và luôn luôn tạo ra giá trị duy nhất.

def byte(ba): 
    """ decode a bytearray as though it were a base 256 number """ 
    return reduce(lambda a,d: a*256 + d, ba, 0) 

ba = bytearray('this is a bytearray') 
d = {} 
d[byte(ba)] = 42 
ba[8] = 'X' # now 'this is X bytearray' 
d[byte(ba)] = 17 # accesses a separate entry in dict 
print d