Trong Python, làm thế nào để bạn tìm thấy chỉ mục của giá trị đầu tiên lớn hơn một ngưỡng trong danh sách được sắp xếp?

Question

Trong Python, làm cách nào bạn tìm thấy chỉ mục của giá trị đầu tiên lớn hơn ngưỡng trong danh sách được sắp xếp?

Tôi có thể nghĩ ra một số cách để thực hiện việc này (tìm kiếm tuyến tính, phân chia bằng tay, ..), nhưng tôi đang tìm cách làm sạch một cách hợp lý. Vì nó có lẽ là một vấn đề khá phổ biến, tôi chắc chắn các nhà kinh nghiệm có thể giúp đỡ!

Cảm ơn!

Answer 1

Hãy xem bisect.

import bisect 

l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] 

bisect.bisect(l, 55) # returns 7 

Hãy so sánh nó với tìm kiếm tuyến tính:

timeit bisect.bisect(l, 55) 
# 375ns 


timeit next((i for i,n in enumerate(l) if n > 55), len(l)) 
# 2.24us 


timeit next((l.index(n) for n in l if n > 55), len(l)) 
# 1.93us 

Answer 2

Bạn có thể nhận được một thời gian tốt hơn so với/cách tiếp cận phát enumerate sử dụng itertools; Tôi nghĩ rằng itertools cung cấp việc triển khai nhanh hơn các thuật toán cơ bản, cho các trình tạo hiệu suất trong tất cả chúng ta. Nhưng bisect vẫn có thể nhanh hơn.

from itertools import islice, dropwhile 

threshold = 5 
seq = [1,4,6,9,11] 
first_val = islice(dropwhile(lambda x: x<=threshold, seq),0,1) 
result = seq.index(first_val) 

Tôi tự hỏi về sự khác biệt giữa cách tiếp cận bisect đưa ra ở đây và một trong những liệt kê cho câu hỏi của bạn trong các ví dụ doc, như xa như thành ngữ/tốc độ. Chúng hiển thị một cách tiếp cận để tìm giá trị, nhưng cắt ngắn thành dòng đầu tiên, nó trả về chỉ mục. Tôi đoán rằng vì nó được gọi là "bisect_right" thay vì "bisect", nó có lẽ chỉ nhìn từ một hướng. Do danh sách của bạn được sắp xếp và bạn muốn lớn hơn, đây có thể là nền kinh tế tìm kiếm lớn nhất.

from bisect import bisect_right 

def find_gt(a, x): 
    'Find leftmost value(switching this to index) greater than x' 
    return bisect_right(a, x) 

Câu hỏi thú vị.