खोज एल्गोरिदम लेकिन कार्यों के लिए

Question

इनपुट की एक सूची को देखते हुए (मान लें कि वे केवल पूर्णांक हैं), और कार्यों की एक सूची (और ये फ़ंक्शन एक पूर्णांक लेते हैं, और या तो सत्य या गलत)।

मुझे इनपुट की यह सूची लेनी है, और देखें कि सूची में कोई भी फ़ंक्शन सूची में किसी भी मान के लिए सही होगा या नहीं।

वहाँ हे की तुलना में इस तेजी से करने के लिए कोई रास्ता नहीं है (एन^2)

अभी मैं क्या है

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

किसी भी तेजी से तरीकों है?

Answer 1

कार्यों पर किसी और जानकारी के बिना, len(functions) * len(values) के परिणाम संभव फ़ंक्शन कॉल को एक-दूसरे से स्वतंत्र माना जाना चाहिए, इसलिए उन सभी की जांच करने से कोई तेज़ तरीका नहीं है। builtin समारोह any() भी शॉर्ट सर्किट, बस अपने मूल कोड की तरह

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

:

आप इस एक छोटे से अधिक संक्षेप में, हालांकि लिख सकते हैं।

संपादित: ऐसा लगता है कि वांछित बराबर

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

हो गया होता एक चर्चा के लिए टिप्पणियाँ देखें।

Answer 2

नहीं, कोई तेज़ तरीका नहीं है। ओ (एम * एन) सीमा है। यदि आपके कार्यों के बारे में अधिक जानकारी थी, तो आप इसे हरा सकते हैं, लेकिन सामान्य मामले में, नहीं।

Answer 3

यदि आप कार्यों या मूल्यों के बारे में अधिक जानते हैं, तो आप नियमित खोज इंजन क्या कर सकते हैं- मूल्य सूची पर कुछ प्रकार की अनुक्रमण लागू करें जो केवल एक ही पास की आवश्यकता है।

संपादित करें:

यहाँ है कि यह उपयोग के मामले के लिए काम करता any() साथ एक दृष्टिकोण है।

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

Answer 4

आप केवल उन्हें पूछताछ की और हाथ में कार्यों पर कुछ सरल बनाने मान्यताओं के बिना O(nm) की तुलना में बेहतर नहीं कर सकते।

ऐसा इसलिए है क्योंकि इस सबूत के लिए कोई ऐसा कार्य नहीं है, यह साबित करने के लिए कि किसी भी पूर्णांक और किसी भी फ़ंक्शन के लिए, क्वेरी का परिणाम False है।

यह साबित करने के लिए, आप सभी प्रश्न करने होंगे कम से कम ऐसा नहीं कर सकते क्योंकि आपके state spaceO(2^nm) है और एक प्रश्न सिर्फ राज्य अंतरिक्ष आधा कर देगा, ताकि आप O(log_2(2^nm)) = O(nm) प्रश्नों की जरूरत समाधान के लिए अपने राज्य स्थान को कम करने "हर कार्य झूठे रिटर्न प्रत्येक पूर्णांक के लिए "।

Answer 5

यह वास्तव में हे (एन) नहीं है, लेकिन यह हर कार्यों पर पुनरावृत्ति से बचाता है:

#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)) 

चर्चा नेस्टेड lambdas pythonic हैं एक पूरी अलग कहानी है या नहीं, लेकिन मैं कार्यात्मक में सोचने के लिए करते हैं कार्यों की सूचियों से निपटने के दौरान शर्तें।