Haskell :: не такой тормоз, как кажется
От: Schade Россия  
Дата: 22.02.08 00:14
Оценка: 118 (11) +1
Disclaimer: всего лишь собственные наблюдения, захотелось поделиться. Может кому интересно будет.
Haskell заработал репутацию чрезвычайно тормознутого языка. Ленивость, добавляющая свой оверхед к любой операции, все значения в хипе, иммутабельность значений — все это, конечно, скорости не добавляет.
Понадобилось решить одну задачку, связанную с разбором гибридного бинарно-текстового формата. Поскольку смысл этого решения — всего лишь упрощение собственной повседневной работы, позволил себе повыбирать средство реализации. В том числе и по быстродействию. И в велосипедописании потренироваться. И вот тут Haskell очень сильно удивил.
Поскольку много кода дублировать на разных языках ой как не хотелось, тест сведен к простой задаче: парсинг потока double'ов. В качестве источника данных — текстовый файл, содержащий 5 000 000 чисел в диапазоне [-10 000; 10 000], размером около 82 мб (сгенереный таким вот C#-кодом):
static void Main(string[] args)
{
    using (Stream stm = new FileStream(@"d:\numbers_large.txt", FileMode.Create))
    {
        TextWriter wr = new StreamWriter(stm);
        System.Random r = new System.Random();
        for (int i = 0; i < 5000000; i++)
        {
            double d=10000*r.NextDouble() * (r.NextDouble() > 0.7 ? -1.0 : 1.0);
            wr.Write("{0} ", d);
        }
        wr.Flush();
    }


А вот код парсера на Haskell. Код наверняка далек от идеального и избыточен (но и писался он не только для такой простой задачи). Кстати, если кто из здешних знатоков Haskell найдет что покритиковать — буду грейтфул
Компилятор GHC 6.8.2, компиляция, естественно, с оптимизацией:
ghc --make -O2 -funfolding-use-threshold=64 hsparser.hs


{-# LANGUAGE NoMonomorphismRestriction, FlexibleInstances,
    MultiParamTypeClasses, FunctionalDependencies,
    BangPatterns  #-}

module Main (main) where

import System.Time
import Control.Monad
import Control.Monad.Trans
import qualified Data.ByteString.Char8 as B8
import qualified Data.ByteString.Lazy.Char8 as BL8
import Data.Char
import Data.Int
import Data.Maybe

{- результат работы любого парсера:
   Pass - успешное завершение, 
      s - остаток входного потока, a - полученное значение
   Fail - неуспешное, s - остаток входного потока в позиции, где случилась ошибка
  -}
data ParseResult s a = Pass s a | Fail s --deriving Show

instance Show a => Show (ParseResult s a) where
    show (Pass _ a) = "Pass: " ++ show a
    show _ = "Fail" 

{- чтобы удобным образом применять преобразования
   к полученному от парсера результату, объявим
   ParseResult инстансом класса Functor
   это даст нам функцию fmap c типом
   ParseResult s a -> (a -> b) -> ParseResult s b
 -}
instance Functor (ParseResult s) where
    fmap f (Pass s a) = Pass s (f a)
    fmap _ (Fail s) = Fail s

{- для того, чтобы на вход парсера можно было подавать
   не только список, но и любой другой тип, например, ByteString,
   определим класс типов ParserInput
 -}
class ParserInput s e | s -> e where
    p_get :: s -> ParseResult s e

{- и его инстансы для списка и ByteString -}
instance ParserInput [e] e where
    p_get (h:t) = Pass t h
    p_get s = Fail s

instance ParserInput B8.ByteString Char where
    p_get s | B8.null s = Fail s
            | otherwise = Pass (B8.tail s) (B8.head s)

instance ParserInput BL8.ByteString Char where
    p_get s | BL8.null s = Fail s
            | otherwise = Pass (BL8.tail s) (BL8.head s)

{- базовый тип парсера - функция, принимающая как аргумент
   входной поток символов, и возвращающая ParseResult,
   т.е. при успехе - остаток входного потока и результат,
   при неуспехе - только остаток потока после ошибки
 -}
newtype Parser s a = Parser { runParser :: s -> ParseResult s a }

{- Parser тоже объявим инстансом класса Functor -}
instance Functor (Parser s) where
    fmap f (Parser p) = Parser $ fmap f . p

{- теперь начинаются монадические заморочки. В принципе, можно
   обойтись и без них, но так зато получаем удобную форму
   записи с использованием do-notation, а также бонус
   в виде некоторых стандартных функций, работающих с монадами
 -}

{- return a - возвращает парсер, который независимо от
   входного потока завершается успешно и возвращает значение a
   bind (>>=) - связывает два парсера в последовательное выполнение,
   при неуспехе первого второй не вызывается. Как это выглядит
   с использованием do-нотации - будет ниже.
  -}

instance Monad (Parser s) where
    return a = Parser $ \s -> Pass s a
    (Parser p) >>= f = Parser $ \s ->
       case p s of
         Pass s' a' -> runParser (f a') s'
         Fail s -> Fail s

{- Объявив парсер инстансом класса MonadPlus, получаем
   две функции: mzero - парсер, который в любом случае
   завершается с неуспехом, и mplus - альтернатива,
   т.е. при неуспехе первого парсера отрабатывает второй
  -}
instance MonadPlus (Parser s) where
    mzero = Parser $ \s -> Fail s
    (Parser p1) `mplus` (Parser p2) = Parser $ \s ->
        case p1 s of { ok@(Pass _ _) -> ok; _ -> p2 s }

{- теперь вот еще какая штука: часто результат разбора в 
   виде строки/списка нам вообще не нужен, а нужен результат
   некоей операции над этим списком - типа fold'а
   Можно определить тип парсера, который сразу же
   по мере обработки потока будет эту свертку выполнять.
   Получается нечто очень похожее на стандартную монаду
   Writer, но Writer требует, чтобы хранящееся в нем
   значение было моноидом - что-то у меня не получилось
   с этим обходиться -}
newtype WriterP w m a = WriterP { runWriterP :: w -> m (w, a) }

instance Monad m => Monad (WriterP w m) where
    return a = WriterP $ \w -> return (w, a)
    (WriterP p) >>= f = WriterP $ \w -> do 
       (w', a') <- p w 
       runWriterP (f a') w'

instance MonadTrans (WriterP w) where
    lift m = WriterP $ \w -> do { a <- m; return (w, a) }

instance MonadPlus m => MonadPlus (WriterP w m) where
    mzero = lift mzero
    (WriterP p1) `mplus` (WriterP p2) = WriterP $ \w -> p1 w `mplus` p2 w

instance Functor m => Functor (WriterP w m) where
    fmap f (WriterP p) = WriterP $ \w -> fmap (apply2 f) (p w)
                         where apply2 f (a, b) = (a, f b)
    

{- базовый "кирпичик", на основе которого строятся все парсеры -
   парсер, который берет 1 символ из входного потока,
   и успешно завершается, если поток не пуст.
   Чтобы компилятор мог сам вывести тип - Parser или WriterP Parser,
   определим класс типов ParseMonad -}
class Monad m => ParseMonad m a where
    p_take :: m a

instance ParserInput s a => ParseMonad (Parser s) a where
    p_take = Parser p_get

instance ParseMonad m a => ParseMonad (WriterP w m) a where
    p_take = lift p_take

{- теперь на основе базового "кирпичика" чуть более полезные
   строительные блоки -}

{- парсер на основе предиката - завершается успешно,
   если символ из входного потока соответствует условию -}
p_pred :: (ParseMonad p a, MonadPlus p) => (a -> Bool) -> p a
p_pred f = do
  a <- p_take
  if f a then return a else mzero

{- парсер, принимающий только заданный символ  -}
p_sym :: (Eq a, ParseMonad p a, MonadPlus p) => a -> p a
p_sym c = p_pred (==c)

{- и, для удобства, его вариация - один из двух символов  -}
p_sym2 :: (Eq a, ParseMonad p a, MonadPlus p) => a -> a -> p a
p_sym2 c d = p_pred $ \a -> a == c || a == d

{- парсер, принимающий заданную строку -}
p_string = mapM p_sym

{- p_try - парсер, который всегда завершается успешно,
   но возвращает не a, a Maybe a  -}
p_try :: (Functor p, MonadPlus p) => p a -> p (Maybe a)
p_try p = fmap Just p `mplus` return Nothing

{- many - множественный (0 или более) повтор парсера 
   не возвращает значения, предполагается что
   парсером будет WriterP -}
many :: (Functor p, MonadPlus p) => p a -> p ()
many p = mn
    where mn = do
            a <- p_try p
            case a of {Just _ -> mn; _ -> return () }

{- 1 или более -}
many1 p = p >> many p

{-- ============================================
теперь вернемся к WriterP. Чтобы иметь возможность
накапливать значение по мере парсинга, определим
класс типов - накопителей
-- ============================================ -}
class Accumulator a e | a -> e where
    a_empty :: a
    a_append :: e -> a -> a

{- и его инстанс для списка, чтобы иметь возможность
   получать результат парсера в виде списка -}
instance Accumulator [e] e where
    a_empty = []
    a_append = (:)

{- теперь трансформер для парсера, который преобразует
 его в аккумулирующий -}
writing :: (Accumulator w a, Monad p) => p a -> WriterP w p ()
writing p = WriterP $ \(!w) -> do
    a <- p
    return (a_append a w, ())

{- и для случаев, если отдельный тип-аккумулятор 
   заводить не хочется -}
writingF :: Monad p => (a -> w -> w) -> p a -> WriterP w p ()
writingF f p = WriterP $ \(!w) -> do
    a <- p
    return (f a w, ())

{- обратный трансформер - аккумулирующий парсер
   в возвращающий накопленное значение  -}
wrRun :: (Monad p, Functor p) => WriterP w p x -> w -> p w
wrRun (WriterP p) w = fmap fst $ p w

{- и еще одна вариация -}
wrUnwrap :: (Functor p, Accumulator w e) => WriterP w p x -> (w -> a) -> p a
wrUnwrap (WriterP p) f = fmap (f . fst) $ p a_empty

(|>|) = wrUnwrap


{- =========================================
   теперь ближе к предмету - пусть пока
   это будут числа -}

{- digit - парсер, принимающий символы от '0' до '9'
   и возвращающий уже их числовое значение -}
digit = fmap digitToInt $ p_pred isDigit

spaces = many $ p_pred isSpace
dot = p_sym2 ',' '.'

{- sign - парсер, опционально принимающий знаки '+' и '-',
   возвращающий Double-множитель, -1.0 для '-',
   1.0 в противном случае -}
sign = fmap getSign $ p_try (p_sym2 '-' '+')
       where getSign (Just '-') = -1.0
             getSign _ = 1.0


data IntAcc = IntAcc { getInt ::  {-# UNPACK #-} !Double }
instance Accumulator IntAcc Int where
    a_empty = IntAcc 0.0
    a_append i (IntAcc a) = IntAcc $ a * 10.0 + fromIntegral i

{- intPart - разбор целой части -}
intPart = many1 (writing digit)  |>| getInt

{- а если не хочется городить отдельный тип для аккумулятора -
   можно так -}
intPart2 = wrRun (many1 (writingF intFold digit)) 0.0
           where intFold e !i = i * 10.0 + fromIntegral e

data FrAcc = FrAcc { mult :: {-# UNPACK #-} !Double,
                     getFrac :: {-# UNPACK #-} !Double }

instance Accumulator FrAcc Int where
    a_empty = FrAcc 0.1 0.0
    a_append i (FrAcc m a) = FrAcc (m * 0.1) (a + m * fromIntegral i)

{- fracPart - разбор дробной части -}
fracPart = dot >> many1 (writing digit) |>| getFrac

{- expn - разбор экспоненты  -}
expn = do
  p_sym2 'e' 'E'
  s <- sign
  i <- intPart
  return $ 10 ** (s * i)

{- number - разбор числового значения -}
number = do
  spaces
  s <- sign
  i <- p_try intPart
  f <- p_try fracPart
  exp <- liftM (fromMaybe 1.0) $ p_try expn
  case (i, f) of
    (Nothing, Nothing) -> mzero
    _ -> return $! exp * s * (fmay i + fmay f)
         where fmay = fromMaybe 0.0


data Sum a = Sum {getSum :: {-# UNPACK #-} !a}

instance Num a => Accumulator (Sum a) a where
    a_empty = Sum $ fromIntegral 0
    a_append e (Sum a) = Sum $ e + a

sumNumbers = many (writing number) |>| getSum

{- выполнение IO action c замером времени -}
measured :: IO a -> IO (a, Double)
measured act = do
  let getSeconds t = fromIntegral (tdPicosec t) / 1000000000000.0 + fromIntegral (tdSec t)
  start <- getClockTime
  !r <- act
  end <- getClockTime
  let delta = getSeconds $ diffClockTimes end start
  return (r, delta)

calculateSumm str = do
  let res = runParser sumNumbers str
  putStrLn $ "Sum: " ++ show res
  return ()

benchMark = do
  str <- B8.readFile "d:\\numbers_large.txt"
  (_, time) <- measured $ calculateSumm str
  putStrLn $ "Time: " ++ show time ++ " s."
  let thr = fromIntegral (B8.length str) / time / 1048576.0;
  putStrLn $ "Throughput: " ++ show thr ++ " Mb/s"
  return ()

main = benchMark


От имени C++ выступает boost::spirit, как инструмент, дающий в руки C++-программиста абстракции, примерно идентичные ФП-шным комбинаторным парсерам. Вот такой (все просто, т.к. используется встроенный спиритовский парсер real_p)
#include <boost/spirit.hpp>
#include <iostream>

struct SumAction
{
    SumAction(double &d) : value(d) {}

    void operator () (double c ) const
    {
        value += c;
    }

    mutable double &value;
};

void Run()
{
    HANDLE h = CreateFile(L"d:\\numbers_large.txt", GENERIC_READ, FILE_SHARE_READ,
        NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
    DWORD sz = GetFileSize(h, NULL);
    char * p = new char [sz+4];
    ZeroMemory(p, sz+4);
    DWORD read;
    ReadFile(h, p, sz, &read, NULL);
    // спиритовский real_p не понимает запятую
    for(unsigned int i=0; i<sz; i++) if(p[i]==',') p[i]='.';

    LARGE_INTEGER li;
    QueryPerformanceFrequency(&li);
    double freq = double(li.QuadPart);

    QueryPerformanceCounter(&li);
    double start = double(li.QuadPart);

    double sum = 0.0;
    parse(p, +real_p[SumAction(sum)], space_p);

    QueryPerformanceCounter(&li);
    double end = double(li.QuadPart);

    double time = (end - start) / freq;

    std::cout << "Sum: " << sum << std::endl;
    std::cout << "Time: " << time << " s." << std::endl;

    CloseHandle(h);
    delete [] p;

}


Компилятор — Visual C++ Express 2008. Все опции оптимизации на максимум — Full optimization, inline any suitable, favor fast code, link-time code generation.

Результат работы (Core2Duo 3,12 ггц)
Haskell — ~1.56 секунды. 52,5 мб/сек.
C++ (spirit) — ~1.88 секунды. 44 мб/сек. Правда, если рантайм сменить с DLL на статически линкуемый, то ~1.65 секунды.
Вот так. Haskell вровень с C++, и даже опережает.
Хотел привести еще то же решение на F#, но если не скатываться к традиционному императивному решению (а зачем тогда F# нужен?), быстрее 10 сек. пока не получилось.
Вообще, старичок двухплюсатый все равно на высоте — если все переписать вручную (код тупой, приводить не охота), отрабатывает за 0,45 сек. Только ведь в более сложном случае вероятность такого ручного расписывания невелика.

Ну а по выразительности c Haskell сложно что-либо сравнивать. Монады — вообще чертовски интересная штука. Этакий очень абстрактный интерфейс, который, если придумать, как пристегнуть к своей задаче, дает бонус в виде стандартных библиотечных функций, ориентированных на работу с монадами. Например, из кода выше:
-- p_sym - парсер, принимающий заданный символ
-- p_string - парсер, принимающий заданную строку
p_string = mapM p_sym -- mapM - стандартная функция, которой
-- достаточно только того, что p_sym - монада
Re: Haskell :: не такой тормоз, как кажется
От: Аноним  
Дата: 22.02.08 06:22
Оценка:
Здравствуйте, Schade:
вы сравниваете не хаскель и с++, а свой парсер со спиритом. здесь же на rsdn было показано, что парсер на с# в 10 раз быстрей спирита. сам по себе спирит — достаточно тормозная штуковина
Re: Haskell :: не такой тормоз, как кажется
От: DmitryMe  
Дата: 22.02.08 08:20
Оценка:
> И в велосипедописании потренироваться. И вот тут Haskell очень сильно удивил.
да уж навелосипедировал от души

Есть еще вот такой ранкинг гейм:


http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&amp;lang=all

так что с Haskell действительно не все так плохо
Re: Haskell :: не такой тормоз, как кажется
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 22.02.08 08:40
Оценка: 6 (1)
Здравствуйте, Schade, Вы писали:

Симпатичный код, приятно читать.

Может быть ты не знал (забыл?), но ok@(Pass _ _) можно записать как ok@Pass{}.
Re[2]: Haskell :: не такой тормоз, как кажется
От: Schade Россия  
Дата: 22.02.08 08:42
Оценка:
Здравствуйте, Аноним, Вы писали:

А>вы сравниваете не хаскель и с++, а свой парсер со спиритом.

Ну, в общем, да. Вроде бы прямым текстом об этом и пишу. И причина указана: более-менее одинаковый подход к решению задачи (насколько это вообще возможно в случае C++ и Haskell)

A>здесь же на rsdn было показано, что парсер на с# в 10 раз быстрей спирита. сам по себе спирит — достаточно тормозная штуковина

Ссылку можно? Интересно поглядеть. Вообще, я привел результат на C++ врукопашную (только код не приводил )- где-то в 3,5 раза быстрее. Если перекомпилировать тот же код в режиме /clr:pure, разница сокращается до 2,5 раз.
Re[2]: Haskell :: не такой тормоз, как кажется
От: Schade Россия  
Дата: 22.02.08 08:53
Оценка:
Здравствуйте, DmitryMe, Вы писали:

DM>Есть еще вот такой ранкинг гейм:


DM>http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&amp;lang=all


Знаем-с. Могу ошибаться, но по-моему в тех ранкигнах Haskell выезжает в основном на использовании более продвинутых алгоритмов, сложных в реализации на более низкоуровневых языках. Мне же было интересно сравнить на более-менее одинаковых алгоритмах, собственно почему и сравнивал со спиритом. В некотором роде этот пост — ответ на заявление
Автор: VladD2
Дата: 20.02.08
, что этому компилятору уже ничего не поможет.
Re[3]: Haskell :: не такой тормоз, как кажется
От: Аноним  
Дата: 22.02.08 09:56
Оценка:
Здравствуйте, Schade, Вы писали:

А>>вы сравниваете не хаскель и с++, а свой парсер со спиритом.

S>Ну, в общем, да. Вроде бы прямым текстом об этом и пишу. И причина указана: более-менее одинаковый подход к решению задачи (насколько это вообще возможно в случае C++ и Haskell)

А если то же самое эксперимента ради на Parsec переписать?
Re[4]: Haskell :: не такой тормоз, как кажется
От: Schade Россия  
Дата: 22.02.08 12:46
Оценка:
Здравствуйте, Аноним, Вы писали:

А>А если то же самое эксперимента ради на Parsec переписать?


Надо попробовать. Я правда как-то сходу им не проникся, там можно без промежуточных списков обойтись? А то на deforestation надейся, а сам не плошай — со списками такая тормозуха получается.
Re: Haskell :: не такой тормоз, как кажется
От: Аноним  
Дата: 22.02.08 18:42
Оценка: 10 (1)
Симпатично. Некоторое количество замечаний таки набралось.

S>instance Functor (ParseResult s) where

S> fmap f (Pass s a) = Pass s (f a)
S> fmap _ (Fail s) = Fail s

Зачем? Мы используем этот fmap только в одном месте — см. ниже.

S>instance Functor (Parser s) where

S> fmap f (Parser p) = Parser $ fmap f . p

Тут проще написать ... where fmap = liftM. И всё. И не требуется instance Functor (ParseResult s).

S>instance Monad (Parser s) where

S> return a = Parser $ \s -> Pass s a
S> (Parser p) >>= f = Parser $ \s ->
S> case p s of
S> Pass s' a' -> runParser (f a') s'
S> Fail s -> Fail s

Очень не вредно объявить fail _ = Parser $ \s -> Fail s

S>newtype WriterP w m a = WriterP { runWriterP :: w -> m (w, a) }


А не проще воспользоваться mtl-ным StateT? Он ведь ровно так и определяется, с точностью до порядка элементов в паре.

S>instance Monad m => Monad (WriterP w m) where ...

S>instance MonadTrans (WriterP w) where ...
S>instance MonadPlus m => MonadPlus (WriterP w m) where ...
S>instance Functor m => Functor (WriterP w m) where ...

Всё это мы получаем от StateT бесплатно, кроме последнего — в mtl там стоит контекст (Monad m) — но нам ведь это по фигу? Кстати, это, похоже, баг в mtl, надо, действительно, Functor.

S>class Monad m => ParseMonad m a where

S> p_take :: m a

Очень правильно, интерфейс монады надо определять в классе.

S>instance ParseMonad m a => ParseMonad (WriterP w m) a where

S> p_take = lift p_take

Ну, понятно, StateT вместо WriterP. Дальше заменять не буду, и так понятно. Или можно просто сказать type WriterP w m a = StateT w m a.

S>p_pred :: (ParseMonad p a, MonadPlus p) => (a -> Bool) -> p a

S>p_pred f = do
S> a <- p_take
S> if f a then return a else mzero

Последнюю строчку я бы разбил на две:
guard $ f a
return a

S>many :: (Functor p, MonadPlus p) => p a -> p ()

S>many p = mn
S> where mn = do
S> a <- p_try p
S> case a of {Just _ -> mn; _ -> return () }

Может, просто написать many p = many1 p `mplus` return ()? Или, если уж на то пошло, сделать many :: p a -> p [a]; many p = many1 p `mplus` return []

S>many1 p = p >> many p


Соответственно, many1 p = liftM2 ( p $ many p?

S>writing p = WriterP $ \(!w) -> do

S> a <- p
S> return (a_append a w, ())

Уй! Можно уровнем повыше работать. Во-1, если уж (!), то импортировать Control.Monad.State.Strict. Во-2, переписать таким образом: writing p = do {a <- lift p; modify $ a_append a; return ()}. Кстати, а почему мы обязательно возращаем ()?

S>writingF f p = WriterP $ \(!w) -> do

S> a <- p
S> return (f a w, ())

Аналогично: writingF f p = do {a <- lift p; modify $ f a; return ()}; кстати, тогда не вредно бы определить выше writing как writingF a_append.

S>wrRun :: (Monad p, Functor p) => WriterP w p x -> w -> p w

S>wrRun (WriterP p) w = fmap fst $ p w

wrRun = execStateT

S>wrUnwrap :: (Functor p, Accumulator w e) => WriterP w p x -> (w -> a) -> p a


Ценой замены Functor на Monad, получаем wrUnwrap p f = liftM f $ execStateT p a_empty

S>digit = fmap digitToInt $ p_pred isDigit


ИМХО — только ИМХО — для монад лучше читается liftM, а не fmap (хотя это одно и то же).

S>data IntAcc = IntAcc { getInt :: {-# UNPACK #-} !Double }


А почему не newtype?

S>measured act = do

S> let getSeconds t = fromIntegral (tdPicosec t) / 1000000000000.0 + fromIntegral (tdSec t)
S> start <- getClockTime
S> !r <- act
S> end <- getClockTime
S> let delta = getSeconds $ diffClockTimes end start
S> return (r, delta)

Чего-то мне в голову стукнуло, что bang patterns внутри do-блоков ничего не делают.

Не ручаюсь, что что-нибудь из этого не вызовет падения производительности. Кстати, я слышал, что с какими-то ghc поставлялась mtl, откомпилированная без оптимизации — что, естественно, замедляло работу.
Re[2]: Haskell :: не такой тормоз, как кажется
От: Аноним  
Дата: 22.02.08 18:48
Оценка:
Блин. Дико извиняюсь, (:) заменилось на корявый смайлик.
Re[2]: Haskell :: не такой тормоз, как кажется
От: Schade Россия  
Дата: 22.02.08 20:07
Оценка:
Здравствуйте, http://migmit.vox.com/, Вы писали:

HMV>Симпатично. Некоторое количество замечаний таки набралось.

Замечательно, что набралось.

S>>instance Functor (ParseResult s) where

HMV>Зачем? Мы используем этот fmap только в одном месте — см. ниже.
Ну, в конечном итоге, мы же все равно вызываем runParser и получаем ParseResult. Почему бы и не оставить? Хотя в принципе да, liftM достаточно.

S>>instance Functor (Parser s) where

S>> fmap f (Parser p) = Parser $ fmap f . p
HMV>Тут проще написать ... where fmap = liftM. И всё. И не требуется instance Functor (ParseResult s).
+1. Сам заметил уже после.

S>>instance Monad (Parser s) where

HMV>Очень не вредно объявить fail _ = Parser $ \s -> Fail s
+1

S>>newtype WriterP w m a = WriterP { runWriterP :: w -> m (w, a) }


HMV>А не проще воспользоваться mtl-ным StateT? Он ведь ровно так и определяется, с точностью до порядка элементов в паре.


S>>instance Monad m => Monad (WriterP w m) where ...

S>>instance MonadTrans (WriterP w) where ...
S>>instance MonadPlus m => MonadPlus (WriterP w m) where ...
S>>instance Functor m => Functor (WriterP w m) where ...

HMV>Всё это мы получаем от StateT бесплатно, кроме последнего — в mtl там стоит контекст (Monad m) — но нам ведь это по фигу? Кстати, это, похоже, баг в mtl, надо, действительно, Functor.


В общем-то, сначала проглядел наличие в стандартной библиотеке strict state Ну и дух велосипедизма — хотелось в своей голове утрясти. Я ж только с C++-ной пальмы слез

S>>many :: (Functor p, MonadPlus p) => p a -> p ()

S>>many p = mn
S>> where mn = do
S>> a <- p_try p
S>> case a of {Just _ -> mn; _ -> return () }

HMV>Может, просто написать many p = many1 p `mplus` return ()? Или, если уж на то пошло, сделать many :: p a -> p [a]; many p = many1 p `mplus` return []

S>>many1 p = p >> many p
HMV>Соответственно, many1 p = liftM2 ( p $ many p?

Что касается первого варианта: many p = many1 p `mplus` return () — ленивость языка, конечно, позволяет уделять меньше внимания преобразованию наивной рекурсии в хвостовую. Но тут не спасает — на сколько-нибудть серьезных объемах данных получаем stack overflow.
many :: p a -> p [a] — это самое очевидное, наглядное, удобное в использовании и легкочитаемое решение. Но, как часто бывает в таких случаях, полный (_|_) bottom по части производительности.
А если в результате нужен все-таки список, можем определить
 
manyL :: (Functor p, MonadPlus p) => p a -> p [a]
manyL p = many (writing p) |>| reverse

Хотя, конечно, не идеально. Хорошо бы без reverse обойтись.

S>>writing p = WriterP $ \(!w) -> do

S>> a <- p
S>> return (a_append a w, ())

HMV>Уй! Можно уровнем повыше работать. Во-1, если уж (!), то импортировать Control.Monad.State.Strict. Во-2, переписать таким образом: writing p = do {a <- lift p; modify $ a_append a; return ()}. Кстати, а почему мы обязательно возращаем ()?

(!) — это потому что с ленивым Хаскелем именно в этом месте нужно обойтись со всей строгостью во избежание space leak. Ну, по поводу StateT все понятно, а что еще возвращать, кроме ()? То же самое a? Вроде как путаница получается — и к состоянию это значение присовокупляем, и возвращаем. Вообще надо подумать.

HMV>Аналогично: writingF f p = do {a <- lift p; modify $ f a; return ()}; кстати, тогда не вредно бы определить выше writing как writingF a_append.

+1

HMV>wrRun = execStateT

+1

HMV>Ценой замены Functor на Monad, получаем wrUnwrap p f = liftM f $ execStateT p a_empty

+1

S>>digit = fmap digitToInt $ p_pred isDigit

HMV>ИМХО — только ИМХО — для монад лучше читается liftM, а не fmap (хотя это одно и то же).

S>>data IntAcc = IntAcc { getInt :: {-# UNPACK #-} !Double }

HMV>А почему не newtype?
Для newtype не позволяет указать strictness annotation. Хотя да, в случае с newtype компилятор, похоже, и сам выполняет UNPACK, даже процентов на 5 в итоге быстрее получается. Что-то я в прошлый раз не так делал, что с newtype получил тормоза.
Re[4]: Haskell :: не такой тормоз, как кажется
От: Schade Россия  
Дата: 23.02.08 13:36
Оценка:
Здравствуйте, Аноним, Вы писали:

А>А если то же самое эксперимента ради на Parsec переписать?


{-# LANGUAGE BangPatterns#-}

module Main where

import System.Time
import System.IO
import Control.Monad
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Language
import Text.ParserCombinators.Parsec.Token
import qualified Data.ByteString.Char8 as B8

sign = liftM getSign (optionMaybe $ oneOf "-+")
       where getSign (Just '-') = -1.0
             getSign _ = 1.0

number = do
  s <- sign
  d <- liftM getN $ naturalOrFloat haskell
  return $! s * d
  where getN (Left i) = fromIntegral i
        getN (Right f) = f

sep = spaces >> return (+)

sumNumbers = spaces >> chainl number sep 0.0

measured act = do
  let getSeconds t = fromIntegral (tdPicosec t) / 1000000000000.0 + fromIntegral (tdSec t)
  start <- getClockTime
  !r <- act
  end <- getClockTime
  let delta = getSeconds $ diffClockTimes end start
  return (r, delta)

calculateSumm str = do
  let !res = parse sumNumbers "" str
  putStrLn $ "Sum: " ++ show res
  return ()

benchmark = do
  str <- readFile "d:\\numbers.txt"
  (_, time) <- measured $ calculateSumm str
  putStrLn $ "Time: " ++ show time ++ " s."
  let thr = fromIntegral (length str) / time / 1048576.0;
  putStrLn $ "Throughput: " ++ show thr ++ " Mb/s"
  return ()

main = benchmark


Работает только при относительно небольшом объеме данных. С 1 000 000 чисел не справляется — долгое пыхтение, затем stack overflow. Явный признак чрезмерной ленивости. Увеличиваем стек — отрабатывает со скоростью примерно 1,33 мб/сек, в 35-37 раз медленнее моего примера.
Беда в том, что в чужом коде не всегда легко понять, в каком месте прищемить хаскелю его ленивость.
Ну и конечно просто убивает традиция haskell community писать так, как будто данных всегда будет заведомо мало, а память и стек бесконечны.
Наверное можно переписать так, чтобы отрабатывало нормально, но все равно будет медленнее. Хотя бы из-за того, что входной поток может быть только списком.
Re[5]: Haskell :: не такой тормоз, как кажется
От: Schade Россия  
Дата: 26.02.08 22:06
Оценка:
[]
Опп... неспортивно обошелся с парсеком...
Во первых, списки не настолько дешевы, чтобы все время работы держать ссылку на голову списка
Во вторых, явно нужно добавить строгости:
sumNumbers = sn 0.0
    where sn !acc = do
            n <- optionMaybe number
            case n of { Just v -> sn (acc+v); _ -> return acc }

Так на основном тестовом файле отрабатывает. Но скорость...
136 секунд. В 87 раз медленнее.
Re[6]: Haskell :: не такой тормоз, как кажется
От: Аноним  
Дата: 27.02.08 14:17
Оценка:
Здравствуйте, Schade, Вы писали:

S>Так на основном тестовом файле отрабатывает. Но скорость...


Действительно, быстро доработать Parsec чтобы тот парсил BypeString не получается... уж чень он завязан на String.
Ну а если взять например, Text.ParserCombinators.ReadP.ByteString ?
Хотя он не его набор готовых примитивов не столь разнообразен, как парсековский
Re: Haskell :: не такой тормоз, как кажется
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 29.02.08 18:47
Оценка: 15 (1)
Ради интереса изобразил нечто подобное на OCaml с использованием enumerations из ExtLib.
На Core2Duo 2.0 GHz получается всего 3,8 МБ/с..
open ExtString;;

let (>>=) o f = match o with Some x -> f x | None -> None;;
let (>>) x f = f x;;

let digit c = c>='0' && c<='9';;

let p_pred p e =
  match Enum.peek e with 
  | Some c -> if p c then Enum.get e else None
  | None -> None;;
  
let manyf prs f s e =
  let rec frec v =
    match prs e with
    | Some c -> frec (f v c)
    | None -> v
  in frec s;;    
  
let rec many prs e = 
  match prs e with
  | Some _ -> many prs e
  | None -> ();;
  
let mkInt v c = v*10 + (int_of_char c) - 48;;
let mkFrac (fv,fr) c = (fv +. (float_of_int ((int_of_char c)-48))*.fr, fr*.0.1);;

let p_spaces = many (p_pred ((=) ' '));;
let p_sign e = match p_pred ((=) '-') e with Some _ -> -1.0 | None -> 1.0;;
let p_int e = Some (manyf (p_pred digit) mkInt 0 e);;
let p_dot = p_pred ((=) ',');;
let p_frac e = let (fv,fr) = manyf (p_pred digit) mkFrac (0.0, 0.1) e in Some fv;; 

let p_float e = 
  p_spaces e >> fun _ ->
  p_sign e >> fun s ->
  p_int e >>= fun n ->
  p_dot e >>= fun _ ->
  p_frac e >>= fun fr ->
  Some(s *. ((float_of_int n) +. fr));;  

let sumNumbers = manyf p_float (+.) 0.0;;

let measured f =
  let t0 = Unix.times() in
  let _ = f () in
  let t1 = Unix.times() in
  t1.Unix.tms_utime -. t0.Unix.tms_utime;;

let ic = open_in "e:\\numbers_large.txt" in
let str = input_line ic in
let t = measured (fun ()->print_float (sumNumbers (String.enum str))) in
close_in ic;
Printf.printf " %f s, %f MB/s" t ((float_of_int (String.length str)) /. t /. 1048576.0);;
Re[2]: Haskell :: не такой тормоз, как кажется
От: Schade Россия  
Дата: 02.03.08 12:36
Оценка:
Здравствуйте, D. Mon, Вы писали:

DM>Ради интереса изобразил нечто подобное на OCaml с использованием enumerations из ExtLib.

DM>На Core2Duo 2.0 GHz получается всего 3,8 МБ/с..

Вообще странно конечно. Вроде бы Камл считается шустрым. У меня отработал немного быстрее — 5,4 Мб/с.
Но вот что интересно — подобное на F# оказалось быстрее (причем F# с участием его новой фичи —
computation expressions aka monads).
[страшный нечитаемый ужас]
#light

open System
type sc = System.Console

module Accumulator =
    type ('e, 'a) t = 'a * ('e -> 'a -> 'a)
    let create a f = (a, f)
    let append e (a, f) = (f e a, f)
    let get = fst
    
module Iterator =
    type 'a t = {buf: 'a array; len: int; pos: int}
    let iterate arr from = {buf=arr; len=Array.length arr; pos=from}
    let inline valid i = i.pos < i.len
    let current i = i.buf.(i.pos)
    let next i = {i with pos = i.pos+1}

let measured f =
    let sd = System.Diagnostics.Stopwatch()
    sd.Start()
    let res = f()
    sd.Stop()
    let time = double (sd.ElapsedMilliseconds) / 1000.0
    (res, time)
    
module A = Accumulator
module I = Iterator


type ('a, 's) ParseResult = Pass of 'a * 's | Fail
let pr_map f = function Pass (a, s) -> Pass(f a, s) | _ -> Fail

type ('a, 's) Parser = 's -> ('a, 's) ParseResult
let p_map f p = p >> (pr_map f)

let p_take s = if I.valid s then Pass(I.current s, I.next s) else Fail

let p_pred f = p_take >> function Pass(a, _) as ok when f a -> ok | _ -> Fail

let p_sym c = p_pred ((=) c)

let p_sym2 a b = p_pred (fun c -> c=a || c = b)

let p_try p s = p s |> function Pass(a, s') -> Pass(Some(a), s') | _ -> Pass(None, s)

let (<|>) p1 p2 s = p1 s |> function Pass(_, _) as ok -> ok | _ -> p2 s

let many p ac =
    let rec m acc s = match p s with Pass(a', s') -> m (A.append a' acc) s' | _ -> Pass(acc, s)
    m ac
    
let skipmany p =
    let rec m s = match p s with Pass(_, s') -> m s'| _ -> Pass((), s)
    m
    
let fconst a = fun _ -> a

type ParseMonad() =
    member x.Delay p = p ()
    member x.Return a = fun s -> Pass(a, s)
    member x.Bind(p, f) = p >> function Pass(a', s') -> (f a') s' | _ -> Fail
    member x.Let(a, f) = f a
    member x.Zero() = fconst Fail
    
let parse = ParseMonad()

let many1 p acc =
  parse {  let! r1 = p
           let! r2 = many p (A.append r1 acc)
           return r2
  }
  
let isDigit c = c >= 48uy && c <= 57uy
let digitToInt c = int (c - 48uy)
let digit = p_map digitToInt (p_pred isDigit)

let intAcc = A.create 0.0 (fun e a -> double e + a * 10.0)

let intPart = p_map A.get (many1 digit intAcc)

let frAcc = A.create (0.1, 0.0) (fun e (m, a) -> (m*0.1, a + m * double e))

let fracPartImpl = p_map (A.get >> snd) (many1 digit frAcc)

let sign = p_map (function Some(45uy) -> -1.0 | _ -> 1.0) (p_try (p_sym2 45uy 43uy))

let dot = p_map (fconst ()) (p_sym2 46uy 44uy)

let spaces = skipmany (p_sym 32uy)

let fracPart =
 parse { do! dot
         let! r = fracPartImpl
         return r
       }
       
let exponent = 
  parse { do! p_map ignore (p_sym2 101uy 69uy)
          let! r = intPart
          return 10.0 ** double r
        }
        
let fromOption a = function Some x -> x | _ -> a

let number =
  let fmay = fromOption 0.0
  parse { do! spaces
          let! s = sign
          let! i = p_try intPart
          let! f = p_try fracPart
          let! exp = p_map (fromOption 1.0) (p_try exponent)
          match (i, f) with
            | (None, None) -> return! (fconst Fail)
            | _ -> return (exp * s * (fmay i + fmay f))
  }
  
let manyNumbers iter () = iter |> p_map (A.get) (many number (A.create 0.0 (+)))

let benchMark() =
    let str = IO.File.ReadAllBytes @"d:\numbers_large.txt"
    let i = I.iterate str 0
    let (res, time) = measured (manyNumbers i)
    match res with
        | Pass(sum, _) -> 
            let thr = double (Array.length str) / 1048576.0 / time
            sc.WriteLine("Sum: {0}; Time: {1} s", sum, time)
            sc.WriteLine("Throughput: {0} Mb/s", thr)
        | _ -> sc.WriteLine "Fail"

do
    sc.WriteLine "Here I go"
    benchMark()
    sc.ReadKey() |> ignore

[/страшный нечитаемый ужас]

Отрабатывает со скоростью 7,3 Мб/с, процентов на 40 шустрее. И все равно отставание от Хаскеля катастрофическое — в 7 раз
Re[3]: Haskell :: не такой тормоз, как кажется
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 15.03.08 10:06
Оценка:
Заменил в своем OCaml коде монады на то, что они эмулировали, скорость возросла в 4,3 раза до 16 МБ/с.
exception Noparse;;

let reader s = 
  let len = String.length s and pos = ref 0 in
  fun p ->
    if !pos>=len then raise Noparse else
    let c = s.[!pos] in
    if p c then (incr pos; c) else raise Noparse;;

let digit c = c>='0' && c<='9';;

let manyf prs f s r =
  let cv = ref s in
  try let rec frec v = cv := v; frec (f v (prs r)) in frec s
  with Noparse -> !cv;;  
  
let many prs r = 
  try let rec frec () = let _ = prs r in frec () in frec ()
  with Noparse->();;    
  
let mkInt v c = v*10 + (int_of_char c) - 48;;
let mkFrac (fv,fr) c = (fv +. (float_of_int ((int_of_char c)-48))*.fr, fr*.0.1);;

let p_pred p r = r p;;
let p_spaces = many (p_pred ((=) ' '));;
let p_sign r = try let _ = p_pred ((=) '-') r in (-1.0) with Noparse -> 1.0;;
let p_int = manyf (p_pred digit) mkInt 0;;
let p_dot = p_pred ((=) ',');;
let p_frac r = let (fv,fr) = manyf (p_pred digit) mkFrac (0.0, 0.1) r in fv;; 

let p_float r = 
  let _ = p_spaces r in
  let s = p_sign r in
  let n = p_int r in
  let _ = p_dot r in
  let fr = p_frac r in
  s *. ((float_of_int n) +. fr);;  

let sumNumbers = manyf p_float (+.) 0.0;;

let measured f =
  let t0 = Unix.times() in
  let _ = f () in
  let t1 = Unix.times() in
  t1.Unix.tms_utime -. t0.Unix.tms_utime;;

let ic = open_in "e:\\numbers_large.txt" in
let str = input_line ic in
let t = measured (fun ()->print_float (sumNumbers (reader str))) in
close_in ic;
Printf.printf " %f s, %f MB/s" t ((float_of_int (String.length str)) /. t /. 1048576.0);;
Re: Haskell :: не такой тормоз, как кажется
От: Basil B Россия  
Дата: 15.03.08 10:33
Оценка:
Здравствуйте, Schade, Вы писали:

S>Ну а по выразительности c Haskell сложно что-либо сравнивать.


? На плюсах получилось гораздо короче и яснее, имхо.
Re[2]: Haskell :: не такой тормоз, как кажется
От: Schade Россия  
Дата: 15.03.08 10:54
Оценка:
Здравствуйте, Basil B, Вы писали:

BB>? На плюсах получилось гораздо короче и яснее, имхо.


Ну, вообще-то, чтобы сравнивать приведенный Haskell-код с плюсами к плюсовому коду нужно прибавить еще весь boost::spirit.
И тут от краткости и ясности камня на камне не останется.
Re[3]: Haskell :: не такой тормоз, как кажется
От: dr.Chaos Россия Украшения HandMade
Дата: 15.03.08 12:18
Оценка:
Schade wrote:

>

> Ну, вообще-то, чтобы сравнивать приведенный Haskell-код с плюсами к
> плюсовому коду нужно прибавить еще весь boost::spirit. И тут от краткости
> и ясности камня на камне не останется.

Ты, кстати, с Parsec'ом 3-й версии не пробовал?
Posted via RSDN NNTP Server 2.1 beta
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
Re[2]: Haskell :: не такой тормоз, как кажется
От: Димчанский Литва http://dimchansky.github.io/
Дата: 19.03.08 10:09
Оценка:
Здравствуйте, Basil B, Вы писали:
BB>? На плюсах получилось гораздо короче и яснее, имхо.

Пример кода на плюсах скажет за себя все..
Экстренное торможение средствами LINQ
От: Klapaucius  
Дата: 20.03.08 18:26
Оценка: 32 (3) :))) :)
C# имеет репутацию не самого тормозного языка, но умелые руки и смекалка могут поставить на колени еще и не такие творения сумрачного скандинавского гения.
Luke Hoban написал небольшой фреймворк для построения монадических комбинаторных парсеров на С# 3:
    // The result of a parse consists of a value and the unconsumed input.
    public class Result<TInput, TValue>
    {
        public readonly TValue Value;
        public readonly TInput Rest;
        public Result(TValue value, TInput rest) { Value = value; Rest = rest; }
    }

    // A Parser is a delegate which takes an input and returns a result.
    public delegate Result<TInput, TValue> Parser<TInput, TValue>(TInput input);

    public static class ParserCombinatorExtensions
    {
        public static Parser<TInput, TValue> OR<TInput, TValue>(this Parser<TInput, TValue> parser1, Parser<TInput, TValue> parser2)
        {
            return input => parser1(input) ?? parser2(input);
        }

        public static Parser<TInput, TValue2> AND<TInput, TValue1, TValue2>(this Parser<TInput, TValue1> parser1, Parser<TInput, TValue2> parser2)
        {
            return input => parser2(parser1(input).Rest);
        }
    }

    // Expose some operations on the Parser type using Extension methods.
    public static class ParserCombinatorsMonad
    {
        // By providing Select, Where and SelecMany methods on Parser<TInput,TValue> we make the 
        // C# Query Expression syntax available for manipulating Parsers.  
        public static Parser<TInput, TValue> Where<TInput, TValue>(this Parser<TInput, TValue> parser, Func<TValue, bool> pred)
        {
            return input =>
            {
                var res = parser(input);
                if (res == null || !pred(res.Value)) return null;
                return res;
            };
        }
        public static Parser<TInput, TValue2> Select<TInput, TValue, TValue2>(this Parser<TInput, TValue> parser, Func<TValue, TValue2> selector)
        {
            return input =>
            {
                var res = parser(input);
                if (res == null) return null;
                return new Result<TInput, TValue2>(selector(res.Value), res.Rest);
            };
        }
        public static Parser<TInput, TValue2> SelectMany<TInput, TValue, TIntermediate, TValue2>(this Parser<TInput, TValue> parser, Func<TValue, Parser<TInput, TIntermediate>> selector, Func<TValue, TIntermediate, TValue2> projector)
        {
            return input =>
            {
                var res = parser(input);
                if (res == null) return null;
                var val = res.Value;
                var res2 = selector(val)(res.Rest);
                if (res2 == null) return null;
                return new Result<TInput, TValue2>(projector(val, res2.Value), res2.Rest);
            };
        }
    }

    // Contains all the basic parsers that are independent of return type.
    public abstract class Parsers<TInput>
    {
        public Parser<TInput, TValue> Succeed<TValue>(TValue value)
        {
            return input => new Result<TInput, TValue>(value, input);
        }
        public Parser<TInput, TValue[]> Rep<TValue>(Parser<TInput, TValue> parser)
        {
            return Rep1(parser).OR(Succeed(new TValue[0]));
        }
        public Parser<TInput, TValue[]> Rep1<TValue>(Parser<TInput, TValue> parser)
        {
            return from x in parser
                   from xs in Rep(parser)
                   select (new[] { x }).Concat(xs).ToArray();
        }
    }

    // Contains a few parsers that parse characters from an input stream
    public abstract class CharParsers<TInput> : Parsers<TInput>
    {
        public abstract Parser<TInput, char> AnyChar { get; }
        public Parser<TInput, char> Char(char ch) { return from c in AnyChar where c == ch select c; }
        public Parser<TInput, char> Char(Predicate<char> pred) { return from c in AnyChar where pred(c) select c; }
    }

Воспользовавшись им, я легко и непринужденно написал парсер для чисел. Этот код, разумеется, весьма далек от идеального и избыточен.
public abstract class DoubleParser<TInput> : CharParsers<TInput>
{
    public Parser<TInput, double> Number;
    public Parser<TInput, char[]> Whitespace;

    protected DoubleParser()
    {
        Whitespace = Rep(Char(' ').OR(Char('\t').OR(Char('\n')).OR(Char('\r'))));
        Number = from ws in Whitespace
                 let Digit = from c in Char(char.IsDigit) select int.Parse(c.ToString())
                 let Dot = Char('.').OR(Char(','))
                 let Sign = (from c in Char('+') select 1).OR(from c in Char('-') select -1)
                 let IntPart = from ws_ in Whitespace
                               from ds in Rep1(Digit)
                               select ds.FoldRightI(0, (i, d, acc) => acc + d*(int)Math.Pow(10, i))
                 let FracPart = from dt in Dot
                                from ds in Rep1(Digit)
                                select ds.FoldLeftI(0.0, (i, d, acc) => acc + d*Math.Pow(0.1, i))
                 let Expn = from c in Char('E').OR(Char('e'))
                            from s in Sign
                            from i in IntPart
                            select Math.Pow(10, s*i)
                 from s in Sign.OR(Default(1))
                 from i in IntPart
                 from f in FracPart.OR(Default(0.0))
                 from e in Expn.OR(Default(1.0))
                 select s * (i + f) * e;
    }

    public IEnumerable<double> Stream(TInput src)
    {
        var s = src;
        var res = Number(s);
        while (res != null)
        {
            yield return res.Value;
            res = Number(res.Rest);
        }
    }

    public Parser<TInput, T> Default<T>(T val)
    {
        return input => new Result<TInput, T>(val, input);
    }
}

public struct StringList
{
    private readonly int _cursor;
    private readonly string _s;

    public StringList(string s)
    {
        _s = s;
        _cursor = 0;
    }

    private StringList(string s, int c)
    {
        _s = s;
        _cursor = c;
    }

    public bool NonNil
    {
        get { return _cursor < _s.Length; }
    }

    public char Head
    {
        get { return _s[_cursor]; }
    }

    public StringList Tail
    {
        get { return new StringList(_s, _cursor + 1); }
    }
}

public static class Helper
{
    public static RT FoldRightI<T, RT>(this T[] arr, RT acc, Func<int, T, RT, RT> f)
    {
        var _acc = acc;
        var len = arr.Length - 1;
        for (var i = 0; i < arr.Length; i++)
            _acc = f(len - i, arr[i], _acc);
        return _acc;
    }

    public static RT FoldLeftI<T, RT>(this T[] arr, RT acc, Func<int, T, RT, RT> f)
    {
        var _acc = acc;
        for (var i = 0; i < arr.Length; i++)
            _acc = f(i + 1, arr[i], _acc);
        return _acc;
    }
}

public class DoubleParserFromIterator : DoubleParser<StringList>
{
    public override Parser<StringList, char> AnyChar
    {
        get
        {
            return input => input.NonNil
                                ?
                                    new Result<StringList, char>(input.Head, input.Tail)
                                :
                                    null;
        }
    }
}

internal class Program
{
    private static void Main()
    {
        var str = File.ReadAllText(@"c:\numbers_large.txt");
        
        var parser = new DoubleParserFromIterator();

        var sw = new Stopwatch();
        sw.Start();

        var sum = parser.Stream(new StringList(str)).Sum();

        sw.Stop();

        Console.WriteLine(str.Length/1024.0/1024.0/(sw.ElapsedMilliseconds/1000.0));
        Console.WriteLine(sum);
    }
}

На E6750 этот парсер работает, с не побоюсь этого слова, феерической скоростью в 0,15 mb/s
... << RSDN@Home 1.2.0 alpha rev. 774>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re: Экстренное торможение средствами LINQ
От: Schade Россия  
Дата: 20.03.08 19:56
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>Luke Hoban написал небольшой фреймворк для построения монадических комбинаторных парсеров на С# 3:

Какой кошмар. И этот человек сейчас работает над F#. Все, приплыли, хана языку
Re: Экстренное торможение средствами LINQ
От: Schade Россия  
Дата: 21.03.08 09:18
Оценка:
Здравствуйте, Klapaucius, Вы писали:
K>Luke Hoban написал небольшой фреймворк для построения монадических комбинаторных парсеров на С# 3:
У, да там еще и рейтрейсер на LINQ есть
А вообще забавная тенденция: раньше народ, чтобы проиллюстрировать ФП-фичи, писал факториалы да фибоначчи. Теперь каждый считает своим долгом написать парсер и рейтрейсер.
Re: Экстренное торможение средствами LINQ
От: Аноним  
Дата: 22.03.08 16:53
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>На E6750 этот парсер работает, с не побоюсь этого слова, феерической скоростью в 0,15 mb/s


Обидно стало за C#. Решил свой велосипед тоже изобразить (взяв за основу вышеозначенный фреймворк и Parsec за образцы). Тока малехо доработав напильником. Получилось не ахти какая скорость (в районе 2Mb/s), но уж не 0.1 хотя бы Монады сохранены, но внутри немного императившины добавлено. Со скоростью думаю проблема в том, что С# слегка ошалевает от обилия функций высшего порядка — надеюсь в F# таке вещи компилит в более съедобный для CLR вид. Ниже получившийся гибридный ужас:
Собственно "do-notation"-вида парсеры и парсинг:
    class Program
    {
        static void Main(string[] args)
        {
            Func<char, Parser<char, char>> symbol = s => Parsers.Satisfy((char c) => c == s);
            Func<string, Parser<char, char>> anyOf = symbols => Parsers.Satisfy((char c) => symbols.Contains(c));

            var digit = Parsers.Satisfy((char c) => c >= '0' && c <= '9');
            var digitValue = from c in digit select (long)c - '0';
            var dot = anyOf(",.");
            var minus = symbol('-');
            var space = anyOf(" \n");

            var integer = Parsers.Fold1Many1(digitValue, (s, i) => 10 * s + i);

            var fraction =
                from d in Parsers.FoldMany1(digitValue, (Tuple<long, int> acc, long i) => new Tuple<long, int>(10 * acc.First + i, acc.Second + 1), () => new Tuple<long, int>(0, 0))
                select d.First / (Math.Pow(10, d.Second));

            var sign = Parsers.Optional(from _ in minus select -1.0, 1.0);

            var exp = Parsers.Optional(
                from _ in anyOf("eE")
                from s in sign
                from i in integer
                select Math.Pow(10, i * s), 1);

            var real =
                from s in sign
                from i in integer
                from d in dot
                from f in fraction
                from e in exp
                select (i + f) * s * e;

            var realNumberSum = Parsers.Fold1Many1(
                    from r in real from _ in space select r,
                (f, s) => f + s);

            using (var fs = File.OpenText(@"C:\numbers_large.txt"))
            {
                DateTime dt = DateTime.Now;
                var sum = realNumberSum(new StreamEnumerator<char>(GetFileContentBlock(fs)));
                Console.WriteLine(sum.Output);
                Console.WriteLine(DateTime.Now - dt);
            }
        }

        static IEnumerable<char> GetFileContentBlock(StreamReader sr)
        {
            int size = 65536;
            char[] buf = new char[size];
            int actual;
            do
            {
                actual = sr.ReadBlock(buf, 0, size);
                for (int i = 0; i < actual; ++i)
                    yield return buf[i];
            } while (actual == size);
        }
    }


Вот сам мини-фрейморк:
    public delegate Result<TInput, TOutput> Parser<TInput, TOutput>(EnumeratorEx<TInput> input);

    public static class Parsers
    {
        public static Parser<TSymbol, TSymbol> Satisfy<TSymbol>(Func<TSymbol,bool> predicate)
        {
            return input =>
                !input.IsValid ?
                new Result<TSymbol, TSymbol>(input) :
                    predicate(input.Head) ?
                    new Result<TSymbol, TSymbol>(input.Head, input.GetTail()) :
                    new Result<TSymbol, TSymbol>(input);
        }

        public static Parser<TInput, TOutput> FoldMany<TInput, TParsed, TOutput>(Parser<TInput, TParsed> parser, Func<TOutput, TParsed, TOutput> accumulator, Func<TOutput> seed)
        {
            return input =>
            {
                TOutput accumulated = seed();
                Result<TInput, TParsed> result;
                var curInput = input;
                while ((result = parser(curInput)).Success)
                {
                    accumulated = accumulator(accumulated, result.Output);
                    curInput = result.Remaining;
                }
                return new Result<TInput, TOutput>(accumulated, curInput);
            };
        }

        public static Parser<TInput, LinkedList<TOutput>> Many<TInput, TOutput>(Parser<TInput, TOutput> parser)
        {
            return FoldMany(parser, (LinkedList<TOutput> all, TOutput i) => { all.AddLast(i); return all; }, () => new LinkedList<TOutput>());
        }


        public static Parser<TInput, LinkedList<TOutput>> Many1<TInput, TOutput>(Parser<TInput, TOutput> parser)
        {
            Func<LinkedList<TOutput>,TOutput,LinkedList<TOutput>> car = (LinkedList<TOutput> list, TOutput elem) => {list.AddFirst(elem) ; return list;};

            return from p in parser
                   from rest in Many(parser)
                   select car(rest, p);
        }

        public static Parser<TInput, TOutput> FoldMany1<TInput, TParsed, TOutput>(Parser<TInput, TParsed> parser, Func<TOutput, TParsed, TOutput> accumulator, Func<TOutput> seed)
        {
            return from p in parser
                   from all in FoldMany(parser, accumulator, () => accumulator(seed(), p))
                   select all;
        }

        public static Parser<TInput, TOutput> Fold1Many1<TInput, TOutput>(Parser<TInput, TOutput> parser, Func<TOutput, TOutput, TOutput> accumulator)
        {
            return from p in parser
                   from all in FoldMany(parser, accumulator, () => p)
                   select all;
        }

        public static Parser<TInput, TOutput> Optional<TInput, TOutput>(Parser<TInput, TOutput> parser, TOutput defaultValue)
        {
            return input =>
            {
                if (!input.IsValid)
                    return new Result<TInput, TOutput>(defaultValue, input);
                var input1 = new RollbackableEnumerator<TInput>(input);
                var result1 = parser(input1);
                return result1.Success ?
                    result1 :
                    new Result<TInput, TOutput>(defaultValue, input1.GetMemorized());
            };
        }

        public static Parser<TInput, TOutput> Choise<TInput, TOutput>(params Parser<TInput, TOutput>[] parsers)
        {
            return input =>
            {
                var result1 = new Result<TInput, TOutput>(default(TOutput), input);
                var input1 = new RollbackableEnumerator<TInput>(input);
                foreach (var parser in parsers)
                {
                    result1 = parser(input1);
                    if (result1.Success)
                        break;
                    input1 = new RollbackableEnumerator<TInput>(input1.GetMemorized());
                }
                return result1;
            };
        }

        public static Parser<TInput, TOutput> All<TInput, TParsed, TOutput>(Func<TOutput, TParsed, TOutput> accumulator, Func<TOutput> seed, params Parser<TInput, TParsed>[] parsers)
        {
            return input =>
            {
                var result = seed();
                var input1 = input;
                foreach (var parser in parsers)
                {
                    var result1 = parser(input1);
                    if (!result1.Success)
                        return new Result<TInput, TOutput>(input1);
                    result = accumulator(result, result1.Output);
                    input1 = result1.Remaining;
                }
                return new Result<TInput, TOutput>(result, input1);
            };
        }


Монадные bind и lift
    public static class ParserExtension
    {
        public static Parser<TInput, TOutput> Select<TInput, TIntermediate, TOutput>(this Parser<TInput, TIntermediate> parser, Func<TIntermediate, TOutput> selector)
        {
            return input =>
            {
                var rez = parser(input);
                return rez.Success ?
                    new Result<TInput, TOutput>(selector(rez.Output), rez.Remaining) :
                    new Result<TInput, TOutput>(rez.Remaining);
            };
        }

        public static Parser<TInput, TOutput> SelectMany<TInput, TIntermediate, TIntermediate2, TOutput>
            (this Parser<TInput, TIntermediate> parser, Func<TIntermediate, Parser<TInput, TIntermediate2>> selector, Func<TIntermediate, TIntermediate2, TOutput> projector)
        {
            return input =>
            {
                var rez1 = parser(input);
                if (!(rez1.Success))
                    return new Result<TInput, TOutput>(rez1.Remaining);
                var rez2 = selector(rez1.Output)(rez1.Remaining);
                return rez2.Success ?
                    new Result<TInput, TOutput>(projector(rez1.Output, rez2.Output), rez2.Remaining) :
                    new Result<TInput, TOutput>(rez2.Remaining);
            };
        }
    }


И всякая мелочь до кучи:
    public struct Tuple<T1, T2>
    {
        T1 first;
        T2 second;

        public Tuple(T1 first, T2 second)
        {
            this.first = first;
            this.second = second;
        }

        public T1 First
        {
            get { return first; }
        }

        public T2 Second
        {
            get { return second; }
        }
    }

    public struct Result<TInput, TOutput>
    {
        EnumeratorEx<TInput> remaining;
        TOutput output;
        bool success;

        public Result(TOutput output, EnumeratorEx<TInput> remaining, bool success)
        {
            this.output = output;
            this.remaining = remaining;
            this.success = success;
        }

        public Result(TOutput output, EnumeratorEx<TInput> remaining)
            : this(output, remaining, true)
        {
        }

        public Result(EnumeratorEx<TInput> remaining)
            :this(default(TOutput),remaining,false)
        {
        }

        public bool Success
        {
            get { return success; }
        }

        public EnumeratorEx<TInput> Remaining
        {
            get { return remaining; }
        }

        public TOutput Output
        {
            get { return output; }
        }
    }

    public abstract class EnumeratorEx<T> : IDisposable
    {
        public abstract bool IsValid
        {
            get;
        }

        public abstract EnumeratorEx<T> GetTail();

        public abstract T Head
        {
            get;
        }

        public abstract void Dispose();
    }

    public class StreamEnumerator<T> : EnumeratorEx<T>
    {
        IEnumerator<T> enumerator;
        bool isValid;

        public StreamEnumerator(IEnumerable<T> enumerable)
        {
            this.enumerator = enumerable.GetEnumerator();
            this.isValid = this.enumerator.MoveNext();
        }

        public override bool IsValid
        {
            get { return isValid; }
        }

        public override EnumeratorEx<T> GetTail()
        {
            if (!isValid)
                throw new InvalidOperationException("Cannot move non valid stream enumerator");
            this.isValid = enumerator.MoveNext();
            return this;
        }

        public override T Head
        {
            get
            {
                if (!isValid)
                    throw new InvalidOperationException("Cannot return head for non valid stream enumerator");
                return enumerator.Current;
            }
        }

        #region IDisposable Members

        public override void Dispose()
        {
            enumerator.Dispose();
        }

        #endregion
    }

    public class RollbackableEnumerator<T> : EnumeratorEx<T>
    {
        class RolledBackEnmerator : EnumeratorEx<T>
        {
            Queue<T> log;
            EnumeratorEx<T> real;

            public RolledBackEnmerator(Queue<T> log, EnumeratorEx<T> real)
            {
                this.log = log;
                this.real = real;
            }

            public override bool IsValid
            {
                get { return true; }
            }

            public override EnumeratorEx<T> GetTail()
            {
                if (log.Count == 0)
                    return real;
                log.Dequeue();
                return this;
            }

            public override T Head
            {
                get { return log.Peek(); }
            }

            public override void Dispose()
            {
                real.Dispose();
            }
        }

        EnumeratorEx<T> real;
        Queue<T> log;

        public RollbackableEnumerator(EnumeratorEx<T> from)
        {
            this.real = from;
            this.log = new Queue<T>();
        }

        public EnumeratorEx<T> GetMemorized()
        {
            return log.Count > 0 ?
                new RolledBackEnmerator(log, real) :
                real;
        }

        public override bool IsValid
        {
            get { return real.IsValid; }
        }

        public override EnumeratorEx<T> GetTail()
        {
            log.Enqueue(real.Head);
            return real = real.GetTail();
        }

        public override T Head
        {
            get { return real.Head; }
        }

        public override void Dispose()
        {
            real.Dispose();
        }
    }


Вот такая ужасная попытка переложить функциональный стиль на C#...
Re: Экстренное торможение средствами LINQ
От: Аноним  
Дата: 14.05.09 18:53
Оценка:
K>На E6750 этот парсер работает, с не побоюсь этого слова, феерической скоростью в 0,15 mb/s

Взяло сомнение — решил проверить

Intel E6750 (2.66 Hz)

Решил проверить:

AMD X2 3800 (2.0 Hz) — 0,41 mb/s
Intel Q6600 (2.4 Hz) — 0,82 mb/s

В парсерах не разбираюсь, поэтому предварительно сделал одну оптимизацию

вместо

let Digit = from c in Char(char.IsDigit) select int.Parse(c.ToString())


сделал

let Digit = from c in Char(char.IsDigit) select c
Re[2]: Экстренное торможение средствами LINQ
От: Аноним  
Дата: 15.05.09 04:32
Оценка:
Здравствуйте, Аноним, Вы писали:

K>>На E6750 этот парсер работает, с не побоюсь этого слова, феерической скоростью в 0,15 mb/s


А>Взяло сомнение — решил проверить


А>Intel E6750 (2.66 Hz)


А>Решил проверить:


А>AMD X2 3800 (2.0 Hz) — 0,41 mb/s

А>Intel Q6600 (2.4 Hz) — 0,82 mb/s

А>В парсерах не разбираюсь, поэтому предварительно сделал одну оптимизацию


Оказывается, если собрать под архитектуру x86, тогда и на Q6600 будет примерно 0,15 mb/s.
А вот если собирать под AnyCPU или под x64, то будет уже 0,82 mb/s.
Re[3]: Экстренное торможение средствами LINQ
От: jenyavb  
Дата: 15.05.09 04:39
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>Оказывается, если собрать под архитектуру x86, тогда и на Q6600 будет примерно 0,15 mb/s.

А>А вот если собирать под AnyCPU или под x64, то будет уже 0,82 mb/s.
Лучше всегда, по-возможности, собирать под AnyCPU, так быстрее.
... << RSDN@Home 1.2.0 alpha 4 rev. 1217>>
Re[3]: Экстренное торможение средствами LINQ
От: Klapaucius  
Дата: 15.05.09 06:47
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>Оказывается, если собрать под архитектуру x86, тогда и на Q6600 будет примерно 0,15 mb/s.

А>А вот если собирать под AnyCPU или под x64, то будет уже 0,82 mb/s.

Я тоже собирал под AnyCPU. Но запускал под 32х разрядной ОС.
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[2]: Экстренное торможение средствами LINQ
От: Klapaucius  
Дата: 15.05.09 06:47
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>В парсерах не разбираюсь, поэтому предварительно сделал одну оптимизацию

А>вместо
А>
let Digit = from c in Char(char.IsDigit) select int.Parse(c.ToString())

А>сделал
А>
let Digit = from c in Char(char.IsDigit) select c


Парсер будет работать некорректно. Вместо того, чтобы возводить в степень числовое значение распарсенной цифры, он будет возводить в степень ASCII код цифры.
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re: Экстренное торможение средствами LINQ
От: vdimas Россия  
Дата: 15.05.09 07:16
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>На E6750 этот парсер работает, с не побоюсь этого слова, феерической скоростью в 0,15 mb/s


А если char.IsDigit заменить на свою легковесную ф-ию? Об этот IsDigit уже спотыкались многократно.
Re[2]: Экстренное торможение средствами LINQ
От: Klapaucius  
Дата: 15.05.09 07:58
Оценка:
Здравствуйте, vdimas, Вы писали:

V>А если char.IsDigit заменить на свою легковесную ф-ию? Об этот IsDigit уже спотыкались многократно.


Ну, это одно из изменений, которое сделано здесь
Автор:
Дата: 22.03.08
.
Я-то это все за какие-то минуты написал, а там видно, что человек серьезно отнесся к задаче. Тем не менее — отставание все равно в десятки раз.
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[3]: Экстренное торможение средствами LINQ
От: Аноним  
Дата: 15.05.09 09:12
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>Парсер будет работать некорректно. Вместо того, чтобы возводить в степень числовое значение распарсенной цифры, он будет возводить в степень ASCII код цифры.


Ах, вот оно что.

Впрочем int.Parse(c.ToString()) все равно слишком медленно для случая когда c.IsDigit.

Такой метод-расширение

    public static int ToDigit(this char argument)
    {
        switch (argument)
        {
            case '0': return 0;
            case '1': return 1;
            case '2': return 2;
            case '3': return 3;
            case '4': return 4;
            case '5': return 5;
            case '6': return 6;
            case '7': return 7;
            case '8': return 8;
            case '9': return 9;
        }
        throw new ArgumentException(argument.ToString());
    }


ускоряет mb/s процентов на 10.
Re[4]: Экстренное торможение средствами LINQ
От: Klapaucius  
Дата: 15.05.09 09:24
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>Впрочем int.Parse(c.ToString()) все равно слишком медленно для случая когда c.IsDigit.


А>Такой метод-расширение

А><...>
А>ускоряет mb/s процентов на 10.

А
(int)с - '0'

не проще?
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[2]: Экстренное торможение средствами LINQ
От: Аноним  
Дата: 15.05.09 17:46
Оценка:
Здравствуйте, vdimas, Вы писали:

V>А если char.IsDigit заменить на свою легковесную ф-ию? Об этот IsDigit уже спотыкались многократно.

IsDigit достаточно быстрый. Своя легковесная функция его не ускоряет особо. Другое дело, что IsDigit подходит не только для '0' — '9'.
Re[5]: Экстренное торможение средствами LINQ
От: Аноним  
Дата: 15.05.09 17:56
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>А

K>
K>(int)с - '0' 
K>

K>не проще?
Ну с точки зрения понятности не так ясно, конечно.
Зато по скорости на равных с методом расширением.
Re: Экстренное торможение средствами LINQ
От: Аноним  
Дата: 16.05.09 00:42
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>На E6750 этот парсер работает, с не побоюсь этого слова, феерической скоростью в 0,15 mb/s

Оказывается, если заменить все массивы на IEnumerable<>, а также в реализации Rep сделать цикл вместо рекурсии, как парсер начинает работать со скоростью 2 mb/s на Q6600. В x86 режиме, производительность тоже поднялась до 1 mb/s. Так что на 3 GHz, будет все 2.5 mb/s для x64.

    public Parser<TInput, IEnumerable<TValue>> Rep<TValue>(Parser<TInput, TValue> parser)
    {
        return input =>
        {
            var result = parser(input);

            var values = new List<TValue>();
            
            while (result != null) {
                input = result.Rest;
                values.Add(result.Value);
                result = parser(input);
            }

            return new Result<TInput, IEnumerable<TValue>>(values, input);
        };
        //return Rep1(parser).OR(Succeed(new TValue[0]));
    }
Re[2]: Экстренное торможение средствами LINQ
От: Klapaucius  
Дата: 18.05.09 16:06
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>
А>    public Parser<TInput, IEnumerable<TValue>> Rep<TValue>(Parser<TInput, TValue> parser)
А>    {
А>        return input =>
А>        {
А>            var result = parser(input);

А>            var values = new List<TValue>();
            
А>            while (result != null) {
А>                input = result.Rest;
А>                values.Add(result.Value);
А>                result = parser(input);
А>            }

А>            return new Result<TInput, IEnumerable<TValue>>(values, input);
А>        };
А>        //return Rep1(parser).OR(Succeed(new TValue[0]));
А>    }
А>


Ну, все правильно, отлично подтверждает мой тезис о том, что именно комбинаторы обходятся дорого — переписываем код на комбинаторах в код без них — и получаем ускорение.
... << RSDN@Home 1.2.0 alpha 4 rev. 1110>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[3]: Экстренное торможение средствами LINQ
От: Аноним  
Дата: 18.05.09 18:56
Оценка:
Здравствуйте, Klapaucius, Вы писали:

K>Ну, все правильно, отлично подтверждает мой тезис о том, что именно комбинаторы обходятся дорого — переписываем код на комбинаторах в код без них — и получаем ускорение.

Не совсем. Прикладной-то код остается таким же, как и был, то есть на комбинаторах.
А вот в библиотеке которая их реализует разумнее от них отказаться.

Просто первоначальный автор решил и сами базовые комбинаторы определить друг через друга, рекурсивно.
Что, конечно, привело к тормозам.
Re[2]: Экстренное торможение средствами LINQ
От: Аноним  
Дата: 20.05.09 03:44
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Оказывается, если заменить все массивы на IEnumerable<>, а также в реализации Rep сделать цикл вместо рекурсии, как парсер начинает работать со скоростью 2 mb/s на Q6600. В x86 режиме, производительность тоже поднялась до 1 mb/s. Так что на 3 GHz, будет все 2.5 mb/s для x64.


.NET 4.0 (Q6600) — 2.8 mb/s, на 3 GHz будет вероятно — 3.5 mb/s
Re: Мой вариант на прологе
От: xonixx  
Дата: 23.05.09 21:40
Оценка: 51 (2)
По-моему очень даже красиво и понятно. На ноуте работает 3 мин и потребляет ~5 Mb оперативы max. На Core2Duo ~1мин, т.е. скорость ~1.3Mb/sec. Не быстро, но зато красиво как )

:- set_prolog_flag(float_format,'%.15g').
:- set_prolog_flag(optimize, true).

integer(I) -->
        digit(D0),
        digits(D),
        { number_chars(I, [D0|D])
        }.

digits([D|T]) -->
        digit(D), !,
        digits(T).
digits([]) -->
        [].

digit(D) -->
        [D],
        { code_type(D, digit)
        }.


float(F) -->
    (   "-", {Sign = -1}
    ;   "", {Sign = 1}
    ), !,
    integer(N),
    ",",
    integer(D),
    {F is Sign * (N + D / 10^(ceiling(log10(D))))
    }.

sum(S, Total) -->
    float(F1), !,
    " ",
    { S1 is S + F1},
    sum(S1, Total).
sum(Total, Total) -->
    [].


go1 :-
    phrase_from_file(sum(0, S),'numbers_large.txt', [buffer_size(16384)]),
    writeln(S).
prolog
Re[2]: Мой вариант на прологе
От: FR  
Дата: 26.05.09 08:26
Оценка: +1 :)
Здравствуйте, xonixx, Вы писали:

X>По-моему очень даже красиво и понятно. На ноуте работает 3 мин и потребляет ~5 Mb оперативы max. На Core2Duo ~1мин, т.е. скорость ~1.3Mb/sec. Не быстро, но зато красиво как )


Питон шустрее и красивше

print sum((float(x.replace(',','.')) for x in open("numbers_large.txt").read().split(" ") if x))


Re[3]: Мой вариант на прологе
От: Schade Россия  
Дата: 26.05.09 10:32
Оценка: +2 :)
Здравствуйте, FR, Вы писали:

FR>
FR>print sum((float(x.replace(',','.')) for x in open("numbers_large.txt").read().split(" ") if x))
FR>


Вот только на прологе — по честному на комбинаторах, а на питоне — встроенная функция. Как насчет комбинаторного варианта на питоне? Будет шустрее и красивше?
Re[4]: Мой вариант на прологе
От: thesz Россия http://thesz.livejournal.com
Дата: 26.05.09 14:53
Оценка: :)
FR>>
FR>>print sum((float(x.replace(',','.')) for x in open("numbers_large.txt").read().split(" ") if x))
FR>>

S>Вот только на прологе — по честному на комбинаторах, а на питоне — встроенная функция. Как насчет комбинаторного варианта на питоне? Будет шустрее и красивше?

И где эти комбинаторы в тексте приведённой программы на Прологе?

Надо бы их текст привести тоже. Чтобы можно было настаивать на изменении кода на Питоне.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[5]: Мой вариант на прологе
От: Аноним  
Дата: 28.05.09 09:30
Оценка:
Здравствуйте, thesz, Вы писали:


T>И где эти комбинаторы в тексте приведённой программы на Прологе?

Гм? Текст программы на Прологе процентов на 90 состоит из определения(комбинации) одних парсеров через другие.

T>Надо бы их текст привести тоже. Чтобы можно было настаивать на изменении кода на Питоне.

Насколько я понимаю, не приведены только комбинаторы Or и And ввиду их встроенности в Пролог.
Re[6]: Мой вариант на прологе
От: thesz Россия http://thesz.livejournal.com
Дата: 28.05.09 09:53
Оценка:
T>>Надо бы их текст привести тоже. Чтобы можно было настаивать на изменении кода на Питоне.
А>Насколько я понимаю, не приведены только комбинаторы Or и And ввиду их встроенности в Пролог.

Не приведены комбинаторы --> с фигурными скобочками и что там ещё.

Or/And оставим за границей.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[3]: Мой вариант на прологе
От: Аноним  
Дата: 28.05.09 09:55
Оценка: :)
Здравствуйте, FR, Вы писали:


FR>Питон шустрее и красивше

А где скорость работы?

FR>
FR>print sum((float(x.replace(',','.')) for x in open("numbers_large.txt").read().split(" ") if x))
FR>


Console.WriteLine(Array.ConvertAll(File.ReadAllText(@"c:\numbers_large.txt").Split(' '), value => double.Parse(value)).Sum());
Re[7]: Мой вариант на прологе
От: Аноним  
Дата: 29.05.09 12:17
Оценка:
Здравствуйте, thesz, Вы писали:

T>Не приведены комбинаторы --> с фигурными скобочками и что там ещё.

--> не комбинатор
[], {} вероятно тоже встроены. К тому же на C# их аналоги занимают пять-десять строчек, что непринципиально.

Важен-то прикладной код описания парсера, а не комбинаторы, представляющие операторы EBNF — , | [] {}.
Re[4]: Мой вариант на прологе
От: FR  
Дата: 29.05.09 14:03
Оценка:
Здравствуйте, Аноним, Вы писали:

А>А где скорость работы?


Так шустрее большинства тут

FR>>
FR>>print sum((float(x.replace(',','.')) for x in open("numbers_large.txt").read().split(" ") if x))
FR>>


А>
А>Console.WriteLine(Array.ConvertAll(File.ReadAllText(@"c:\numbers_large.txt").Split(' '), value => double.Parse(value)).Sum());
А>


error CS1061: 'System.Array' does not contain a definition for 'Sum' and no extension method 'Sum' accepting a first argument of type 'System.Array' could be found (are you missing a using directive or an assembly reference?)
Re[8]: Мой вариант на прологе
От: xonixx  
Дата: 29.05.09 15:06
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, thesz, Вы писали:


T>>Не приведены комбинаторы --> с фигурными скобочками и что там ещё.

-->> не комбинатор
А>[], {} вероятно тоже встроены. К тому же на C# их аналоги занимают пять-десять строчек, что непринципиально.

А>Важен-то прикладной код описания парсера, а не комбинаторы, представляющие операторы EBNF — , | [] {}.


Ну в принципе, да, эти вещи встроенные. Если уважаемому thesz интересна реализация этих штук, могу только сказать, что программа с DCG на этапе загрузки использую механизм term expansion преобразуется в обычный прологовский код с предикатами, который далее исполняется. Например если посде consult'а вышеприведенной программы-парсера сделать listing, получим:

sum(C, G, A, I) :-
        float(D, A, B), !,
        B=[32|E],
        F is C+D,
        H=E,
        sum(F, G, H, I).
sum(A, A, B, B).

digit(A, [A|C], B) :-
        code_type(A, digit),
        B=C.

digits([A|C], B, E) :-
        digit(A, B, D), !,
        digits(C, D, E).
digits([], A, A).

integer(C, A, F) :-
        digit(D, A, B),
        digits(E, B, G),
        number_chars(C, [D|E]),
        F=G.

go1 :-
        phrase_from_file(sum(0, A), 'numbers_large.txt', [buffer_size(16384)]),
        writeln(A).

float(H, A, K) :-
        (   A=[45|B],
            C= -1,
            D=B
        ;   E=A,
            C=1,
            D=E
        ), !,
        integer(I, D, F),
        F=[44|G],
        integer(J, G, L),
        H is C* (I+J/10^ceiling(log10(J))),
        K=L.


Из этого можно легко видеть, как происходит преобразование. Как устроен этот преобразователь мне если честно немного лень вникать, но исходники есть в SWI, можно смотреть. Ну и эта штука DCG встроена во все мало-мальски популярные прологи (Sicstus, Gnu, Yap, Amzi, Xsb), т.ч можно просто считать это частью языка.
Re[8]: Мой вариант на прологе
От: thesz Россия http://thesz.livejournal.com
Дата: 29.05.09 20:07
Оценка:
T>>Не приведены комбинаторы --> с фигурными скобочками и что там ещё.
А> --> не комбинатор

С чего бы это?

Он, как раз, обеспечивает преобразование описания a --> b, c. в распознавание a(String,Rest) :- b(String,Rest1), c(Rest1,Rest).

И если уж зашла речь о комбинаторах, попробуйте описать на прологе комбинатор bracketed:
bracketed open close action = do
    open
    x <- action
    close
    return x


А>[], {} вероятно тоже встроены. К тому же на C# их аналоги занимают пять-десять строчек, что непринципиально.

А>Важен-то прикладной код описания парсера, а не комбинаторы, представляющие операторы EBNF — , | [] {}.

В данной конкретной задаче важно всё — базовые комбинаторы, собранные с их помощью разборщики, скорость их работы в комплексе...

Здесь проверяется то, как из простого описания на комбинаторах мы можем раскрутить сложные описания прикладных задач. Во что нам это встанет.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[9]: Мой вариант на прологе
От: thesz Россия http://thesz.livejournal.com
Дата: 29.05.09 20:13
Оценка:
А>>Важен-то прикладной код описания парсера, а не комбинаторы, представляющие операторы EBNF — , | [] {}.
X>Ну в принципе, да, эти вещи встроенные. Если уважаемому thesz интересна реализация этих штук, могу только сказать, что программа с DCG на этапе загрузки использую механизм term expansion преобразуется в обычный прологовский код с предикатами, который далее исполняется.

Вот. Так и привели бы, чего кота тянуть за хвост.

Про DCG я знаю, они в PTAPG описываются.

X>Из этого можно легко видеть, как происходит преобразование. Как устроен этот преобразователь мне если честно немного лень вникать, но исходники есть в SWI, можно смотреть. Ну и эта штука DCG встроена во все мало-мальски популярные прологи (Sicstus, Gnu, Yap, Amzi, Xsb), т.ч можно просто считать это частью языка.


А можно ли сделать что-то типа DCG для какой-либо другой задачи? А насколько эффективно получится?

Поэтому я и поднял вопрос о том, что желательно бы на них посмотреть.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[9]: Мой вариант на прологе
От: xonixx  
Дата: 29.05.09 20:56
Оценка:
Здравствуйте, thesz, Вы писали:

T>И если уж зашла речь о комбинаторах, попробуйте описать на прологе комбинатор bracketed:

T>
T>bracketed open close action = do
T>    open
T>    x <- action
T>    close
T>    return x
T>


типа такого http://xonix.habrahabr.ru/blog/50693/ ?
Re[10]: Мой вариант на прологе
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 30.05.09 04:30
Оценка:
Здравствуйте, xonixx, Вы писали:

X>типа такого http://xonix.habrahabr.ru/blog/50693/ ?


Нет, совсем другое. Речь про аналог try/finally.
Re[5]: Мой вариант на прологе
От: Аноним  
Дата: 30.05.09 04:54
Оценка:
Здравствуйте, FR, Вы писали:

FR>Так шустрее большинства тут

Так где измерение скорости внутри кода?

FR>error CS1061: 'System.Array' does not contain a definition for 'Sum' and no extension method 'Sum' accepting a first argument of type 'System.Array' could be found (are you missing a using directive or an assembly reference?)

System.Linq?
Re[9]: Мой вариант на прологе
От: Аноним  
Дата: 30.05.09 05:06
Оценка:
Здравствуйте, thesz, Вы писали:

T>С чего бы это?


T>Он, как раз, обеспечивает преобразование описания a --> b, c. в распознавание a(String,Rest) :- b(String,Rest1), c(Rest1,Rest).

Это не --> обеспечивает, а [Head|Tail], a([Head|Tail]) --> b(Head,Tail1), c(Tail1,Tail).

T>И если уж зашла речь о комбинаторах, попробуйте описать на прологе комбинатор bracketed:

В прологе как ни странно, не разбираюсь.

T>В данной конкретной задаче важно всё — базовые комбинаторы, собранные с их помощью разборщики, скорость их работы в комплексе...

Да ладно, всё. Тут сравниваются слишком разные языки и на разных платформах, и во многих из них некоторые конструкции уже встроены в язык.
Так что важно как выглядит более-менее сложный парсер, ну и скорость его работы.

T>Здесь проверяется то, как из простого описания на комбинаторах мы можем раскрутить сложные описания прикладных задач. Во что нам это встанет.

Никакого множества сложных прикладных задач тут нет, речь идет о преобразовании строки в число с плавающей точкой.
Настолько трививальная задача, что она уже содержится в библиотечных функциях в большинстве языков.
Re[10]: Мой вариант на прологе
От: thesz Россия http://thesz.livejournal.com
Дата: 30.05.09 08:07
Оценка:
T>>И если уж зашла речь о комбинаторах, попробуйте описать на прологе комбинатор bracketed:
T>>
T>>bracketed open close action = do
T>>    open
T>>    x <- action
T>>    close
T>>    return x
T>>


X>типа такого http://xonix.habrahabr.ru/blog/50693/ ?


Нет.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[10]: Мой вариант на прологе
От: thesz Россия http://thesz.livejournal.com
Дата: 30.05.09 08:10
Оценка:
T>>Он, как раз, обеспечивает преобразование описания a --> b, c. в распознавание a(String,Rest) :- b(String,Rest1), c(Rest1,Rest).
А>Это не --> обеспечивает, а [Head|Tail], a([Head|Tail]) --> b(Head,Tail1), c(Tail1,Tail).

Читайте про DCG. Как мне это надоело.

T>>И если уж зашла речь о комбинаторах, попробуйте описать на прологе комбинатор bracketed:

А>В прологе как ни странно, не разбираюсь.

Как и во всём другом.

T>>В данной конкретной задаче важно всё — базовые комбинаторы, собранные с их помощью разборщики, скорость их работы в комплексе...

А>Да ладно, всё. Тут сравниваются слишком разные языки и на разных платформах, и во многих из них некоторые конструкции уже встроены в язык.

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

А>Так что важно как выглядит более-менее сложный парсер, ну и скорость его работы.


Важно, как собирается сложная система и чем может помочь компилятор в плане скорости ее выполнения.

T>>Здесь проверяется то, как из простого описания на комбинаторах мы можем раскрутить сложные описания прикладных задач. Во что нам это встанет.

А>Никакого множества сложных прикладных задач тут нет, речь идет о преобразовании строки в число с плавающей точкой.

Есть. "Внимательней вглядись" (С) Басё

А>Настолько трививальная задача, что она уже содержится в библиотечных функциях в большинстве языков.


Не содержится.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[5]: Мой вариант на прологе
От: Schade Россия  
Дата: 30.05.09 10:56
Оценка:
Здравствуйте, FR, Вы писали:

FR>Так шустрее большинства тут


FR>>>
FR>>>print sum((float(x.replace(',','.')) for x in open("numbers_large.txt").read().split(" ") if x))
FR>>>


Используя встроенные функции можно конечно и так написать
sumFile :: String -> IO Double
sumFile = fmap (foldl' (+) 0.0 . fmap read . words) . readFile

и не городить весь этот огород
Смысл-то в разборе более сложных структур, чем даблы. А смысл даблов — померять скорость, не более того.
Re[6]: Мой вариант на прологе
От: FR  
Дата: 30.05.09 11:37
Оценка:
Здравствуйте, Аноним, Вы писали:

FR>>error CS1061: 'System.Array' does not contain a definition for 'Sum' and no extension method 'Sum' accepting a first argument of type 'System.Array' could be found (are you missing a using directive or an assembly reference?)

А>System.Linq?

Теперь

Unhandled Exception: System.FormatException: Input string was not in a correct format.
at System.Number.StringToNumber(String str, NumberStyles options, NumberBuffer& number, NumberFormatInfo info, Boolean parseDecimal)
at System.Number.ParseDouble(String value, NumberStyles options, NumberFormatInfo numfmt)
at System.Double.Parse(String s, NumberStyles style, NumberFormatInfo info)
at MainApp.<Main>b__0(String value)
at System.Array.ConvertAll[TInput,TOutput](TInput[] array, Converter`2 converter)
at MainApp.Main()

Похоже умирает на лишнем пустой строчке
Re[11]: Мой вариант на прологе
От: Аноним  
Дата: 30.05.09 12:55
Оценка:
Здравствуйте, thesz, Вы писали:

T>Читайте про DCG.

Читайте.

T>Как мне это надоело.

Надеюсь, никто с паяльником не стоит над душой?

T>Как и во всём другом.

Зато как мне приятно тратить ваше время.

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

Да ладно, всё. Потрудитесь в конце концов изучить то, о чём неумело пытаетесь спорить.

T>Важно, как собирается сложная система и чем может помочь компилятор в плане скорости ее выполнения.

Хе-хе, собирается, стало быть.

T>Есть. "Внимательней вглядись" (С) Басё

Нет. Хотя, конечно, если долго всматриваться в бездну, то и бездна начинает всматриваться в тебя. (с) Ницше.

T>Не содержится.

Содержится.
Re[11]: Мой вариант на прологе
От: xonixx  
Дата: 30.05.09 13:00
Оценка:
Здравствуйте, D. Mon, Вы писали:

DM>Здравствуйте, xonixx, Вы писали:


X>>типа такого http://xonix.habrahabr.ru/blog/50693/ ?


DM>Нет, совсем другое. Речь про аналог try/finally.


можно пример или ссылочку?
Re[7]: Мой вариант на прологе
От: Аноним  
Дата: 30.05.09 13:09
Оценка:
Здравствуйте, FR, Вы писали:

FR>Теперь


FR>Unhandled Exception: System.FormatException: Input string was not in a correct format.

FR> at System.Number.StringToNumber(String str, NumberStyles options, NumberBuffer& number, NumberFormatInfo info, Boolean parseDecimal)
FR> at System.Number.ParseDouble(String value, NumberStyles options, NumberFormatInfo numfmt)
FR> at System.Double.Parse(String s, NumberStyles style, NumberFormatInfo info)
FR> at MainApp.<Main>b__0(String value)
FR> at System.Array.ConvertAll[TInput,TOutput](TInput[] array, Converter`2 converter)
FR> at MainApp.Main()

FR>Похоже умирает на лишнем пустой строчке

Эээ, сами поправите?
Re[12]: Мой вариант на прологе
От: FR  
Дата: 30.05.09 13:14
Оценка:
Здравствуйте, xonixx, Вы писали:


DM>>Нет, совсем другое. Речь про аналог try/finally.


X>можно пример или ссылочку?


http://www.gnu.org/software/emacs/elisp/html_node/Cleanups.html
Re[8]: Мой вариант на прологе
От: FR  
Дата: 30.05.09 13:14
Оценка: +1 :)))
Здравствуйте, Аноним, Вы писали:

FR>>Похоже умирает на лишнем пустой строчке

А>Эээ, сами поправите?

Не мне удобнее считать что шарп сливает
Re[13]: Мой вариант на прологе
От: xonixx  
Дата: 30.05.09 13:49
Оценка:
Здравствуйте, FR, Вы писали:

FR>Здравствуйте, xonixx, Вы писали:



DM>>>Нет, совсем другое. Речь про аналог try/finally.


X>>можно пример или ссылочку?


FR>http://www.gnu.org/software/emacs/elisp/html_node/Cleanups.html


Ну в прологе (по крайней мере, в SWI) тоже есть исключения

 ?- catch((writeln('Test1...'),
|    throw(exc('Ups..')),
|    writeln('Unachievable..')), exc(E), writeln(E)).
Test1...
Ups..
E = 'Ups..'.


Сдается, товарищи выше имели в виду что-то более конкретное...
Re[14]: Мой вариант на прологе
От: thesz Россия http://thesz.livejournal.com
Дата: 30.05.09 14:14
Оценка:
DM>>>>Нет, совсем другое. Речь про аналог try/finally.
X>>>можно пример или ссылочку?
FR>>http://www.gnu.org/software/emacs/elisp/html_node/Cleanups.html
X>Ну в прологе (по крайней мере, в SWI) тоже есть исключения
X>
X> ?- catch((writeln('Test1...'),
X>|    throw(exc('Ups..')),
X>|    writeln('Unachievable..')), exc(E), writeln(E)).
X>Test1...
X>Ups..
X>E = 'Ups..'.
X>


X>Сдается, товарищи выше имели в виду что-то более конкретное...


Именно.

Я имел в виду функции высших порядков.

import Control.Monad.State
import Control.Monad.List

type P a = StateT String [] a

pitem :: P Char
pitem = do
    cs <- get
    case cs of
        (c:cs) -> do
            put cs
            return c
        _ -> mzero

psat p = do
    x <- pitem
    if p x then return x else mzero

pchar c = psat (==c)

pmany p = pmany1 p `mplus` return []
pmany1 p = do
    x <- p
    xs <- pmany p
    return $ x:xs

bracketed open close action = do
    open
    x <- action
    close
    return x

braced = bracketed (pchar '(') (pchar ')')

balanced = do {pmany (braced balanced); return ()}


Твой самый первый пример выражен в самом конце.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[14]: Мой вариант на прологе
От: FR  
Дата: 30.05.09 14:37
Оценка:
Здравствуйте, xonixx, Вы писали:

X>Сдается, товарищи выше имели в виду что-то более конкретное...


Имелось в виду что эти "исключения" делются штатными средствами языка.
Re[15]: Мой вариант на прологе
От: xonixx  
Дата: 30.05.09 14:46
Оценка:
X>>Сдается, товарищи выше имели в виду что-то более конкретное...

T>Именно.


T>Я имел в виду функции высших порядков.


T>
T>import Control.Monad.State
T>import Control.Monad.List

T>type P a = StateT String [] a

T>pitem :: P Char
T>pitem = do
T>    cs <- get
T>    case cs of
T>        (c:cs) -> do
T>            put cs
T>            return c
T>        _ -> mzero

T>psat p = do
T>    x <- pitem
T>    if p x then return x else mzero

T>pchar c = psat (==c)

T>pmany p = pmany1 p `mplus` return []
T>pmany1 p = do
T>    x <- p
T>    xs <- pmany p
T>    return $ x:xs

T>bracketed open close action = do
T>    open
T>    x <- action
T>    close
T>    return x

T>braced = bracketed (pchar '(') (pchar ')')

T>balanced = do {pmany (braced balanced); return ()}
T>


T>Твой самый первый пример выражен в самом конце.


Я правильно понял, что в функция высшего порядка это pmany?

Тогда можно как-то так сообразить:

many(What) -->
    What,
    many(What).
many(_) --> [].

bracketed(Open, Close, What) -->
    Open,
    What,
    Close.

braced(What) --> bracketed("(", ")", What).
braced(What) --> bracketed("{", "}", What).
braced(What) --> bracketed("[", "]", What).

balanced -->
    many(braced(balanced)).

test :-
    phrase(balanced, "[](){[{()}]}"),
    phrase(balanced, "[[[()]]]({}{{[]}})[{}]()[]"),
    \+ phrase(balanced, "[[[()]]]({[}{{[]}})[{}]()[]").



?- test.
true .
Re[16]: Мой вариант на прологе
От: thesz Россия http://thesz.livejournal.com
Дата: 30.05.09 20:33
Оценка:
X>>>Сдается, товарищи выше имели в виду что-то более конкретное...
T>>Именно.
T>>Я имел в виду функции высших порядков.
T>>Твой самый первый пример выражен в самом конце.
X>Я правильно понял, что в функция высшего порядка это pmany?

pmany, pmany1, bracketed, braced, sqbracketed.

X>Тогда можно как-то так сообразить:

X>
X>...
X>test :-
X>    phrase(balanced, "[](){[{()}]}"),
X>    phrase(balanced, "[[[()]]]({}{{[]}})[{}]()[]"),
X>    \+ phrase(balanced, "[[[()]]]({[}{{[]}})[{}]()[]").
X>


Это я понял.

И какая у этого производительность?

Если переписать те же digits через pmany, что получится, какая скорость?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[9]: Мой вариант на прологе
От: Аноним  
Дата: 31.05.09 05:33
Оценка:
Здравствуйте, FR, Вы писали:

FR>Не мне удобнее считать что шарп сливает

Не вам? А кому удобнее считать?
Re[5]: Мой вариант на прологе
От: Аноним  
Дата: 31.05.09 07:17
Оценка:
Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Аноним, Вы писали:


А>>А где скорость работы?


FR>Так шустрее большинства тут

Проверил на IronPython, следующий код

from System.Diagnostics import Stopwatch

s = Stopwatch()
s.Start()

print sum((float(value.replace(',','.')) for value in open("c:\\numbers_large.txt").read().split(" ") if value))

s.Stop()

print s.ElapsedMilliseconds


На Q6600 отработал за 24 секунды
Аналог на C# отработал за 4 секунды.
Re[6]: Мой вариант на прологе
От: FR  
Дата: 31.05.09 13:25
Оценка:
Здравствуйте, Аноним, Вы писали:

А>На Q6600 отработал за 24 секунды

А>Аналог на C# отработал за 4 секунды.

Аналог на C# засекречен?
Re[10]: Мой вариант на прологе
От: FR  
Дата: 31.05.09 13:26
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, FR, Вы писали:


FR>>Не мне удобнее считать что шарп сливает

А>Не вам? А кому удобнее считать?

У меня запятая на клавиатуре сломалась
Re[17]: Мой вариант на прологе
От: xonixx  
Дата: 31.05.09 21:50
Оценка:
Здравствуйте, thesz, Вы писали:

T>Это я понял.


T>И какая у этого производительность?


T>Если переписать те же digits через pmany, что получится, какая скорость?


переписал так:

:- set_prolog_flag(float_format,'%.15g').

many1(What, [H | T]) -->
    call(What, H), !,
    many1(What, T).
many1(_, []) --> [].


integer(I) -->
        many1(digit, [D|DD]),
    { number_chars(I, [D|DD])
        }.

digit(D) -->
        [D],
        { code_type(D, digit)
        }.


float(F) -->
    (   "-", {Sign = -1}
    ;   "", {Sign = 1}
    ), !,
    integer(N),
    ",",
    integer(D),
    {F is Sign * (N + D / 10^(ceiling(log10(D))))
    }.

sum(S, Total) -->
    float(F1), !,
    " ",
    { S1 is S + F1},
    sum(S1, Total).
sum(Total, Total) -->
    [].

go1 :-
    phrase_from_file(sum(0, S),'numbers_large.txt', [buffer_size(16384)]),
    writeln(S).


да, скорость в легкую подупала (1мин 6 сек -> 1 мин 20 сек, вероятнее всего из-за использования call). Потребление памяти не изменилось.
prolog
Re[7]: Мой вариант на прологе
От: Аноним  
Дата: 02.06.09 15:54
Оценка:
Здравствуйте, FR, Вы писали:

FR>Аналог на C# засекречен?

Скорее тривиален.
Console.WriteLine((from value in File.ReadAllText(@"c:\numbers_large.txt").Split(' ') where value !=  "" select double.Parse(value)).Sum());
Re[8]: Мой вариант на прологе
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 02.06.09 17:32
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Скорее тривиален.

А>
А>Console.WriteLine((from value in File.ReadAllText(@"c:\numbers_large.txt").Split(' ') where value !=  "" select double.Parse(value)).Sum());
А>


Сколько мегов в секунду, кстати?
Re[9]: Мой вариант на прологе
От: Аноним  
Дата: 02.06.09 18:20
Оценка:
Здравствуйте, D. Mon, Вы писали:

DM>Сколько мегов в секунду, кстати?

25 mb/s на Q6600.

Split, понятно, тормозит.

Если заменить на такой:

public static class StringHelper
{
    public static IEnumerable<string> AsyncSplit(this string value, char delimiter)
    {
        int start = 0;
        int index = value.IndexOf(delimiter, start);

        while (index != -1)
        {
            yield return value.Substring(start, index - start);
            start = index + 1;
            index = value.IndexOf(delimiter, start);
        }
    }
}


то будет 33 mb/s.
Re[8]: Мой вариант на прологе
От: FR  
Дата: 03.06.09 05:33
Оценка: :)
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, FR, Вы писали:


FR>>Аналог на C# засекречен?

А>Скорее тривиален.
А>
А>Console.WriteLine((from value in File.ReadAllText(@"c:\numbers_large.txt").Split(' ') where value !=  "" select double.Parse(value)).Sum());
А>


Тык мы языкам необучены, спасибо что снизошли

Да в четыре раза шустрее питона, но корявей немного. В общем третий шарп уже достаточно выразителен.
Re: Haskell :: не такой тормоз, как кажется
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 04.06.09 07:02
Оценка: 5 (1)
Весной для Сапки делал на Окамле классические парсер-комбинаторы на списках, на обуждаемой тут задачке про даблы сам разбор получился 23 МБ/с (на 2.33 GHz), но это если не учитывать перевод строки в список. А если учитывать, то только 7.8 МБ/с.

На днях попробовал в качестве proof of concept сделать оптимизирующие парсер-комбинаторы. Получилось не так элегантно, зато шустро — 35 МБ/с, т.е. на машине топикстартера можно ожидать 46 МБ/с — чуть быстрее Спирита. И при такой скорости никакой кодогенерации не используется, парсер создается динамически, как обычно воспроизводя грамматику.
Подробности про оба тут:
http://thedeemon.livejournal.com/1155.html#cutid1
ocaml parsers
Re[2]: Haskell :: не такой тормоз, как кажется
От: FR  
Дата: 04.06.09 07:44
Оценка:
Здравствуйте, D. Mon, Вы писали:

DM>Весной для Сапки делал на Окамле классические парсер-комбинаторы на списках, на обуждаемой тут задачке про даблы сам разбор получился 23 МБ/с (на 2.33 GHz), но это если не учитывать перевод строки в список. А если учитывать, то только 7.8 МБ/с.


Да в OCaml не хватает прямого паттерн матчинга по строкам.
Для этой задачи правильнее указывать не частоту процессора, а скорость работы памяти и размер кеша процессора

DM>На днях попробовал в качестве proof of concept сделать оптимизирующие парсер-комбинаторы. Получилось не так элегантно, зато шустро — 35 МБ/с, т.е. на машине топикстартера можно ожидать 46 МБ/с — чуть быстрее Спирита. И при такой скорости никакой кодогенерации не используется, парсер создается динамически, как обычно воспроизводя грамматику.

DM>Подробности про оба тут:
DM>http://thedeemon.livejournal.com/1155.html#cutid1

Хотелось бы цельный исходник
Re[3]: Haskell :: не такой тормоз, как кажется
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 04.06.09 15:37
Оценка: 5 (1)
Здравствуйте, FR, Вы писали:

FR>Хотелось бы цельный исходник


исходник и собранный exe
Re[4]: Haskell :: не такой тормоз, как кажется
От: Димчанский Литва http://dimchansky.github.io/
Дата: 04.06.09 15:49
Оценка:
Здравствуйте, D. Mon, Вы писали:

DM>исходник и собранный exe


У меня exe вываливается:

Fatal error: exception Invalid_argument("String.create")

Re[5]: Haskell :: не такой тормоз, как кажется
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 04.06.09 22:20
Оценка:
Собран 32-битной версией, там строки ограничены 16 мегами. Т.е. нужен поменьше файл.
Re[6]: Haskell :: не такой тормоз, как кажется
От: FR  
Дата: 05.06.09 04:16
Оценка: 3 (1)
Здравствуйте, D. Mon, Вы писали:

DM>Собран 32-битной версией, там строки ограничены 16 мегами. Т.е. нужен поменьше файл.


Надо было на потоках (Module Stream) сделать.
Re[2]: Haskell :: не такой тормоз, как кажется
От: FR  
Дата: 05.06.09 10:13
Оценка:
Здравствуйте, D. Mon, Вы писали:

DM>Ради интереса изобразил нечто подобное на OCaml с использованием enumerations из ExtLib.

DM>На Core2Duo 2.0 GHz получается всего 3,8 МБ/с..

Попробовал переделать на потоки, у меня с 2.79 МБ/с стало 10.70 МБ/с ну и без проблем кушает 80 метровый файл.

let (>>=) o f = match o with Some x -> f x | None -> None;;
let (>>) x f = f x;;

let digit c = c>='0' && c<='9';;

let p_pred p e =
  match Stream.peek e with 
  | Some c when p c -> Stream.junk e; Some c
  | _ -> None;;
  
let manyf prs f s e =
  let rec frec v =
    match prs e with
    | Some c -> frec (f v c)
    | None -> v
  in frec s;;    
  
let rec many prs e = 
  match prs e with
  | Some _ -> many prs e
  | None -> ();;
  
let mkInt v c = v*10 + (int_of_char c) - 48;;
let mkFrac (fv,fr) c = (fv +. (float_of_int ((int_of_char c)-48))*.fr, fr*.0.1);;

let p_spaces = many (p_pred ((=) ' '));;
let p_sign e = match p_pred ((=) '-') e with Some _ -> -1.0 | None -> 1.0;;
let p_int e = Some (manyf (p_pred digit) mkInt 0 e);;
let p_dot = p_pred ((=) ',');;
let p_frac e = let (fv,fr) = manyf (p_pred digit) mkFrac (0.0, 0.1) e in Some fv;; 

let p_float e = 
  p_spaces e >> fun _ ->
  p_sign e >> fun s ->
  p_int e >>= fun n ->
  p_dot e >>= fun _ ->
  p_frac e >>= fun fr ->
  Some(s *. ((float_of_int n) +. fr));;  

let sumNumbers = manyf p_float (+.) 0.0;;

let measured f =
  let t0 = Unix.times() in
  let _ = f () in
  let t1 = Unix.times() in
  t1.Unix.tms_utime -. t0.Unix.tms_utime;;

let ic = open_in "numbers_large.txt" in
let str = Stream.of_channel ic in
let t = measured (fun ()->print_float (sumNumbers  str)) in
close_in ic;
Printf.printf " %f s, %f MB/s\n" t ((float_of_int (Stream.count str)) /. t /. 1048576.0);;
Re[6]: Мой вариант на прологе
От: FR  
Дата: 05.06.09 13:02
Оценка:
Здравствуйте, Schade, Вы писали:

S>Используя встроенные функции можно конечно и так написать

S>
S>sumFile :: String -> IO Double
S>sumFile = fmap (foldl' (+) 0.0 . fmap read . words) . readFile
S>

S>и не городить весь этот огород
S>Смысл-то в разборе более сложных структур, чем даблы. А смысл даблов — померять скорость, не более того.

Не заметил раньше. Ну пошутить уже нельзя
Но все равно интересно померять скорость и для встроенных функций, так что хотелось бы полный компилируемый код.
Re[7]: Мой вариант на прологе
От: Schade Россия  
Дата: 05.06.09 14:16
Оценка:
Здравствуйте, FR, Вы писали:

FR>Но все равно интересно померять скорость и для встроенных функций, так что хотелось бы полный компилируемый код.


Чудес не будет.

{-# LANGUAGE BangPatterns  #-}

module Main where

import System.Time
import System.IO
import Data.List

sumFile :: String -> IO Double
sumFile = fmap (foldl' (+) 0.0 . fmap read . words) . readFile

measured :: IO a -> IO (a, Double)
measured act = do
  let getSeconds t = fromIntegral (tdPicosec t) / 1000000000000.0 + fromIntegral (tdSec t)
  start <- getClockTime
  !r <- act
  end <- getClockTime
  let delta = getSeconds $ diffClockTimes end start
  return (r, delta)

main = do
   (s, time) <- measured $ sumFile "d:\\numbers_large.txt"
   putStrLn $ "Sum: " ++ show s
   putStrLn $ "Time: " ++ show time ++ " s."


GHC 6.10.1. 179 секунд. Ленивый список на 80 с гаком млн. элементов — не самая быстрая структура данных
Re[8]: Мой вариант на прологе
От: FR  
Дата: 05.06.09 15:21
Оценка:
Здравствуйте, Schade, Вы писали:

S>Чудес не будет.


.....

S>GHC 6.10.1. 179 секунд. Ленивый список на 80 с гаком млн. элементов — не самая быстрая структура данных


Да прикольно, медленее питона
Re[8]: Мой вариант на прологе
От: FR  
Дата: 05.06.09 15:25
Оценка:
Здравствуйте, Schade, Вы писали:

S>GHC 6.10.1. 179 секунд. Ленивый список на 80 с гаком млн. элементов — не самая быстрая структура данных


Да на компьютере с русской локалью (с запятой вместо точки) не работает выше на питоне и шарпе это учитывалось, и была замена в строках запятой на точку.
Re[9]: Мой вариант на прологе
От: Буравчик Россия  
Дата: 06.06.09 07:26
Оценка: 1 (1)
Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Schade, Вы писали:


S>>Чудес не будет.


FR>.....


S>>GHC 6.10.1. 179 секунд. Ленивый список на 80 с гаком млн. элементов — не самая быстрая структура данных


FR>Да прикольно, медленее питона


В GHC надо использовать ByteString вместо строк. Будет на порядок быстрее.
... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>
Best regards, Буравчик
Re[7]: Haskell :: не такой тормоз, как кажется
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 08.06.09 17:11
Оценка:
Здравствуйте, FR, Вы писали:

FR>Надо было на потоках (Module Stream) сделать.


Чего-то я задумался, а как на потоках делать комбинатор альтернативы (a|b)? Нужна возможность отката. В Enum'ах можно было сделать clone. А в Stream'ax?

И еще, кто-нибудь в курсе как в классических парсер-комбинаторах на Окамле делают рекурсивные правила?
Re[8]: Haskell :: не такой тормоз, как кажется
От: FR  
Дата: 09.06.09 07:12
Оценка:
Здравствуйте, D. Mon, Вы писали:

DM>Чего-то я задумался, а как на потоках делать комбинатор альтернативы (a|b)? Нужна возможность отката. В Enum'ах можно было сделать clone. А в Stream'ax?


Отката в потоках нет, но есть возможность посмотреть n элементов не двигая указателя — npeek

DM>И еще, кто-нибудь в курсе как в классических парсер-комбинаторах на Окамле делают рекурсивные правила?


Можно примерчик того что именно нужно?
Re[8]: Haskell :: не такой тормоз, как кажется
От: FR  
Дата: 09.06.09 07:45
Оценка:
Здравствуйте, D. Mon, Вы писали:


DM>Чего-то я задумался, а как на потоках делать комбинатор альтернативы (a|b)? Нужна возможность отката. В Enum'ах можно было сделать clone. А в Stream'ax?


Да еще camlp4 предоставляет расширение — destructive matching то есть PM для потоков плюс конструкторы потоков [< >], с этим можно любые откаты сделать.
Re[9]: Haskell :: не такой тормоз, как кажется
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 09.06.09 16:48
Оценка:
Здравствуйте, FR, Вы писали:

FR>Отката в потоках нет, но есть возможность посмотреть n элементов не двигая указателя — npeek


Пока неясно, как она может помочь в комбинаторах.
Например, недавно делал раскраску кода, нужно было уметь отличать тэги вроде None или Some от названий модулей типа Array. Отличить их в коде можно по точке после имени модуля. Классический ПК с откатами пытается разобрать сначала как имя модуля, если точки нет, то идет откат и тот же текст пытается разобрать как тэг. Как это можно сделать при помощи npeek? Или при помощи destructive PM?


DM>>И еще, кто-нибудь в курсе как в классических парсер-комбинаторах на Окамле делают рекурсивные правила?


FR>Можно примерчик того что именно нужно?


Например, let p_expr = p_ident ||| ( p_char '(' >>> p_expr >>> p_char ')' );;
Re[10]: Haskell :: не такой тормоз, как кажется
От: FR  
Дата: 10.06.09 04:47
Оценка:
Здравствуйте, D. Mon, Вы писали:

FR>>Отката в потоках нет, но есть возможность посмотреть n элементов не двигая указателя — npeek


DM>Пока неясно, как она может помочь в комбинаторах.

DM>Например, недавно делал раскраску кода, нужно было уметь отличать тэги вроде None или Some от названий модулей типа Array. Отличить их в коде можно по точке после имени модуля. Классический ПК с откатами пытается разобрать сначала как имя модуля, если точки нет, то идет откат и тот же текст пытается разобрать как тэг. Как это можно сделать при помощи npeek? Или при помощи destructive PM?

Да npeek неудобен, практически придется писать эмуляцию того же emun.
destructive PM вполне подойдет, у него откат автоматически если образец не сопоставился то и поток останется неизменным. Правда с ним могут быть проблемы в сложных комбинаторах при общем откате.

DM>>>И еще, кто-нибудь в курсе как в классических парсер-комбинаторах на Окамле делают рекурсивные правила?


FR>>Можно примерчик того что именно нужно?


DM>Например, let p_expr = p_ident ||| ( p_char '(' >>> p_expr >>> p_char ')' );;


destructive PM рекурсию допускает, например:
# let rec sum = parser [<'n; r=sum>] -> n + r | [<>] -> 0;;
val sum : int Stream.t -> int = <fun>
# sum [<'1; '2; '3>];;
- : int = 6
#
Re[10]: Haskell :: не такой тормоз, как кажется
От: FR  
Дата: 10.06.09 05:09
Оценка: 6 (1)
Здравствуйте, D. Mon, Вы писали:

Тут http://www.ffconsultancy.com/ocaml/benefits/parsing.html примерчик как раз по теме.
Re: Haskell :: не такой тормоз, как кажется
От: VladD2 Российская Империя www.nemerle.org
Дата: 08.12.10 20:53
Оценка:
Здравствуйте, Schade, Вы писали:
S>
S>module Main (main) where...
S>


Изучать эту кучу кода очень не хочется. А можно для интересующихся привести грамматику в виде BNF или чем-то похожем (регексы, PEG...)?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Haskell :: не такой тормоз, как кажется
От: andrey_nado  
Дата: 08.12.10 21:16
Оценка:
Здравствуйте, Schade, Вы писали:

S>[haskell]

S>{-# LANGUAGE NoMonomorphismRestriction, FlexibleInstances,
S> MultiParamTypeClasses, FunctionalDependencies,
S> BangPatterns #-}

А сильно изменится скорость работы если убрать эти опции?
Re[2]: Haskell :: не такой тормоз, как кажется
От: deniok Россия  
Дата: 08.12.10 21:30
Оценка:
Здравствуйте, andrey_nado, Вы писали:

_>Здравствуйте, Schade, Вы писали:


S>>[haskell]

S>>{-# LANGUAGE NoMonomorphismRestriction, FlexibleInstances,
S>> MultiParamTypeClasses, FunctionalDependencies,
S>> BangPatterns #-}

_>А сильно изменится скорость работы если убрать эти опции?


Код не скомпилируется — это более-менее стандартные расширения языка из GHC.
Re: Haskell :: не такой тормоз, как кажется
От: VladD2 Российская Империя www.nemerle.org
Дата: 09.12.10 00:10
Оценка: 4 (2) +2
Здравствуйте, Schade, Вы писали:

S>Результат работы (Core2Duo 3,12 ггц)

S>Haskell — ~1.56 секунды. 52,5 мб/сек.
S>C++ (spirit) — ~1.88 секунды. 44 мб/сек. Правда, если рантайм сменить с DLL на статически линкуемый, то ~1.65 секунды.
S>Вот так. Haskell вровень с C++, и даже опережает.
S>Хотел привести еще то же решение на F#, но если не скатываться к традиционному императивному решению (а зачем тогда F# нужен?), быстрее 10 сек. пока не получилось.
S>Вообще, старичок двухплюсатый все равно на высоте — если все переписать вручную (код тупой, приводить не охота), отрабатывает за 0,45 сек. Только ведь в более сложном случае вероятность такого ручного расписывания невелика.

Откровенно говоря тест тупой. Назвать это битовыжимание парсингом у меня язык не поворачивается. Регулярная грамматика не показатель для парсеров. Банальная функция преобразования строки в число в дотнете отжирает времени больше чем сам парсинг.

Ради спортивного интереса накатал парсер на основе Nemerle-ового макроса PegGrammar. Код приведен в конце сообщения.
К сожалению грамматики не нашел, поэтому ориентировался на формат файла генератор которого был приведен в теме. Кстати, в нем надо было seed прописать явно. А то ведь при каждой генерации новые набор чисел получается. А это может повлиять на время. Не хорошо.

Результат на моем Core 2 2.83 Ггц — 1.26 сек. (конфигурация Release + no pdb + запуск без отладчика).
Так что Хаскель конечно крут, но наш брат таки рвет его потихоничку. Причем не самопалами с объемом кода на 5 экранов, а самым что ни наесть штатным образом.

S>Ну а по выразительности c Haskell сложно что-либо сравнивать.


Ага. Это ты хорошо пошутил!
Хуже кода для столь простой задачи придумать просто невозможно .

S>Монады — вообще чертовски интересная штука.


Ага. Но в парсере им не место.

S>Этакий очень абстрактный интерфейс, который, если придумать, как пристегнуть к своей задаче, дает бонус в виде стандартных библиотечных функций, ориентированных на работу с монадами. Например, из кода выше:

S>
S>-- p_sym - парсер, принимающий заданный символ
S>-- p_string - парсер, принимающий заданную строку
S>p_string = mapM p_sym -- mapM - стандартная функция, которой
S>-- достаточно только того, что p_sym - монада
S>


Как-то декларативно заданная грамматика мне больше нравится.

using Nemerle.Peg;
using System;
using System.Collections.Generic;
using System.Console;

[PegGrammar(
  start,
  grammar 
  {
    any             = ['\u0000'..'\uFFFF'];
    s     : void    = ' ';
    dot   : void    = '.';
    num   : double  = '-'? ['0'..'9']+ dot ['0'..'9']+ s;
    start : double  = num+ !any;
  }
)]
public partial class Parser
{
  _str : string;
  public this(str : string) { _str = str; }

  // Генератор парсеров не рассчитан на дурные битодробильные тесты, а рассчитан на генерацию AST.
  // По сему помещает результат циклических правил в список, что не здорово для подобных задач.
  start(nums : List[double]) : double
  {
    mutable res = 0.0;
    foreach (n in nums)
      res += n;
    res
  }

  num(minus : NToken, num1 : NToken, num2 : NToken) : double
  {
    if (minus.IsEmpty)
      ToLong(num1) + GetFrac(num2)
    else
      -1.0 * (ToLong(num1) + GetFrac(num2));
  }

  // Рукопашная реализация так как стандартная дотнетная функция на таких скоростях выглядит тормозом.
  ToLong(num : NToken) : long 
  {
    mutable res : long = 0;
    
    for (mutable i = num.StartPos; i < num.EndPos; i++)
      res = res * 10 + (_str[i] - '0' : int);
      
    res
  }

  GetFrac(num : NToken) : double
  {
    mutable res : double = 0.0;
    
    for (mutable i = num.EndPos - 1; i >= num.StartPos; i--)
      res = res * 0.1 + (_str[i] - '0' : int);
      
    res * 0.1
  }
}

module Program
{
  Main() : void
  {
    def data    = IO.File.ReadAllText(@"e:\temp\numbers_large.txt");
    def parser  = Parser(data);
    def timer   = Diagnostics.Stopwatch.StartNew();
    
    match (parser.Parse(data))
    {
      | Some(res) => WriteLine($"Result: $res  Test took: $(timer.Elapsed)");
      | None      => WriteLine("Parsing failed");
    }
  }
}
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Мой вариант на прологе
От: VladD2 Российская Империя www.nemerle.org
Дата: 09.12.10 00:29
Оценка: :)
Здравствуйте, FR, Вы писали:

FR>
FR>print sum((float(x.replace(',','.')) for x in open("numbers_large.txt").read().split(" ") if x))
FR>


FR>


Опять народ разводишь?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Мой вариант на прологе
От: VladD2 Российская Империя www.nemerle.org
Дата: 09.12.10 01:04
Оценка: -2 :))
Здравствуйте, FR, Вы писали:

FR>>>Не мне удобнее считать что шарп сливает

А>>Не вам? А кому удобнее считать?

FR>У меня запятая на клавиатуре сломалась


Значит слил!
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Haskell :: не такой тормоз, как кажется
От: Воронков Василий Россия  
Дата: 09.12.10 07:59
Оценка: +1
Здравствуйте, Schade, Вы писали:

Вообще странный тест. Как по нему можно судить о производительности кода? Попробуйте с помощью Coco/R сгенерировать на C# сканер и пропарсить с помощью него. Ну или сделать парсер вручную. Он порвет просто в хлам и Хаскель, и Спирит. Что, прикажете из этого делать вывод, что C# на пару порядков быстрее C++?
Re[2]: Haskell :: не такой тормоз, как кажется
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 09.12.10 08:27
Оценка: +1
Здравствуйте, VladD2, Вы писали:

VD>Откровенно говоря тест тупой. Назвать это битовыжимание парсингом у меня язык не поворачивается. Регулярная грамматика не показатель для парсеров. Банальная функция преобразования строки в число в дотнете отжирает времени больше чем сам парсинг.


+1

VD>Ради спортивного интереса накатал парсер на основе Nemerle-ового макроса PegGrammar. Код приведен в конце сообщения.


Отличия — нет знака +, вместо точки как разделитель может использоваться запятая, нет парсинга экспоненты (1.2E3), как целой (.23), так и дробной (1.) части может не быть.

VD>Ага. Это ты хорошо пошутил!

VD>Хуже кода для столь простой задачи придумать просто невозможно .

Там в основном реализация парсера, поэтому так. Сама реализация вот например:
{- number - разбор числового значения -}
number = do
  spaces
  s <- sign
  i <- p_try intPart
  f <- p_try fracPart
  exp <- liftM (fromMaybe 1.0) $ p_try expn
  case (i, f) of
    (Nothing, Nothing) -> mzero
    _ -> return $! exp * s * (fmay i + fmay f)
         where fmay = fromMaybe 0.0

Хотя, можно было и покрасивее, конечно.

S>>Монады — вообще чертовски интересная штука.

VD>Ага. Но в парсере им не место.

Почему?

P.S. А вообще чего эту древнючую тему подняли?
Re[2]: Haskell :: не такой тормоз, как кажется
От: Klapaucius  
Дата: 09.12.10 12:24
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Изучать эту кучу кода очень не хочется. А можно для интересующихся привести грамматику в виде BNF или чем-то похожем (регексы, PEG...)?


Что-то вроде такого:
whitespaces <- whitespace+
sign <- ('-' / '+')?
int <- [0-9]+
dot <- '.' / ','
frac <- dot int
exp <- ('e' / 'E') sign int
num <- int / (int frac) / frac
float <- sign num exp? whitespaces
floats <- float*
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[2]: Haskell :: не такой тормоз, как кажется
От: Klapaucius  
Дата: 09.12.10 12:46
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Откровенно говоря тест тупой.


Это можно воспринимать не столько как тест парсера, сколько как тест качества оптимизации кода с большим кол-вом функций высшего порядка.

VD>Причем не самопалами с объемом кода на 5 экранов, а самым что ни наесть штатным образом.


Там сама библиотека для постоения парсеров приведена.
Парсер чисел вот:
{- digit - парсер, принимающий символы от '0' до '9'
   и возвращающий уже их числовое значение -}
digit = fmap digitToInt $ p_pred isDigit

spaces = many $ p_pred isSpace
dot = p_sym2 ',' '.'

{- sign - парсер, опционально принимающий знаки '+' и '-',
   возвращающий Double-множитель, -1.0 для '-',
   1.0 в противном случае -}
sign = fmap getSign $ p_try (p_sym2 '-' '+')
       where getSign (Just '-') = -1.0
             getSign _ = 1.0

data IntAcc = IntAcc { getInt ::  {-# UNPACK #-} !Double }
instance Accumulator IntAcc Int where
    a_empty = IntAcc 0.0
    a_append i (IntAcc a) = IntAcc $ a * 10.0 + fromIntegral i

{- intPart - разбор целой части -}
intPart = many1 (writing digit)  |>| getInt

data FrAcc = FrAcc { mult :: {-# UNPACK #-} !Double,
                     getFrac :: {-# UNPACK #-} !Double }

instance Accumulator FrAcc Int where
    a_empty = FrAcc 0.1 0.0
    a_append i (FrAcc m a) = FrAcc (m * 0.1) (a + m * fromIntegral i)

{- fracPart - разбор дробной части -}
fracPart = dot >> many1 (writing digit) |>| getFrac

{- expn - разбор экспоненты  -}
expn = do
  p_sym2 'e' 'E'
  s <- sign
  i <- intPart
  return $ 10 ** (s * i)

{- number - разбор числового значения -}
number = do
  spaces
  s <- sign
  i <- p_try intPart
  f <- p_try fracPart
  exp <- liftM (fromMaybe 1.0) $ p_try expn
  case (i, f) of
    (Nothing, Nothing) -> mzero
    _ -> return $! exp * s * (fmay i + fmay f)
         where fmay = fromMaybe 0.0


data Sum a = Sum {getSum :: {-# UNPACK #-} !a}

instance Num a => Accumulator (Sum a) a where
    a_empty = Sum $ fromIntegral 0
    a_append e (Sum a) = Sum $ e + a

sumNumbers = many (writing number) |>| getSum


VD>Как-то декларативно заданная грамматика мне больше нравится.


А там грамматика и так декларативно задана. Другое дело, что все это можно красивее записать, на аппликативных функторах и с постфиксными операторами. Ну и работать это сейчас должно быстрее — все-таки GHC 6.8.2 это теперь седая старина.
... << RSDN@Home 1.2.0 alpha 4 rev. 1476>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Re[3]: Haskell :: не такой тормоз, как кажется
От: dr.Chaos Россия Украшения HandMade
Дата: 10.12.10 05:27
Оценка: +1 :))) :)
Здравствуйте, lomeo, Вы писали:

L>P.S. А вообще чего эту древнючую тему подняли?


Видимо PegGrammar дописали/тестируют .
Побеждающий других — силен,
Побеждающий себя — Могущественен.
Лао Цзы
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.