Filtr analizy porównawczej i partycja

Question

Testowałem wydajność funkcji partition dla list i otrzymałem pewne dziwne wyniki, jak sądzę.

Mamy tę partition p xs == (filter p xs, filter (not . p) xs), ale wybraliśmy pierwszą implementację, ponieważ wykonuje tylko jedno przejście na liście. Jednak wyniki, które otrzymałem, mówią, że być może lepiej byłoby użyć implementacji, która używa dwóch przejazdów.

Oto minimalny kod, który pokazuje, co widzę

import Criterion.Main 
import System.Random 
import Data.List (partition) 

mypartition :: (a -> Bool) -> [a] -> ([a],[a]) 
mypartition p l = (filter p l, filter (not . p) l) 



randList :: RandomGen g => g -> Integer -> [Integer] 
randList gen 0 = [] 
randList gen n = x:xs 
    where 
    (x, gen') = random gen 
    xs = randList gen' (n - 1) 

main = do 
    gen <- getStdGen 
    let arg10000000 = randList gen 10000000 
    defaultMain [ 
     bgroup "filters -- split list in half " [ 
     bench "partition100"   $ nf (partition (>= 50)) arg10000000 
     , bench "mypartition100"  $ nf (mypartition (>= 50)) arg10000000 
     ] 
     ] 

Pobiegłem testy zarówno z -O i bez niego i za każdym razem dostaję że podwójne przechodzenia przez to lepiej.

Używam ghc-7.10.3 z criterion-1.1.1.0

moje pytania są następujące:

• Czy to prawidłowo?

• Czy używam kryterium poprawnie? Wiem, że lenistwo może być trudne i (filter p xs, filter (not . p) xs) wykona tylko dwa przejazdy, jeśli użyte zostaną oba elementy krotki.

• Czy ma to coś wspólnego ze sposobem obsługi list w Haskell?

Wielkie dzięki!

Answer 1

Nie ma czarno-białej odpowiedzi na to pytanie. Aby przeanalizować problem, rozważ następujący kod:

import Control.DeepSeq 
import Data.List (partition) 
import System.Environment (getArgs) 


mypartition :: (a -> Bool) -> [a] -> ([a],[a]) 
mypartition p l = (filter p l, filter (not . p) l) 


main :: IO() 
main = do 
    let cnt = 10000000 
     xs = take cnt $ concat $ repeat [1 .. 100 :: Int] 
    args <- getArgs 
    putStrLn $ unwords $ "Args:" : args 
    case args of 
    [percent, fun] 
     -> let p = (read percent >=) 
     in case fun of 
      "partition"  ->    print $ rnf $ partition p xs 
      "mypartition" ->    print $ rnf $ mypartition p xs 
      "partition-ds" -> deepseq xs $ print $ rnf $ partition p xs 
      "mypartition-ds" -> deepseq xs $ print $ rnf $ mypartition p xs 
      _ -> err 
    _ -> err 
    where 
    err = putStrLn "Sorry, I do not understand." 

Nie używam kryterium, aby mieć lepszą kontrolę nad kolejnością oceny. Aby uzyskać czas, używam opcji środowiska wykonawczego +RTS -s. Różne przypadki testowe są wykonywane przy użyciu różnych opcji wiersza poleceń. Pierwsza opcja wiersza poleceń określa, dla którego procent danych przechowywany jest predykat. Druga opcja linii poleceń wybiera między różnymi testami.

Testy rozróżnić dwa przypadki:

1. Dane są generowane leniwie (2 argumentów partition lub mypartition).
2. Dane są już w pełni wyliczone w pamięci (drugi argument partition-ds lub mypartition-ds).

Wynikiem podziału jest zawsze obliczane od lewej do prawej, czyli począwszy od listy, która zawiera wszystkie elementy, dla których orzeczenie trzyma.

W przypadku, gdy 1 partition ma tę zaletę, że elementy pierwszej listy wynikowej są odrzucane, zanim wszystkie elementy listy wejściowej zostały nawet utworzone. Przypadek 1 jest szczególnie dobry, jeśli predykat pasuje do wielu elementów, tj. Pierwszy argument linii poleceń jest duży.

W przypadku 2, partition nie można odtworzyć tej przewagi, ponieważ wszystkie elementy są już w pamięci.

Dla mypartition, w każdym przypadku wszystkie elementy są przechowywane w pamięci po oszacowaniu pierwszej wynikowej listy, ponieważ są one potrzebne ponownie do obliczenia drugiej wynikowej listy. Dlatego nie ma dużej różnicy między tymi dwoma przypadkami.

Wygląda na to, że im więcej pamięci zostanie zużyte, tym trudniej zbierze śmieci. Dlatego też partition jest dobrze dopasowany, jeśli predykat pasuje do wielu elementów i używany jest leniwy wariant.

Odwrotnie, jeśli predykat nie pasuje do wielu elementów lub wszystkie elementy są już w pamięci, to mypartition działa lepiej, ponieważ rekurencja nie zajmuje par w przeciwieństwie do partition.

Pytanie Stackoverflow "Irrefutable pattern does not leak memory in recursion, but why?" może dać więcej wglądu w obsługę par w rekursji partition.