Início / coding / Perguntas / 77922852
Accepted
salferdez
Asked: 2024-02-02 03:25:02 +0800 CST

Melhorando a eficiência no cálculo dos números Stirling

  • 772

Tenho tentado explorar as possibilidades de recursão em Haskell, mas não sei muito sobre como melhorar a eficiência ao enfrentar grandes recursões. Hoje, eu queria fazer uma função que calculasse números de Stirling de segundo tipo:

factorial :: Integer -> Integer
factorial n = helper n 1
    where
        helper 1 a = a
        helper n a = helper (n-1) (a*n)


stirling :: Integer -> Integer -> Integer
stirling n 1 = 1
stirling n 2 = ((2 ^n)- 2) `div` 2
stirling n k
    | k > n      = 0
    | k == n     = 1
    | k == (n-1) = (factorial n) `div` (factorial 2 * (factorial(n-2)))
    | otherwise  = stirling (n-1) (k-1) + k *(stirling (n-1) k)

Tenho tentado criar uma função auxiliar, assim como na definição fatorial, que pudesse evitar a inconveniência da avaliação preguiçosa de Haskell consumir muitos recursos de memória. Quero fazer o mesmo, calculando o produto em cada chamada do

k *(stirling (n-1) k)

recursão, mas não peguei o jeito. Alguma ideia?

PD: O código já funciona bem, mas sou novo em Haskell e ainda não sei quais são as possibilidades. Qualquer melhoria é bem-vinda (embora eu não use nenhuma biblioteca; quero aprender o básico antes de entrar nisso).

performance

2 respostas

  1. Não posso escrever uma explicação muito detalhada agora, mas você pode torná-la um pouco mais rápida:

    • Usando a matemática, simplifique algumas fórmulas
    • Usando deslocamentos de bits em vez de divisão
    • Usando Intpara a entrada em vez deInteger

    Então você entende isso:

    import Data.Bits

stirling :: Int -> Int -> Integer
stirling n 1 = 1
stirling n 2 = (1 `unsafeShiftL` (n - 1)) - 1
stirling n k
    | k > n        = 0
    | k == n       = 1
    | k == (n - 1) = fromIntegral ((n * (n - 1)) `unsafeShiftR` 1)
    | otherwise    = stirling (n - 1) (k - 1) + fromIntegral k * stirling (n - 1) k

    A próxima coisa que eu tentaria é a programação dinâmica para evitar computação redundante.

    E você usa o estilo acumulador para fazer com que uma das chamadas recursivas não finais seja recursiva, como fazem nesta postagem do blog: https://www.haskell.org/ghc/blog/20190728-free-variable-traversals.html

    • 0
  2. Best Answer

    Sua implementação já parece ser bastante eficiente em termos de memória, pelo menos em meus testes. Por exemplo:

    % time ./test salferdez 32 16
1194461517469807833782085
11.50user 0.00system 0:11.48elapsed 100%CPU (0avgtext+0avgdata 8704maxresident)k
0inputs+0outputs (0major+1267minor)pagefaults 0swaps

    Alterar os parâmetros (para cima ou para baixo) não parece alterar muito a residência de 8 MB, então espero que seja o custo mínimo de inicialização de um programa Haskell. Por outro lado, parece bastante lento. Parâmetros ainda um pouco maiores do que os que usei aqui - digamos, o dobro de ambos - demoraram mais do que eu gostaria de esperar. A simples implementação direta da fórmula da Wikipedia parece ser muito mais rápida, mantendo um bom perfil de memória:

    % time ./test dmwit 32 16
1194461517469807833782076
0.00user 0.00system 0:00.01elapsed 16%CPU (0avgtext+0avgdata 4352maxresident)k
0inputs+0outputs (0major+206minor)pagefaults 0swaps
% time ./test dmwit 10000 5000
<snip'd very very long output>
10.62user 0.02system 0:10.62elapsed 100%CPU (0avgtext+0avgdata 16716maxresident)k
0inputs+0outputs (1major+26643minor)pagefaults 0swaps

    (Eu não recompilei entre essas execuções e as anteriores, então você pode ter certeza de que ambos obtivemos o mesmo nível de otimização.)

    Por outro lado, recebo uma resposta um pouco diferente da sua. Talvez você consiga detectar um bug em um ou outro de nosso código. De qualquer forma, aqui está a fórmula da Wikipedia * e aqui está minha opinião sobre sua tradução mais direta:

    stirling n k = sum [(-1)^(k-i)*i^n`div`(product [1..k-i]*product[1..i]) | i <- [0..k]]

    Não se esqueça de compilar -O2e deixar o GHC fazer todo o trabalho sujo de pensar em como torná-lo rápido e com uso eficiente de memória.

    * StackOverflow possui um mecanismo para incluir a imagem diretamente, em vez de vinculá-la, mas não parece estar funcionando para mim. Não sei por que!

    • 0

relate perguntas