Showing posts with label haskell. Show all posts
Showing posts with label haskell. Show all posts

Wednesday, August 3, 2011

Kharkov DOU Hackathon - отчёт об участии

A hackathon, a hacker neologism, is an event when programmers meet to do collaborative computer programming(c) wiki
Вышеобозначеный хакатон проходил в Харькове 30-31 августа в соревновательном виде. За сутки нужно было написать что-нибудь интересное и команда Von Neumann Architecture в составе двух человек приняла вызов. В качестве задачи мы выбрали портирование Pascal игрушки 1994-го года на HTML5/JS посредством написания Haskell транслятора. Исходники здесь. Полноценный отчёт можно почитать здесь. Также можно посмотреть онлайн демку, демка доделывалась уже после Хакатона. Цитата:
Повторяю, вы видите как работает интерпретатор многопоточного (yield) Javascript, сконвертированного (via Haskell) из Turbo Pascal, сам интерпретатор Javascript-а "Rhino" написан на Java, портирован (via gwt + ножницы) в Javascript.
Внизу работающая программа, проверено под Chrome, Mozilla. Если в опере загрузить ее отладчик DragonFly, то там отчего-то тоже начинает работать.

Sunday, September 27, 2009

Мини-отчёт об участии в GCJ

GCJ(Google Code Jam) - контест по спортивному программированию, который проводит всем известная компания Google. Контест не командный, международный, проводится в онлайн.
В этому году участвовал в первый раз, основные результаты таковы: остановился на втором раунде, в третий не прошёл.

Впечатления

Сумбурные. Участие в ICFPC и в Sapka рождает совсем другие эмоции. GCJ более напряженный, задачи значительно меньше по объему, но труднее, временные рамки куда жестче. Однако задачи GCJ отличаются и от тех, что встречаются на ACMовских олимпиадах. Большинство задач действительно имеют очень короткие и очень красивые решения, каждую из них действительно можно решить за отведенное время, если уловить какую-то важную мысль.

Выводы

  • Неожиданно для себя обнаружил доказательство тезиса "Разные ЯП - для разных задач". Решал задачи на Python(основной язык), Haskell и С++ - действительно, иногда тот или иной язык куда лучше подходил для решения определенной задачи
  • Фан можно получать и от простых задачек, не обязательно рулить спутниками или писать AI для bombermanа. Зря я почти забросил теорию - теперь сыплюсь на стандартных алгоритмах и мне очень стыдно
  • Нужно обязательно участвовать в следующих GCJ. Он совсем не напрягает и занимает куда меньше времени, чем многодневные командные состязания

Интересная ссылкa

Недавно мне подбросили ссылку на еще один контест - Hugi Size Coding Competition Series(hugi-compo), который кардинально отличается от всех, в которых я доселе участвовал. Именно этим он и привлекателен, хоть я и не обладаю достаточной квалификацией для удачных выступлений(контест посвящен ассемблерной оптимизации). Возможно, кого-нибудь заинтересует такое нестандартное соревнование. Спасибо за внимание!

Wednesday, May 13, 2009

C++ 0x уже сегодня?

Вступление

С++ 0x - кодовое имя грядущего стандарта С++, который несет в себе огромное количество изменений. Если и до этого язык С++ был одним из самых нагруженных и сложных, то с приходом нового стандарта он может вообще быть погребен под собственной массой. Но случится ли это? Ответу на этот вопрос и посвящен данный пост.

Основная часть

На BoostCon было точно подмечено, что "С++ 0x" нужно читать как "C++ 0A","C++0B", etc, однако многое можно попробовать уже сейчас.
Для этого я собрал gcc из cxx0x-lambdas-branch, который, по-моему, сейчас максимально близок к C++0x (бранч периодически мержится с основной веткой, но в этом бранче полностью отстутствуют Concepts). О том, как собирать - смотрите ссылки ниже.
Итак, имеем:
$ bin/gcc --version
gcc (GCC) 4.5.0 20090421 (experimental)
Copyright (C) 2009 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Попробуем что-нибудь написать:
#include <iostream>
#include <vector>
#include <algorithm>


int main()
{
std::vector<int> v = {1,2,3,4,5};
std::vector<std::pair<int,int>> v2;
std::transform(v.begin(),
v.end(),
std::back_inserter(v2),
[](int x){return std::pair<int,int>(x, x*x);});
for_each(v2.begin(),v2.end(),[](std::pair<int,int> x){std::cout<<"("<<x.first<<","<<x.second<<")";});
int s = 0;
for_each(v.begin(),v.end(),[&s](int x){s+=x;});
std::cout<<"\nResult:"<<s<<"\n";
// static_assert(false, "Dummy assertion!");
auto is_42 = [](int x) {return x == 42;};
auto answer = 42;
if (is_42(answer))
{
std::cout<<"Yes, it is!\n";
}
decltype(answer + 42) new_answer = 43;//?
std::cout<<"New Answer:"<<new_answer<<"\n";
}
Впечатляет? Присмотритесь внимательней, в этом примере: initializer lists(список инициализации для v), right angle brackets (две правые угловые скобки в определении v2), lambda(с захватом переменных и без), static_assert (закомментирован), auto (для простых случаев и для лямбда-выражений), decltype(для определения типов). Меня очень впечатлило. Несмотря на то, что в язык добавлены новые элементы, язык стал только выразительней, а никак не сложнее.
Таким образом, С++ вбирает в себя всё новые и новые идеи. Несложно заметить, что С++ 0x - огромный шаг поближе к Haskell. Кто считает, что это чепуха - присмотритесь к Variadic Templates:
template<unsigned... Args> struct mysum;
template<>
struct mysum<> {
static const int value = 0;
};

