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...
Пока на собственное сообщение не было ответов, его можно удалить.