Cách nhanh nhất để tìm hai phần tử nào của danh sách một mục khác gần nhất trong python

Question

Đầu vào là danh sách các phần tử được sắp xếp và một mục bên ngoài. Ví dụ:

list_ = [0, 3.5, 5.8, 6.2, 88] 
item = 4.4 

cách nhanh nhất tìm ra hai yếu tố trong list_item thác giữa là gì? Trong trường hợp này, ví dụ, hai con số sẽ là 3,5 và 5,8. Bất kỳ ý tưởng?

Answer 1

Vì đầu vào được sắp xếp, bạn đặt cược theo thuật toán tốt nhất là sử dụng mô-đun bisect - ví dụ: bisect_left

>>> list_ = [0, 3.5, 5.8, 6.2, 88] 
>>> item = 4.4 
>>> bisect.bisect_left(list_, item) 
2 

Các mục bạn muốn cư trú tại chỉ số bisect_left(list_, item) và
bisect_left(list_, item) - 1

này sẽ cho bạn kết quả trong O(logN) tìm kiếm - Nó không trở nên tốt hơn rất nhiều so với từ một quan điểm thuật toán.

Answer 2

Bạn có thể sử dụng chức năng bisect module's bisect để có được những chỉ số mà tại đó các item phù hợp trong

list_, item = [0, 3.5, 5.8, 6.2, 88], 4.4 
from bisect import bisect 
print bisect(list_, item) 
# 2 

Ghi bạn list_ phải được sắp xếp, để có thể sử dụng các chức năng trong bisect module.

Answer 3

Tôi sẽ sử dụng gọn gàng:

from numpy import * 
x = array([0, 3.5, 5.8, 6.2, 88]) 
item = 4.4 

i= argmin(abs(x-item)) 
print(i)