template<unsigned x, unsigned... Args>
struct mysum<x, Args...> {
static const int value = x + mysum<Args...>::value;
};

int main()
{
static_assert(mysum<10,20,11,1>::value==42, "Wow!");
}
Variadic Templates уже доступны, однако работают не полностью.

Выводы

С++ 0x - попытка скачкообразно осовременить С++. И, как мне кажется, эта попытка вполне может оказаться удачной.

Ссылки

Спасибо за внимание!

Tuesday, February 12, 2008

Как посчитать очень большой факториал?

Не так давно обратил внимание на то, как быстро Maple считает факториалы(встроенный функционал). 500000! - огромное число - он посчитал за пару секунд. Стало интересно - как же это реализовано? В итоге было написано несколько тестовых кусочков кода на ЯП, которые поддерживают большие числа. Первым таким языком был Erlang. Код весьма прост:
[UPD]
fact3(X)->fact3(X,1).

fact3(0,Acc)->Acc;
fact3(X,Acc)->fact3(X-1,Acc*X).
[/UPD]
Erlang соптимизирует рекурсию в цикл и в итоге этот код будет достаточно оптимальным. [UPD]На сравнительно небольших числах он работает отменно. Например, 50000! он посчитал за 6 секунд(особой точности здесь не требуется, поэтому я не старался получить максимально точные данные или тестировать в абсолютно чистой среде). Но 100000! у меня он вообще считать отказался - упал по нехватке памяти.[/UPD]
Вторым языком, который был опробован, стал PHP. Наивный код на PHP на больших числах не стесняясь выдавал INF, но тов. Josser(не знаю, куда поставить ссылку) довёл код до ума:

$targ = 50000;
$res = 1;

$startime = time();
for ($i=1; $i<=$targ; $i++) {
echo $i."\r\n";
$res = bcmul($res, $i);
}
$endtime = time();

echo $res."\r\n";

echo $endtime-$startime."\r\n";

Также Josser и протестировал его:
30000! - 99 секунды
50000! - 242 секунды

Как видим, работает оно медленней, чем вариант на Erlang, но хотя бы работает на 50000!.
Следующим языком стал Python. Код также прост, как и в предыдущих случаях:


def fact(x):
s=1
for i in range(2,x+1):
s*=i
return s

Протестировав, получаем:
30000! - 1.64100003242
50000! - 7.54700016975
100000! - 40.75

Как видим, Python смотрится просто героем на фоне Erlang и PHP. Однако, с увеличением чисел понимаем, что подобраться к заветному 500000! таким образом не получится.
Следующим протестированным языком стал Haskell. Я не особо знаком с этим языком, поэтому не могу похвастать и абсолютно правильным кодом. Главное - работает:

import Text.Printf
import Control.Exception
import System.CPUTime

time :: IO t -> IO t
time a = do
start <- getCPUTime
v <- a
end <- getCPUTime
let diff = (fromIntegral (end - start)) / (10^12)
printf "Computation time: %0.3f sec\n" (diff :: Double)
return v

fac n = if n == 0 then 1 else n * fac (n-1)

main = do
putStrLn "Starting..."
time $ fac 100000 `seq` return ()
putStrLn "Done."

Результаты тестирования:
30000! - 4.828 sec
50000! - 14.531 sec
100000! - 70.625 sec
Получше, чем Erlang и PHP, но хуже, чем Python. Также я вспомнил свои познания из области математики и попробовал организовать вычисление факториала через гамма-функцию. Код для вычисления логарифма гамма-функции:

cof :: [Double]
cof = [76.18009172947146,-86.50532032941677,24.01409824083091,-1.231739572450155,0.001208650973866179,-0.000005395239384953]

ser :: Double
ser = 1.000000000190015

gammaln :: Double -> Double
gammaln xx = let tmp' = (xx+5.5) - (xx+0.5)*log(xx+5.5)
ser' = foldl (+) ser $ map (\(y,c) -> c/(xx+y)) $ zip [1..] cof
in -tmp' + log(2.5066282746310005 * ser' / xx) where

Используется потом так:
exp (gammaln 20001)
Так считается 20000! Но, к сожалению, здесь Haskell прямо ответил - Infinity.

В итоге, после того, как мы опробовали кучу языков программирования, можно сделать вывод, что ни один из них изначально не подходит для решения заветной задачи - нахождения 500000!. Но раз стандартные средства не работают, время поискать нестандартное решение. И оно сразу находится - библиотека GNU MP или GMP. Кому хочется посмотреть, на что способна эта библиотека - попробуйте здесь. Также можно попробовать скачать и установить - даже без тонкой настройки всё равно получаем очень неплохие результаты.
Ну, и финальный аккорд - нахождение искомого 500000! при помощи GNU MP:

The result of executing 500000! is:

computation took 1418 ms
result is about 2632341 digits, not printing it


Итоговый результат: хотите посчитать очень большой факториал? Используйте GNU MP![UPD](который и используется в Хаскеле(?) )[/UPD]

[UPD]
Спасибо lionet, который заметил чушь, которую я назвал хвостовой рекурсией раньше, чем я ее исправил. Также спасибо yorool-gui за развитие Хаскелевского варианта. Я не буду исправлять текущий код - вы можете посмотреть на более оптимальные варианты решения задачи здесь.
[/UPD][UPD]
Кстати, в GMP используется функция mpz_fac_ui для того, чтобы подсчитать факториал. Т.е., это отдельная функция. И именно она даёт такие хорошие результаты. Тогда становится понятным, почему Haskell c GMP не даёт таких результатов, как просто использование данной функции.[/UPD]