Thuật toán tìm kiếm nhưng đối với hàm

Question

Đưa ra danh sách đầu vào (giả sử chúng chỉ là số nguyên) và danh sách hàm (và các hàm này lấy số nguyên và trả về Đúng hoặc Sai).

Tôi phải lấy danh sách đầu vào này và xem liệu có bất kỳ hàm nào trong danh sách sẽ trả về True cho bất kỳ giá trị nào trong danh sách hay không.

Có cách nào để làm điều này nhanh hơn so với O (n^2)

Ngay bây giờ những gì tôi có là

for v in values: 
    for f in functions: 
     if f(v): 
      # do something to v 
      break 

Bất kỳ phương pháp nhanh hơn?

Answer 1

Nếu không có thêm thông tin về chức năng, kết quả của các cuộc gọi chức năng có thể phải được xem là độc lập với nhau, vì vậy không có cách nào nhanh hơn kiểm tra tất cả.

Bạn có thể viết này một chút chính xác hơn, mặc dù:

any(f(v) for v in values for f in functions) 

Chức năng dựng sẵn any() cũng ngắn mạch, giống như mã ban đầu của bạn.

Sửa: Nó chỉ ra rằng tương đương với mong muốn sẽ có được

all(any(f(v) for f in functions) for v in values) 

Xem các ý kiến ​​cho một cuộc thảo luận.

Answer 2

Không, không có cách nào nhanh hơn. O (m * n) là giới hạn. Nếu bạn có thêm thông tin về các chức năng, bạn có thể đánh bại được điều đó, nhưng trong trường hợp chung, không.

Answer 3

Nếu bạn biết thêm về các hàm hoặc giá trị, bạn có thể thực hiện công cụ tìm kiếm thông thường áp dụng một số loại chỉ mục trên danh sách giá trị chỉ yêu cầu một lần truyền.

EDIT:

Đây là cách tiếp cận với any() hoạt động cho trường hợp sử dụng này.

for v in values: 
    if any(f(v) for f in functions): 
     #do something to v 

Answer 4

Bạn không thể làm tốt hơn O(nm) bằng cách chỉ truy vấn chúng và không có một số giả định đơn giản hóa các chức năng trong tầm tay.

Đó là vì bằng chứng không có bất kỳ chức năng nào như vậy yêu cầu bạn chứng minh rằng, đối với bất kỳ số nguyên và hàm nào, kết quả của truy vấn là False.

Để chứng minh điều đó, bạn không thể làm ít hơn thực hiện tất cả các truy vấn, bởi vì state space của bạn là O(2^nm) và một truy vấn chỉ làm giảm một nửa không gian trạng thái, vì vậy bạn cần O(log_2(2^nm)) = O(nm) truy vấn để giảm không gian trạng thái của bạn với các giải pháp "tất cả các chức năng trả về false cho mọi số nguyên ".

Answer 5

Đây không phải là thực sự O (n), nhưng nó giúp bạn tiết kiệm từ iterating trên các chức năng mọi:

#combine all funcs into one with `or` 
newFunc = reduce(lambda f,g: (lambda x: f(x) or g(x)), funcs) 

#cleaner than for, i think 
satisfied = any(map(newFunc, values)) 

Thảo luận dù lambdas lồng nhau là pythonic là một câu chuyện hoàn toàn khác nhau, nhưng tôi có xu hướng nghĩ trong chức năng các điều khoản khi xử lý danh sách các hàm.