Haskell işlevinin Naive uygulaması 'daha akıllı' çözümden daha hızlıdır?

Question

Bu yüzden Haskell’e yeni başlayan biriyim ve naif uygulamamın neden daha akıllıca bir çözüm olduğunu düşündüğümden daha hızlı olduğunu anlamaya çalışıyorum.

String verilen bir işlev, String'in bir ve tam olarak sesli harf kullanıp kullanmadığını belirten bir Bool döndürecek bir işlev yazmaya çalışıyorum. Ben ünlü kümesinde olmayan elemanların tümü filtrelemek

singleVowel :: Maybe String -> Bool 
singleVowel Nothing = False 
singleVowel (Just s) = singleVowel (Just s) = length (nub $ filter (`elem` "aeiouyAEIOUY") s) == 1 

Uyarı: Aşağıdaki benim naif uygulamasıdır. Daha sonra filtrelenmiş listeden kopyaları kaldırmak için nub işlevini kullanarak başka bir geçiş yapın ve listede tam olarak 1 sesli harf olup olmadığına bakın. En kötü durumda, bu çözüm, filtrelenmiş liste için bellek ayırmak zorunda olduğu için O(n) bellek ve saati kullanacaktır.

Şimdi diğer çözümüm için, yinelemeyi kullanmaya karar verdim ve görüldüğü takdirde geçerli sesli harfin kaydını tutmak için her bir özyineleme çağrısı üzerine bir karakter geçtim.

singleVowelFaster :: Maybe String -> Bool 
singleVowelFaster Nothing = False 
singleVowelFaster (Just s) = singleVowelHelper s Nothing 

singleVowelHelper :: String -> Maybe Char -> Bool 
singleVowelHelper [] Nothing = False 
singleVowelHelper [] _ = True 
singleVowelHelper (x:xs) Nothing = if x `elem` "aeiouyAEIOUY" 
    then singleVowelHelper xs (Just x) 
    else singleVowelHelper xs Nothing 
singleVowelHelper (x:xs) (Just c) = 
    (x `elem` "aeiouyAEIOUY" && c == x) && singleVowelHelper xs (Just c) 

Ama 'naif' uygulaması daha hızlı 'akıllı' çözümden çok çalışan bazı garip nedenle

.

o (x elem "aeiouyAEIOUY" && c == x) Haskell beri değerlendirilmektedir olmadığı gerçeği böylece thunks tüm temel durum 'naif' uygulaması yavaş olmasına katkıda böylece ulaşıldığında değerlendirilir, tembel olabilir mi?

Eğer durum böyleyse, o zaman neden bu durumda (x elem "aeiouyAEIOUY" && c == x) elem "aeiouyAEIOUY" && c == x)'u değerlendirdiğimde, işlev değerlendirmesinin benzerliği zorlanırsa neden böyle olur?

İkinci işlevin, O(n) zamanı ile O(1) alan kullanımının olduğunu söyleyebilir miyim?

Answer 1

En basit düzeltme, ilk && aramanızın sırasını ters çevirmek, ucuz numarasını incelemeden önce pahalı elem kontrol edin.

Bu, işlevinizin daha hızlı çalışmasını sağlar ... ancak yine de yanlış olur! Temel olarak, ilk ünlüden sonra, aşağıdaki tüm karakterlerin aynı sesli olduğunu iddia ediyorsunuz; Bunun yerine yapmak istediğin, sesli harflerin tümü'un aynı sesli harf olduğunu iddia eder.

(x == c || not (x `elem`vowels)) && singleVowelHelper xs (Just c) 

Ya, evet, gerçekten ben biraz farklı bütün işlevini yazardı ama yukarıdaki uygulama çalışması için en basit değişimdir: Ben böyle yazardı. İşte daha genel bir yüklem tabanlı fonksiyonu ile başlayan ve daha sonra sesli harflerin için uzmanlaşmış, ben yazardım uygulama görebilirsiniz:

exactlyOne :: Eq a => (a -> Bool) -> [a] -> Bool 
exactlyOne pred [] = False 
exactlyOne pred (x:xs) 
    | pred x = not . any pred . filter (/= x) $ xs 
    | otherwise = exactlyOne pred xs 

exactlyOneVowel :: String -> Bool 
exactlyOneVowel = exactlyOne (`elem` "aeiouAEIOU")