अनावश्यक गणना से कैसे बचें?

Question

यदि सूची में 3 से अधिक तत्वों के लिए कोई परीक्षण विफल रहता है तो मुझे झूठी वापसी की आवश्यकता है। क्या ऑप्टिमाइज़ करने के लिए मैं कुछ भी कर सकता हूं?

isItemOk :: Integer -> Boolean 
isItemOk = (some costly opernation) 

इस समारोह मैं अनुकूलन करने के लिए कोशिश कर रहा हूँ,

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum ([ 1 | x <- [1.1000], isItemOk x ]) 

अनुकूलन पर मेरे प्रयास है, अगर यह 4 तत्वों अधिक के लिए नहीं लग रही होगी पाता ले संभालने है।

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum (take 4 [ 1 | x <- [1.1000], isItemOk x ]) 

धन्यवाद।

Answer 1

तुम सिर्फ कुछ है कि नाकाम रहने के तत्वों, तो take 4 और घटकों की संख्या जानना आप length साथ है के लिए जाँच करता साथ filter उपयोग कर सकते हैं।

आलसी मूल्यांकन का मतलब है कि यह उन चारों को ढूंढने के बाद कुछ भी जांचने से परेशान नहीं होगा, इसलिए आप कर चुके हैं। बेशक, यदि परीक्षण तीन या कम तत्वों के लिए विफल रहता है, तो यह पूरी सूची की जांच करेगा, लेकिन इसके बारे में आप कुछ भी नहीं कर सकते हैं।

से महत्वपूर्ण बात से बचें "परीक्षण में विफल होने वाले तत्वों की गणना करें" या "फ़िल्टर करें और फिर परिणाम की लंबाई प्राप्त करें", या ऐसा कुछ भी। take या पहले कुछ ऐसा उपयोग किए बिना, ऐसा करने से पूरी सूची की जांच हो जाएगी। यह शुरुआती लोगों को सलाह दी जाती है कि "उपयोग null या रिक्त सूचियों की जांच के लिए पैटर्न मिलान" का एक और सामान्य संस्करण है। लेकिन ऐसा लगता है कि आप पहले से ही उस गलती से परहेज कर रहे हैं!

Answer 2

3 की तरह कम संख्या के लिए, आप पैटर्न मिलान का उपयोग कर सकते हैं।

case filter isItemOk xs of 
    x1 : x2 : x3 : _ -> ... 
    _    -> ... 

Answer 3

मुझे पहली बार अपने समारोह थोड़ा पुनर्लेखन दो,

रूप

isListOk :: Bool 
isListOk = length (filter isItemOk [1 .. 1000]) <= 3 

तार्किक रूप से आपके संस्करण की तुलना में अधिक मुहावरेदार है। (ध्यान दें कि मैं भी रूप में तुम्हारा गलत थी प्रकार हस्ताक्षर बदल दिया है। इसके अलावा, आप 1 .. 1000 लिखा जाना चाहिए था बल्कि 1.1000 से।)

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

दुर्भाग्यवश, length का उपयोग (या प्रत्येक तत्व को सूची से 1 तक मैप करना और उसके परिणामस्वरूप सूची को सूचीबद्ध करना) जैसा कि आप करते हैं) यहां रास्ते में आ रहा है। यही है, length सूची की रीढ़ की हड्डी में सख्त है: यह केवल सूची की लंबाई का उत्पादन कर सकता है अगर यह इसके अंत में मूल्यांकन करता है, जो इस मामले में, इसका मतलब है कि आपके कार्यक्रम को आपके चेक को हजार बार ।

एक समाधान लंबाई की गणना को जोड़ना होगा (यानी।

isNotLongerThan :: [a] -> Integer -> Bool 
isNotLongerThan []  n = n >= 0 
isNotLongerThan (_ : xs) n = n >= 1 && isNotLongerThan xs (n - 1) 

और उसके बाद लिखें:, सूची की रीढ़ का ट्रेवर्सल) और परीक्षण गणना लंबाई एक भी समारोह अपने तर्क सूची की रीढ़ की हड्डी में आलसी वास्तव में यह है कि में एक दी गई सीमा से अधिक नहीं है कि क्या

isListOk :: Bool 
isListOk = filter isItemOk [1 .. 1000] `isNotLongerThan` 3 

एक पुन: प्रयोज्य समाधान के लिए, आप निश्चित रूप से दोनों विधेय और सीमा से अधिक सार कर सकते हैं: Hammar, बताते हैं

forNoMoreThan :: (a -> Bool) -> Integer -> [a] -> Bool 
forNoMoreThan p n = (`isNotLongerThan` n) . filter p 

isListOk :: Bool 
isListOk = (isItemOk `forNoMoreThan` 3) [1 .. 1000] 

अंत में, यदि आपके ताड़ना पुराना छोटा और निश्चित छोटा है, आप यह निर्धारित करने के लिए पैटर्न मिलान का उपयोग कर सकते हैं कि कोई सूची पर्याप्त है या नहीं।

Answer 4

मैं इस अवसर को lazy natural numbers को प्रचारित करने का अवसर लेना चाहता हूं। इस पुस्तकालय और genericLength का उपयोग करना, हम सिर्फ

import Data.Number.Natural 
import Data.List 
isListOk = (3 :: Natural) >= genericLength (filter isItemOk [1..1000]) 

लिख सकते हैं और की तुलना में यह करने के लिए है यह कोई अधिक काम करना होगा: इस समारोह लौटने से पहले ज्यादा से ज्यादा चार ठीक आइटम मिल जाएगा। उदाहरण के लिए:

> (3 :: Natural) >= genericLength (filter even (2:4:6:8:undefined)) 
False