Здравствуйте, 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");
}
}
}
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Вообще странный тест. Как по нему можно судить о производительности кода? Попробуйте с помощью Coco/R сгенерировать на C# сканер и пропарсить с помощью него. Ну или сделать парсер вручную. Он порвет просто в хлам и Хаскель, и Спирит. Что, прикажете из этого делать вывод, что C# на пару порядков быстрее C++?
Здравствуйте, 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>Ага. Но в парсере им не место.
Здравствуйте, 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
Здравствуйте, 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