Python: tìm khóa gần nhất trong từ điển từ khóa nhập đã cho

Question

Tôi có dữ liệu dưới dạng từ điển .. NOw Tôi lấy đầu vào từ người dùng và có thể là bất cứ điều gì .. Và tôi đang cố gắng thực hiện tiếp theo. Nếu khóa tồn tại sau đó mát .. lấy giá trị từ từ điển. nếu không, sau đó tìm nạp gần nhất (theo nghĩa số). Đối example..if phím đầu vào là 200 và các phím giống như: ....

197,202,208... 

Sau đó, có lẽ 202 là chìa khóa gần 200 .. Bây giờ, từ điểm thuật toán xem. của nó thẳng về phía trước .. nhưng là có một cách pythonic để làm điều này? Cảm ơn

Answer 1

đây là chức năng của bạn trên một dòng:

data.get(num, data[min(data.keys(), key=lambda k: abs(k-num))]) 

chỉnh sửa: để không đánh giá phút khi quan trọng là trong việc sử dụng dict:

data[num] if num in data else data[min(data.keys(), key=lambda k: abs(k-num))] 

hoặc nếu tất cả các giá trị trong data đánh giá để True bạn có thể sử dụng:

data.get(num) or data[min(data.keys(), key=lambda k: abs(k-num))] 

Answer 2

Điều này sẽ làm những gì bạn muốn (trừ nhận từ khóa, nhưng bạn có thể tìm ra điều đó :).

f = lambda a,l:min(l,key=lambda x:abs(x-a)) 
numbers = (100, 200, 300, 400) 
num = int(raw_input()) 
print 'closest match:', f(num, numbers) 

Lưu ý: f là từ this question.

Answer 3

Nếu tất cả những gì bạn có là từ điển Python, bạn không thể làm tốt hơn kiểm tra tất cả các mục trong từ điển (như trong câu trả lời của Will). Tuy nhiên, nếu bạn muốn tìm khóa gần nhất hiệu quả hơn số đó (tức là, trong O(log N) thay vì O(N)), bạn muốn có một cây cân bằng nào đó.

Thật không may, tôi không tin rằng Python có cơ sở hạ tầng như vậy trong thư viện chuẩn của nó - như cách Pythonic là sử dụng một dict thay thế. Vì vậy, nếu bạn mong muốn thực hiện nhiều truy vấn như vậy trên một bản đồ lớn, lựa chọn tốt nhất của bạn có thể là tìm một thư viện mở rộng, hoặc thậm chí cuộn ...

Answer 4

Vấn đề này được thực hiện khó khăn hơn nhiều bởi các phím dict không theo thứ tự đặc biệt. Nếu bạn có thể chơi với cách bạn tạo ra dict để chúng có trật tự (như ví dụ của bạn) và sử dụng python> = 2.7 bạn có thể sử dụng OrderedDict và bisect để làm cho tia chớp này nhanh.

import collections 
a = collections.OrderedDict() 
for i in range(100): 
    a[i] = i 

import bisect 
ind = bisect.bisect_left(a.keys(), 45.3) 

Sau đó, bạn chỉ cần kiểm tra phần tử ind và ind-1 để xem đó là gần hơn, do đó làm cho tính toán ít hơn rất nhiều.

---

Như được chỉ ra dưới đây bởi Steven G, trong Python3 .keys() không chỉ là danh sách và phải được thay đổi thành một.

bisect.bisect_left(list(a.keys()), 45.3) 

Answer 5

Thay vì sử dụng OrderedDict và chia hai nga, xem xét các loại SortedDict trong module sortedcontainers. Đó là một tinh khiết-Python và fast-as-C implementation của danh sách được sắp xếp, dict, và các loại thiết lập với 100% thử nghiệm bảo hiểm và giờ căng thẳng.

Với SortedDict bạn có thể chia đôi cho khóa mong muốn. Ví dụ:

from sortedcontainers import SortedDict 
sd = SortedDict((key, value) for key, value in data) 

# Bisect for the index of the desired key. 
index = sd.bisect(200) 

# With that index, lookup the key. 
key = sd.iloc[index] 

# You can also look ahead or behind to find the nearest key. 
behind = sd.iloc[index - 1] 
ahead = sd.iloc[index + 1] 

Đó là Pythonic để sử dụng PyPI!