Здравствуйте, 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

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

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

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

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

Здравствуйте, D. Mon, Вы писали:

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

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

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

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

Здравствуйте, D. Mon, Вы писали:

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

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

Здравствуйте, 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);;

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

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

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

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

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

Здравствуйте, 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 с гаком млн. элементов — не самая быстрая структура данных

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

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

.....

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

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

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

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

Да на компьютере с русской локалью (с запятой вместо точки) не работает выше на питоне и шарпе это учитывалось, и была замена в строках запятой на точку.

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

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

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

FR>.....

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

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

В GHC надо использовать ByteString вместо строк. Будет на порядок быстрее.

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

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

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

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

Здравствуйте, D. Mon, Вы писали:

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

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

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

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

Здравствуйте, D. Mon, Вы писали:


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

Да еще camlp4 предоставляет расширение — destructive matching то есть PM для потоков плюс конструкторы потоков [< >], с этим можно любые откаты сделать.

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

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

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


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

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

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

Здравствуйте, 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
#

Здравствуйте, D. Mon, Вы писали:

Тут http://www.ffconsultancy.com/ocaml/benefits/parsing.html примерчик как раз по теме.

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

S>module Main (main) where...
S>

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

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

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

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

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

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

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

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

Код не скомпилируется — это более-менее стандартные расширения языка из GHC.