[Haskell] Динамическое программирование

> по ссылке реализации работают ~100 раз медленнее Си

Вы куда-то спешите?

> Вопрос: как быть?

Решать поставленную задачу, используя наиболее подходящий инструмент. Если в ТЗ минимальная скорость работы не указано, то надо забить и заняться чем-нибудь более полезным.

>Вы куда-то спешите?

Хороший конечно ответ. Да вот 100 раз - влоб интерпретируемые языки себя ведут лучше.

>Решать поставленную задачу, используя наиболее подходящий инструмент. Если в ТЗ минимальная скорость работы не указано, то надо забить и заняться чем-нибудь более полезным.

ТЗ? вопрос то как раз и стоит в границах применимости Haskell.

> Если в ТЗ минимальная скорость работы не указано, то надо забить и заняться чем-нибудь более полезным.

В рамочку и на стену. Чем больше хаскеляторов так будет думать, тем меньше этой заразы %)

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

>Предыдущий пост как бэ намекает, что не во всех задачах скорость выполнения важна..

Не спорю. Но вопрос то как раз в другом. Действительно ли Хаскель медленный язык? Вон на shootout очень достойно соревнуется.

Ну и главное, можно ли решить туже задачу на Хаскеле лучше и быстрее?

> Ну и главное, можно ли решить туже задачу на Хаскеле лучше и быстрее?

в имеющейся формулировке -- конечно. Числа представимые упаковками монет образуют конечно порожденную полугруппу. Довольно очевидно, что с какого то (небольшого) N все числа представимы упаковками (потому что числа взаимно просты). То есть достаточно просто предвычислить представимость на отрезке [1,N] и загнать в таблицу.

> То есть достаточно просто предвычислить представимость на отрезке [1,N] и загнать в таблицу.

Возьми с полки пирожок. А теперь рассмотрим случай, когда чисел штук 20, и размером они в несколько миллиардов.

Мне очень лениво, так что приведи, плиз, сишный исходник.

#include <stdio.h>
int main(){
        int n=1000000;
        int f[1000001];
        f[0]=1;
        int i;
        for(i=1;i<=n;i++)
                f[i] = (i>=6 && f[i-6])||(i>=9 && f[i-9])||(i>=20 && f[i-20]);
        printf("%d",f[n]);
}

Сенькс.
Прямой аналог сишного кода:

import Data.Array.IO
import Data.Array.Unboxed
n = 1000000
f bs i = f' [6, 9, 20] where
    f' (n:ns) | i >= n = do {b <- readArray bs $ i - n; if b then return True else f' ns}
    f' _ = return False
main =
    do bs <- newArray_ (0, n) :: IO (IOUArray Int Bool)
       writeArray bs 0 True
       mapM_ (\i -> f bs i >>= writeArray bs i) [1..n]
       b <- readArray bs n
       print b

Вполне идиоматичный хаскель, который раз в пять лучше, чем то, что в вики:

import Data.List bs = True : zipWith3 (\b1 b2 b3 -> b1 || b2 || b3) (replicate 6 False ++ bs) (replicate 9 False ++ bs) (replicate 20 False ++ bs) main = print $ bs !! 1000000

Вот ведь...

import Data.List
bs = True : zipWith3 (\b1 b2 b3 -> b1 || b2 || b3) (replicate 6 False ++ bs) (replicate 9 False ++ bs) (replicate 20 False ++ bs)
main = print $ bs !! 1000000

Угу.... спасибо. А можешь в двух словах, в чем проблема кода в вики?

самого первого предпочтительно.

Почти всё время уходит на сборку мусора (легко выявляется, если запустить собранный бинарник с опциями +RTS -sstderr). Я так полагаю, это многочисленные замыкания - вместо того, чтобы линейно пройтись по массиву от начала до конца, этот код начинает с конца и много раз рекурсивно вызывает себя. А на каждый рекурсивный вызов тратятся дополнительные ресурсы.

сишный код явно плохой. 
вот в предположении, что нужен все же весь массив,
а не последнее число.

#include <stdio.h>
int main(){
    int n=1000000;
    int max=20;
    int f[max+n]; 
    int i;
    for( i=0; i<max; i++)
        f[i]=0;
    f[max]=1;
    for( i=max+1; i<max+n; i++)
       f[i] = f[i-6] || f[i-9] || f[i-20];
    printf("%d",f[n+max]);
}

А если нужно *именно* последнее число (а памяти на весь массив нет!), надо юзать std::deque, которую ручками раз в сколько-то итераций резать с начала.

Либо написать свой deque. Но тут уже хаскельный подход становится хоть как-то интересным, по критерию скорость_работы/время_написания_кода.

www_linux_org_ru

Молодец. Садись, пять. Меня сишный код вообще не интересует.

И вопрос был не столько, как решить эту задачу, сколько как решать задачи динамического программирования на Хаскель?

у тебя явно ошибка. Похоже надо 5 8 19.

> Меня сишный код вообще не интересует.

Будешь сравнивать с плохим сишным кодом -- сделаешь неправильный вывод о быстродействии хаскеля.

> И вопрос был не столько, как решить эту задачу, сколько как решать задачи динамического программирования на Хаскель?

Эффективно -- никак.

> И вопрос был не столько, как решить эту задачу, сколько как решать задачи динамического программирования на Хаскель?

неэффективно и/или с применением кучи изворотливости там, где можно написать прямо

>у тебя явно ошибка. Похоже надо 5 8 19.

С какого это перепоя?

>Будешь сравнивать с плохим сишным кодом -- сделаешь неправильный вывод о быстродействии хаскеля.

Да не такой уж плохой у меня код. Попробуй потестить. Разница с твоим несущественна

> С какого это перепоя?

С такого, что там True в самом начале.

Прав, однако.

> Попробуй потестить. Разница с твоим несущественна

Похоже потому, что скорость обмена с памятью уже достигнута, и быстрее просто невозможно. Если поставить у нас обоих char, разница проявится ( gcc -O3 -g -mtune=pentium4 test1.c )

Но самое главное -- для скоростного и красивого варианта на с++ (а именно, битовый массив) я бы взял именно код по типу мигелевского. Да, написал бы свой зип. Скорость можно поднять еще раз в 30, если с sse4 -- может даже в 100 раз.

> Прав, однако.

у меня там тоже ошибка на 1 в размерности массива. это часто бывает.

подумав, я не нашел, как писать быстро и красиво для битового массива, кроме как через определение своего zip на с++.

Хаскель или нет, но функциональщина тут кажется очень к месту.

>быстрее просто невозможно.

если нужен последний элемент то на С самым быыстрым будет код printf("1");
если нужен весь массив то наверно memset в 1, используя sse кстати весьма быстро можно единицами закидывать ибо начиная с 44 любое число можно представить сочетанием из тройки 6,9,20.