haskell - Filtro de referencia y partición

ghc criterion

Question

Estaba probando el rendimiento de la función de partition para listas y obtuve algunos resultados extraños, creo.

Tenemos esa partition p xs == (filter p xs, filter (not . p) xs) pero elegimos la primera implementación porque solo realiza un recorrido único sobre la lista. Sin embargo, los resultados que obtuve dicen que tal vez sea mejor usar la implementación que usa dos recorridos.

Aquí está el código mínimo que muestra lo que estoy viendo

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
      ]
      ]

Realicé las pruebas tanto con -O como sin ellas, y las dos veces obtengo que el doble recorrido es mejor.

Estoy usando ghc-7.10.3 con criterion-1.1.1.0

Mis preguntas son:

• ¿Se espera esto?

• ¿Estoy usando Criterion correctamente? Sé que la pereza puede ser complicada y (filter p xs, filter (not . p) xs) solo hará dos recorridos si se usan ambos elementos de la tupla.

• ¿Esto tiene que ver con la forma en que se manejan las listas en Haskell?

¡Muchas gracias!

Answer 1

No hay respuesta en blanco o negro a la pregunta. Para analizar el problema considere el siguiente código:

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."

No utilizo Criterion para tener un mejor control sobre el orden de evaluación. Para obtener los tiempos, uso la opción de tiempo de ejecución +RTS -s . Los diferentes casos de prueba se ejecutan utilizando diferentes opciones de línea de comando. La primera opción de línea de comando define para qué porcentaje de los datos se mantiene el predicado. La segunda opción de línea de comando elige entre diferentes pruebas.

Las pruebas distinguen dos casos:

1. Los datos se generan perezosamente ( partition segundo argumento o mypartition ).
2. Los datos ya están completamente evaluados en la memoria (2do argumento partition-ds o mypartition-ds ).

El resultado de la partición siempre se evalúa de izquierda a derecha, es decir, comienza con la lista que contiene todos los elementos para los que se mantiene el predicado.

En el caso 1, la partition tiene la ventaja de que los elementos de la primera lista resultante se descartan antes de que se produzcan todos los elementos de la lista de entrada. El caso 1 es especialmente bueno si el predicado coincide con muchos elementos, es decir, el primer argumento de la línea de comando es grande.

En el caso 2, la partition no puede aprovechar esta ventaja, ya que todos los elementos ya están en la memoria.

Para mypartition , en cualquier caso, todos los elementos se mantienen en la memoria después de que se evalúa la primera lista resultante, porque se necesitan nuevamente para calcular la segunda lista resultante. Por lo tanto, no hay mucha diferencia entre los dos casos.

Parece que, cuanto más memoria se usa, más difícil es la recolección de basura. Por lo tanto, la partition es adecuada si el predicado coincide con muchos elementos y se usa la variante perezosa.

A la inversa, si el predicado no coincide con muchos elementos o todos los elementos ya están en la memoria, mypartition funciona mejor, ya que su recursión no trata con los pares en contraste con la partition .

La pregunta de "El patrón irrefutable no pierde memoria en la recursión, pero ¿por qué? ”Podría dar más información sobre el manejo de los pares en la recursión de la partition .