Как эффективно выполнить суммирование обратных рядов в haskell?

haskell

90 просмотра

3 ответа

Это код, который я пытаюсь конвертировать в haskell. Но неизменность создает проблему. Как сделать расчет без изменяемых переменных. Создание списка [1..20]и его отображение не похоже на экономию пространства. Есть ли уловка или техника, чтобы избежать неизменности?

int main()
{
    int i,n=0;
    double sum= 0.0;
    for ( i=1; i<20; ++i )
    {
        n += i;
        sum = 1 / (double) n;
    }
    printf("The sum is: %lf",sum);
    return 0;
}
Автор: GauravP Источник Размещён: 08.11.2019 11:21

Ответы (3)


5 плюса

Решение

Используйте scanl1для генерации вашего списка ns:

> scanl1 (+) $ [1..19]
[1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190]

Отсюда легко вычислить обратное

> map (1/) . scanl1 (+) $ [1..19]
[1.0,0.3333333333333333,0.16666666666666666, ...]

и сложить их:

> sum . map (1/) . scanl1 (+) $ [1..19]
1.8999999999999997

Хотя код на Haskell рассматривает значения как неизменяемые, и кажется, что вы генерируете несколько промежуточных списков, компилятор достаточно умен, чтобы генерировать эффективный исполняемый код.

Автор: chepner Размещён: 20.08.2016 02:43

4 плюса

Вы можете проверить код, который генерирует GHC -ddump-asm.

Скомпилируйте эту программу:

main = print $ 1.0 / fromIntegral (sum [(1::Int)..12345])

с участием:

$ ghc -O2 Main.hs -ddump-asm > asm-output

Затем посмотрите asm-output, найдите 12345и вы увидите этот цикл:

_c47b:
        addq %r14,%rsi
        incq %r14
_c476:
        cmpq $12345,%r14
        jne _c47b

Это показывает, что список на [1..12345]самом деле не создан.

Обновить

Кажется, вы намеревались суммировать обратные значения треугольных чисел, то есть 1/1 + 1/3 + 1/6 + ... То есть вы намеревались написать:

sum += 1.0 / (double) n;

Это может быть выражено в Haskell как:

main = print $ sum $ map (\x -> 1 / (fromIntegral x)) $ scanl (+) 1 [(2::Int)..12345]

Исследуя сгенерированную сборку, мы снова видим, что промежуточный список не создается:

_c4ao:
        cvtsi2sdq %rsi,%xmm0
        movsd _n4aP(%rip),%xmm2
        divsd %xmm0,%xmm2
        addsd %xmm2,%xmm1
        incq %r14
_c4ad:
        addq %r14,%rsi
        cmpq $12345,%r14
        jne _c4ao

Вот %r14счетчик iв вашем C-коде, %rsiэто переменная nи %xmm1аккумулятор sum.

Автор: ErikR Размещён: 20.08.2016 01:44

3 плюса

Для того, чтобы временно избежать неизменность вы можете использовать в STмонаду .

Однако в этом нет необходимости. В следующем выражении все будет оптимизировано компилятором благодаря Stream Fusion :

sum (map (\n -> 1 / fromIntegral n) [1..20])
Автор: Nikita Volkov Размещён: 20.08.2016 01:37
Вопросы из категории :
32x32