Медленный Хаскель (... и быстрый Питон!)

psihodog

Я тут решил написать решение вот этой задачи на новом для меня языке под названием Haskell и вот что у меня получилось:
import qualified Data.Map as Map 



readInts :: String -> [Int]

readInts = map read . words



addFruit (balance, taste) balanceToMaxTaste = Map.unionWith max balanceToMaxTaste $

    Map.fromList $ map (\(b, t) -> (balance + b, taste + t $ Map.toList balanceToMaxTaste



solve [n,k] as bs = if maxTaste > 0 then maxTaste else -1

    where maxTaste = (Map.!) maxTastes 0

          maxTastes = foldr addFruit (Map.singleton 0 0) balanceTastes

          balanceTastes = [(a - b*k, a) | (a, b) <- zip as bs]



main = do

    nk <- getLine

    as <- getLine

    bs <- getLine

    print $ solve (readInts nk) (readInts as) (readInts bs)

Для сравнения, то же решение на Python:
from sys import stdin as cin

from collections import defaultdict



def main:

    n,k = map(int, next(cin).split

    a = map(int, next(cin).split

    b = map(int, next(cin).split

    b = [ x*k for x in b ]



    b2t = defaultdict(lambda:0, { 0 : 0 })

    for t,c in zip(a, b):

        bal = t - c

        b2t2 = b2t.copy

        for ba, ta in b2t.iteritems:

            b2t2[ba + bal] = max(b2t2[ba + bal], ta + t)

        b2t = b2t2



    return b2t[0] or -1



print main

Взял последний тест:
$ cat 20

88 10

6 64 43 1 1 1 8 15 39 1 95 2 1 80 36 40 25 2 52 24 29 26 16 45 96 99 1 91 16 97 67 1 39 91 1 41 72 67 93 84 1 12 67 53 26 1 14 39 94 92 28 75 10 16 81 97 77 22 1 1 41 90 51 49 90 74 5 61 1 45 88 1 40 7 4 59 16 33 6 4 92 1 38 20 4 53 10 80

70 45 1 73 52 1 20 78 68 98 1 95 2 61 1 56 5 70 92 1 99 52 84 87 87 1 76 51 30 20 1 12 4 52 80 63 33 1 1 3 1 12 43 29 51 64 1 82 6 81 1 15 93 74 11 1 41 89 40 40 20 6 80 42 1 1 1 83 3 69 42 2 55 37 7 1 1 1 43 79 79 50 79 68 52 1 77 59

Скормил его программе на хаскеле и неприятно удивился:
$ time ./3.map < 20

1750



real    0m3.817s

user    0m3.592s

sys     0m0.176s

ибо решение на питоне работает в 3 раза быстрее:
$ time python 3.py < 20

1750



real    0m1.149s

user    0m1.096s

sys     0m0.024s

ну ладно... меняем Data.Map на Data.Map.Strict:
$ time ./3.map.strict < 20                                                                                                                                                    

1750



real    0m2.104s

user    0m2.064s

sys     0m0.016s

на Data.HashMap.Strict:
$ time ./3.hashmap.strict < 20

1750



real    0m2.005s

user    0m1.948s

sys     0m0.044s

получше, конечно, но всё равно хуже стандартного питона в два раза!
а если уж PyPy взять:
$ time pypy 3.py < 20                                                                                                                                                         

1750



real    0m0.587s

user    0m0.524s

sys     0m0.040s

А я, если честно ожидал приличного прироста в скорости при переходе на хаскель.
В общем, прошу показать, где я не правильно этот хаскель готовлю.

apl13

Компилировал с каким -O?

apl13

(a, b) <- zip as bs
А нельзя a <- as, b <- bs?

stm5872449

А нельзя a <- as, b <- bs?
Это даст всевозможные сочетания a и b, zip работает не так.

apl13

А, ну да.
balanceTastes = zipWith (\a b -> (a - b * k, a as bs

apl13

Map.fromList $ map (\(b, t) -> (balance + b, taste + t $ Map.toList
:aaa:

psihodog

без -O, я когда пост написал, скомпилировал с -O2, лучший вариант стал ~1.5 секунды, что, конечно получше, но тоже полный фейл по сравнению с питоном.

psihodog

заменил на
addFruit (balance, taste) balanceToMaxTaste = Map.unionWith max balanceToMaxTaste $

    Map.map +) taste) $ Map.mapKeysMonotonic +) balance) balanceToMaxTaste

но это работает только на упорядоченных мапах и там (с -O2) дало улучшение с 1.6 с до 1.5 с
в общем, копейки... :(
upd: хотя, позволило пройти TLE на codeforces :)

psihodog

так красивее, да, но на производительность никак не влияет, bottleneck тут addFruit — шаг динамического программирования.

stm5872449

Я в этом вашем хаскеле нуб, но вот так не быстрее?
 


import Data.List

import Data.Maybe



readInts :: String -> [Int]

readInts = map read . words



merge xk,xv):xs) yk,yv):ys)

	| xk < yk = (xk,xv) : merge xs y 

	| xk == yk = (xk, max xv yv) : merge xs ys

	| xk > yk = (yk,yv) : merge x ys 

merge xs ys = xs ++ ys



addFruit (balance, taste) acc = merge acc acc'

    where acc' = map (\(b, t) -> (balance + b, taste + t acc



solve [n,k] as bs = if snd (fromMaybe (0,0) maxTaste) > 0 then snd $ fromJust maxTaste else -1

    where maxTaste = find (\(b,t) -> b == 0) maxTastes 

          maxTastes = foldr addFruit [(0, 0)] balanceTastes

          balanceTastes = [(a - b*k, a) | (a, b) <- zip as bs]



main = do

    nk <- getLine

    as <- getLine

    bs <- getLine

    print $ solve (readInts nk) (readInts as) (readInts bs)

Учитывая, сколько твой addFruit всего аллоцирует, неудивительно, что тормозит.

Maurog

Для сравнения, то же решение на Python:
я не понял, почему решение "то же" ? в питоновском решении не вижу функцию addFruit ! что сравниваем и чему удивляемся?

yroslavasako

что сравниваем и чему удивляемся?
сравниваем решения в том стиле, который характерен для языка. Программист на фортране может писать на фортране на любом языке, но тогда сравнивать языки будет не интересно, потому что вместо свойств языка будет измеряться качество реализации фортрана.
Вот ты берёшь книжку "learning haskell for greater good" и методично следуешь советам оттуда при составлении решения. Потом берёшь книжку "программировать как питономатик" и используешь рекомендации относительно питоновского кода и составляешь решение. Потом сравниваешь эффективность. Это и будет практическая эффективность языков.
А так, конечно, можно написать быструю либу на си, и через нативный интерфейс подгрузить её и в cpython, и в ghc, только смысл замера будет нулевой. Почти нулевые отличия по времени исполнения покажут почти нулевые отличия питона от хаскеля, когда ты используешь си для программирования обоих.

Maurog

сравниваем решения в том стиле, который характерен для языка.
в данном случае имеем другое:
на новом для меня языке под названием Haskell
чтобы составить решение, характерное для Хаскеля, нужно очень сильно перевернуть сознание (если оно повернуто в другую сторону :grin: )
Вот ты берёшь книжку "learning haskell for greater good" и методично следуешь советам оттуда при составлении решения. Потом берёшь книжку "программировать как питономатик" и используешь рекомендации относительно питоновского кода и составляешь решение. Потом сравниваешь эффективность. Это и будет практическая эффективность языков.
ничего общего с практической эффективностью здесь не будет
код, написанный на языке после прочтения книги "язык Х для чайников", не имеет никакой пользы и его нельзя использовать для набросов типа "Х быстрее Y"

psihodog

увы...
$ time ./3a < 20                                                                                                                                                              

1750



real    0m1.958s

user    0m1.864s

sys     0m0.084s

Вообще, по сути это то же самое, что решение с деревянной мапой: там тоже за линейное время "сдвигаются" ключи и значения у дерева, а потом за линейное же время мержатся два дерева.

psihodog

ну, она в цикле, вынес её отдельно:
from sys import stdin as cin

from collections import defaultdict



def addFruit(b2t, bal, t):

    b2t2 = b2t.copy

    for ba, ta in b2t.iteritems:

        b2t2[ba + bal] = max(b2t2[ba + bal], ta + t)

    return b2t2



def main:

    n,k = map(int, next(cin).split

    a = map(int, next(cin).split

    b = map(int, next(cin).split

    b = [ x*k for x in b ]



    b2t = defaultdict(lambda:0, { 0 : 0 })

    for t,c in zip(a, b):

        b2t = addFruit(b2t, t - c, t)



    return b2t[0] or -1



print main

yroslavasako

странно. Си для чайников мне вполне хватало на олимпиадах.

apl13

сравниваем решения в том стиле, который характерен для языка. Вот ты берёшь книжку "learning haskell for greater good" и методично следуешь советам оттуда при составлении решения.
:jaw_drop: :hair:

psihodog

код, написанный на языке после прочтения книги "язык Х для чайников"
я её ещё не дочитал :grin:
не имеет никакой пользы и его нельзя использовать для набросов типа "Х быстрее Y"
я не хочу набросить, наоборот хочу разобраться.
в моём понимании, ghc должен был там всё очень хорошо соптимизировать, так что чуть ли не на Сях написано получится.
ну уж точно не проигрывать питону, про который я привык думать, что он очень тормозной.
и решение у меня алгоритмически такое же как на питоне, и скомпилировано всё уже, и соптмизировано, и про типы всё знает, но вот почему получается тормознее — это я и пытаюсь понять.

pilot

в моём понимании, ghc должен был там всё очень хорошо соптимизировать, так что чуть ли не на Сях написано получится.
ну уж точно не проигрывать питону, про который я привык думать, что он очень тормозной.
Как в твоем понимании PyPy может быть быстрее CPython? :o

Maurog

и решение у меня алгоритмически такое же как на питоне
в этом и был мой изначальный вопрос. где тут одинаковые решения? я не распознал :(

Maurog

вынес её отдельно
теперь смотрим пристально в addFruit на питоне и на хаскеле и пытаемся найти десять отличий:
в питоне делаем поиски логарифмические в мапе, а в хаскеле превращает дерево в список, мурыжим его и снова упаковываем в дерево
мне кажется это кардинально разными алгоритмами и последнее с точки зрения сложности должно жрать больше времени
зззз, и вообще, это разные addFruit, интерфейс разный, делают они немного разные вещи

psihodog

Как в твоем понимании PyPy может быть быстрее CPython?
ну как, JIT и всё такое... да ты на время исполнения посмотри.
psyco для CPython'а не поддерживается, так что всё понятно.

psihodog

еперь смотрим пристально в addFruit на питоне и на хаскеле и пытаемся найти десять отличий:
в питоне делаем поиски логарифмические в мапе, а в хаскеле превращает дерево в список, мурыжим его и снова упаковываем в дерево
в питоне поиски O(1 вроде, там же хэши везде.
хаскель же ленивый, я надеялся, что он всё это соптимизирует.
и в хаскеле я попробовал два варианта:
1. с хэшмапой, хэш один остаётся на месте, а второй строится всё равно с нуля, потом они мержатся, по идее оверхед не должен быть очень большой.
тут, конечно, было бы быстрее иметь функцию, unionWith, которая вторым параметром list принимает, но кто виноват, что её нет?
2. с деревянной мапой, смотри второй вариант, там дерево фиксится без распаковки, а потом два дерева мержатся в одно. всё это, как я себе представляю довольно быстро. или вариант от — примерно то же самое.

psihodog

зззз, и вообще, это разные addFruit, интерфейс разный, делают они немного разные вещи
ну извиняйте, в хаскеле иммутабл структуры, там в принципе нельзя сделать того что можно в питоне.
ну так это ограничение не с неба спустилось, предполагалось (я полагаю что язык будет эффективным при выбранном дизайне.
вот я переписал питоно-код в ужасном стиле:
from sys import stdin as cin

from itertools import chain



def addFruit(b2t, bal, tst):

    b2t2 = ba + bal, ta + tst) for (ba,ta) in b2t.iteritems

    res = {}

    for b,t in chain(b2t.iteritems b2t2):

        try:

            res[b] = max(res[b], t)

        except:

            res[b] = t

            

    return res

    

    

def main:

    n,k = map(int, next(cin).split

    a = map(int, next(cin).split

    b = map(int, next(cin).split

    b = [ x*k for x in b ]

    

    b2t = { 0 : 0 }

    for t,c in zip(a, b):

        b2t = addFruit(b2t, t - c, t)

        

    return b2t[0] or -1

    

print main

Да, на питоне он стал жутко тормозной, а вот с PyPy до сих пор работает на недосягаемой для Хаскеля скорости:
$ time pypy 3b.py < 20                                                                                                                                                        

1750



real    0m0.641s

user    0m0.560s

sys     0m0.064s

alfadred

Ну вообще-то IO - это часть Haskell, и если структура данных эффективно реализуется только с помощью IO, то почему бы это не использовать.
Кстати, Data.HashMap очень неудачно назван, потому что он тоже дерево (IntMap (Map k v
У меня получились такие результаты(a - исходный вариант, b - Data.IntMap.Strict, c - Data.HashTable, IO, d - BasicHashTable из пакета hashtables)
a

1750



real    0m1.692s

user    0m1.622s

sys     0m0.064s

---



b

1750



real    0m0.589s

user    0m0.577s

sys     0m0.011s

---



c

1750



real    0m0.496s

user    0m0.484s

sys     0m0.008s

---



d

1750



real    0m0.379s

user    0m0.370s

sys     0m0.009s

Код:
=====

b.hs

=====

import qualified Data.IntMap.Strict as Map 



readInts :: String -> [Int]

readInts = map read . words



addFruit (balance, taste) balanceToMaxTaste = Map.unionWith max balanceToMaxTaste $

    Map.mapKeysMonotonic (+balance) $ Map.map (+taste) balanceToMaxTaste



solve [n,k] as bs = if maxTaste > 0 then maxTaste else -1

    where maxTaste = (Map.!) maxTastes 0

          maxTastes = foldr addFruit (Map.singleton 0 0) balanceTastes

          balanceTastes = [(a - b*k, a) | (a, b) <- zip as bs]



main = do

    nk <- getLine

    as <- getLine

    bs <- getLine

    print $ solve (readInts nk) (readInts as) (readInts bs)



=====

c.hs

=====

import qualified Data.HashTable as Hash

import Control.Monad

import Data.Maybe



readInts :: String -> [Int]

readInts = map read . words



updateMax dict (k, v) = Hash.lookup dict k >>= maybe (Hash.insert dict k v)

    (\old -> if v > old then void $ Hash.update dict k v else return 



addFruit dict (balance, taste) = do

    list <- Hash.toList dict

    mapM_ (\(b, t) -> updateMax dict (b + balance, t + taste list

    return dict;



solve [n,k] as bs = do

    dict <- Hash.new (==) Hash.hashInt

    Hash.insert dict 0 0

    dict <- foldM addFruit dict [(a - b * k, a) | (a, b) <- zip as bs]

    Hash.lookup dict 0 >>= (return . fromMaybe (-1



main = do

    nk <- getLine

    as <- getLine

    bs <- getLine

    print =<< solve (readInts nk) (readInts as) (readInts bs)



=====

d.hs

=====

import qualified Data.HashTable.IO as Hash

import Control.Monad

import Data.Maybe



readInts :: String -> [Int]

readInts = map read . words



updateMax dict (k, v) = Hash.lookup dict k >>= maybe (Hash.insert dict k v)

    (\old -> if v > old then Hash.insert dict k v else return 



addFruit dict (balance, taste) = do

    list <- Hash.toList dict

    mapM_ (\(b, t) -> updateMax dict (b + balance, t + taste list

    return dict;



solve [n,k] as bs = do

    dict <- Hash.new :: IO (Hash.BasicHashTable Int Int)

    Hash.insert dict 0 0

    dict <- foldM addFruit dict [(a - b * k, a) | (a, b) <- zip as bs]

    Hash.lookup dict 0 >>= (return . fromMaybe (-1



main = do

    nk <- getLine

    as <- getLine

    bs <- getLine

    print =<< solve (readInts nk) (readInts as) (readInts bs)

yroslavasako

Ну вообще-то IO - это часть Haskell,
Ну если бы я хотел IO, я бы просто не брал хаскель. Не на IO меня заманивали мануалы. Найди хоть один, где IO рекомендуется для statefull вычислений, а не для исключительно вввода-вывода. Если бы все мануалы честно говорили, без IO хаскель не юзабелен, то он растерял бы значительную часть своей популярности.
Нативные интерфейсы - это тоже часть и хаскеля, и cpython, но это же не значит, что мы должны написать модуль на сях, подключить нативно и радоваться производительности. Тогда проще сразу на сях писать.

alfadred

Если бы все мануалы честно говорили, без IO хаскель не юзабелен, то он растерял бы значительную часть своей популярности.
Отсутствие хэш-таблиц - это не неюзабельность. Лично мне всегда хватало Data.Map/Data.IntMap, а там, где хэш-таблицы становятся эффективнее, можно уже брать базу данных или специализированную сишную либу.
Нативные интерфейсы - это тоже часть и хаскеля, и cpython, но это же не значит, что мы должны написать модуль на сях, подключить нативно и радоваться производительности. Тогда проще сразу на сях писать.
Не знаю, я пробовал - мне кажется, получается удобнее, чем на сях.

psihodog

Ну вообще-то IO - это часть Haskell, и если структура данных эффективно реализуется только с помощью IO, то почему бы это не использовать.
до IO я ещё не дочитал =)
но код выглядит не так круто как оригинальное решение.
как-то императивненько получается
Кстати, Data.HashMap очень неудачно назван, потому что он тоже дерево (IntMap (Map k v
Я брал unordered-containers, написано, что честный хэш-мэп.
У меня получились такие результаты(a - исходный вариант, b - Data.IntMap.Strict, c - Data.HashTable, IO, d - BasicHashTable из пакета hashtables)
Спасибо! А можешь, плз, ещё для масштаба померять питоновское решение, желательно с PyPy.

apl13

хаскель же ленивый, я надеялся, что он всё это соптимизирует.
Лень не про это. :]
Лень дает ускорение в других смыслах.
Если тебя удовлетворяет голова списка, тебе незачем шерстить его хвост. :]
Принцип Ходжи Насреддина. :]

stm5872449

чтобы составить решение, характерное для Хаскеля, нужно очень сильно перевернуть сознание
И каково подобное решение для данной задачи? :)

psihodog

что-то я стормозил, я же для масштаба могу твои решения у себя запустить.
итак (компилировал -O2):
$ time ./3d < 20

1750



real    0m1.105s

user    0m1.064s

sys     0m0.016s



$ time ./3c < 20

1750



real    0m1.350s

user    0m1.316s

sys     0m0.020s



$ time pypy 3.py < 20

1750



real    0m0.579s

user    0m0.512s

sys     0m0.056s

Так что, увы. Я, вот честно скажу, расстроен.

stm5872449

Так что, увы. Я, вот честно скажу, расстроен.
Ну, не надо было покупаться на рекламу. :)
Я так понял, что для эффективного динамического программирования хранение промежуточных результатов надо делать либо с помощью ленивых структур/мемоизации (см. фибоначчи либо используя монаду State, которая внутри юзает мутабельность.

Maurog

итак (компилировал -O2):
вот я себе поставил pypy + haskell и получил другие результаты
D:\cygwin\bin\time.exe ./d.exe 0<20
1750
system 0:00.40
D:\cygwin\bin\time.exe D:\pypy-2.2.1\pypy.exe 3b.py 0<20
1750
system 0:00.68
убогий time в цигвине =\
сделал замер другой прогой:
>ptime.exe d.exe 0<20
=== d.exe ===
1750
Execution time: 0.436 s
-----------------------------
ptime.exe D:\pypy-2.2.1\pypy.exe 3b.py 0<20
=== D:\pypy-2.2.1\pypy.exe 3b.py ===
1750
Execution time: 0.699 s
есть идеи что я делаю не так?

psihodog

а ты питоновский код какой брал?
из оригинального поста, или тот который я потом специально "ухудшил", чтобы он походил на мой же хаскелевский код?

psihodog

Запустил на стареньком FreeBSD-шном сервере (до этого запускал на своей рабочей линуксовой машине получил


$ time pypy 3.py < 20

1750



real    0m0.709s

user    0m0.669s

sys     0m0.039s



$ time ./d < 20

1750



real    0m0.826s

user    0m0.809s

sys     0m0.016s

тут они почти сравнялись, но всё равно пипи чуть быстрее.
ну, в общем, скорее всего, тут различие в оптимизациях под разные ОСи/процессоры.

Maurog

а ты питоновский код какой брал?
как ты выше заметил, разницы для pypy нет
ptime.exe D:\pypy-2.2.1\pypy.exe 3b_orig.py 0<20
1750
Execution time: 0.709 s
------------------------------------------
ptime.exe D:\pypy-2.2.1\pypy.exe 3b.py 0<20
1750
Execution time: 0.699 s

Maurog

тут различие в оптимизациях
а дай-ка версию ghc
моя:
>ghc -v
Glasgow Haskell Compiler, Version 7.6.3, stage 2 booted by GHC version 7.4.1

psihodog

рабочий линукс:
$ ghc -v

Glasgow Haskell Compiler, Version 7.4.1, stage 2 booted by GHC version 7.4.1

FreeBSD сервер:
$ ghc -v

Glasgow Haskell Compiler, Version 7.6.3, stage 2 booted by GHC version 7.4.1
Оставить комментарий
Имя или ник:
Комментарий: