Hai chiều/ngược lại bản đồ

Question

Tôi đang làm điều tổng đài này trong python, nơi tôi cần theo dõi ai đang nói chuyện với ai, vì vậy nếu Alice -> Bob, thì điều đó ngụ ý rằng Bob -> Alice.

Có, tôi có thể điền hai bản đồ băm, nhưng tôi tự hỏi liệu có ai có ý tưởng làm điều đó với một bản đồ không.

Hoặc đề xuất cấu trúc dữ liệu khác.

Không có nhiều cuộc hội thoại. Giả sử đây là trung tâm dịch vụ khách hàng, vì vậy khi Alice quay số vào tổng đài, cô ấy sẽ chỉ nói chuyện với Bob. Câu trả lời của anh cũng chỉ dành cho cô.

Answer 1

Bạn có thể tạo loại từ điển của riêng mình bằng cách phân lớp dict và thêm logic mà bạn muốn. Dưới đây là một ví dụ cơ bản:

class TwoWayDict(dict): 
    def __setitem__(self, key, value): 
     # Remove any previous connections with these values 
     if key in self: 
      del self[key] 
     if value in self: 
      del self[value] 
     dict.__setitem__(self, key, value) 
     dict.__setitem__(self, value, key) 

    def __delitem__(self, key): 
     dict.__delitem__(self, self[key]) 
     dict.__delitem__(self, key) 

    def __len__(self): 
     """Returns the number of connections""" 
     return dict.__len__(self) // 2 

Và nó hoạt động như sau:

>>> d = TwoWayDict() 
>>> d['foo'] = 'bar' 
>>> d['foo'] 
'bar' 
>>> d['bar'] 
'foo' 
>>> len(d) 
1 
>>> del d['foo'] 
>>> d['bar'] 
Traceback (most recent call last): 
    File "<stdin>", line 7, in <module> 
KeyError: 'bar' 

tôi chắc chắn rằng tôi không bao gồm tất cả các trường hợp, nhưng điều đó sẽ giúp bạn bắt đầu.

Answer 2

Không, thực sự không có cách nào để thực hiện việc này mà không cần tạo hai từ điển. Làm thế nào nó có thể thực hiện điều này chỉ với một từ điển trong khi tiếp tục cung cấp hiệu suất tương đương?

Bạn nên tạo loại tùy chỉnh đóng gói hai từ điển và hiển thị chức năng bạn muốn.

Answer 3

Hai bản đồ băm thực sự có thể là giải pháp hoạt động nhanh nhất giả sử bạn có thể tiết kiệm bộ nhớ. Tôi sẽ bọc chúng trong một lớp đơn - gánh nặng cho lập trình viên là đảm bảo rằng hai bản đồ băm đồng bộ hóa chính xác.

Answer 4

tôi sẽ chỉ cư một băm thứ hai, với

reverse_map = dict((reversed(item) for item in forward_map.items())) 

Answer 5

Trong trường hợp đặc biệt, bạn có thể lưu trữ cả trong một từ điển:

relation = {} 
relation['Alice'] = 'Bob' 
relation['Bob'] = 'Alice' 

Kể từ những gì bạn đang mô tả là một mối quan hệ đối xứng. A -> B => B -> A

Answer 6

Bạn có hai vấn đề riêng biệt.

1. Bạn có đối tượng "Đối thoại". Nó đề cập đến hai người. Vì một người có thể có nhiều cuộc hội thoại, bạn có mối quan hệ nhiều-nhiều.

2. Bạn có Bản đồ từ người đến danh sách các cuộc trò chuyện. Một chuyển đổi sẽ có một cặp người.

Do something như thế này

from collections import defaultdict 
switchboard= defaultdict(list) 

x = Conversation("Alice", "Bob") 
y = Conversation("Alice", "Charlie") 

for c in (x, y): 
    switchboard[c.p1].append(c) 
    switchboard[c.p2].append(c) 

Answer 7

Các kjbuckets module mở rộng C cung cấp một "đồ thị" cấu trúc dữ liệu mà tôi tin mang đến cho bạn những gì bạn muốn.

Answer 8

Bạn có thể sử dụng DoubleDict như được hiển thị trong recipe 578224 trên Python Cookbook.

Answer 9

Một giải pháp khả thi khác là triển khai một lớp con của dict, giữ từ điển gốc và theo dõi phiên bản ngược của nó. Việc giữ hai dấu riêng biệt có thể hữu ích nếu các khóa và giá trị chồng lên nhau.

class TwoWayDict(dict): 
    def __init__(self, my_dict): 
     dict.__init__(self, my_dict) 
     self.rev_dict = {v : k for k,v in my_dict.iteritems()} 

    def __setitem__(self, key, value): 
     dict.__setitem__(self, key, value) 
     self.rev_dict.__setitem__(value, key) 

    def pop(self, key): 
     self.rev_dict.pop(self[key]) 
     dict.pop(self, key) 

    # The above is just an idea other methods 
    # should also be overridden. 

Ví dụ:

>>> d = {'a' : 1, 'b' : 2} # suppose we need to use d and its reversed version 
>>> twd = TwoWayDict(d) # create a two-way dict 
>>> twd 
{'a': 1, 'b': 2} 
>>> twd.rev_dict 
{1: 'a', 2: 'b'} 
>>> twd['a'] 
1 
>>> twd.rev_dict[2] 
'b' 
>>> twd['c'] = 3 # we add to twd and reversed version also changes 
>>> twd 
{'a': 1, 'c': 3, 'b': 2} 
>>> twd.rev_dict 
{1: 'a', 2: 'b', 3: 'c'} 
>>> twd.pop('a') # we pop elements from twd and reversed version changes 
>>> twd 
{'c': 3, 'b': 2} 
>>> twd.rev_dict 
{2: 'b', 3: 'c'} 

Answer 10

Có thư viện các bộ sưu tập-mở rộng trên pypi: https://pypi.python.org/pypi/collections-extended/0.6.0

Sử dụng lớp song ánh là dễ dàng như:

RESPONSE_TYPES = bijection({ 
    0x03 : 'module_info', 
    0x09 : 'network_status_response', 
    0x10 : 'trust_center_device_update' 
}) 
>>> RESPONSE_TYPES[0x03] 
'module_info' 
>>> RESPONSE_TYPES.inverse['network_status_response'] 
0x09 

Answer 11

Tôi biết đó là một câu hỏi cũ hơn, nhưng tôi muốn đề cập đến một giải pháp tuyệt vời khác cho vấn đề này, cụ thể là gói python bidict. Nó cực kỳ thẳng về phía trước để sử dụng:

from bidict import bidict 
map = bidict(Bob = "Alice") 
print(map["Bob"]) 
print(map.inv["Alice"])