Haskell :: не такой тормоз, как кажется - Декларативное программирование

По-моему очень даже красиво и понятно. На ноуте работает 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).

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

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

FR>

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

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

FR>>

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

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

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

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

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

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

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

Насколько я понимаю, не приведены только комбинаторы Or и And ввиду их встроенности в Пролог.

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

А>Насколько я понимаю, не приведены только комбинаторы Or и And ввиду их встроенности в Пролог.

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

Or/And оставим за границей.

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

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

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

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

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

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

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

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?)

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

А>Здравствуйте, 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), т.ч можно просто считать это частью языка.

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 — , | [] {}.

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

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

А>>Важен-то прикладной код описания парсера, а не комбинаторы, представляющие операторы EBNF — , | [] {}.
X>Ну в принципе, да, эти вещи встроенные. Если уважаемому thesz интересна реализация этих штук, могу только сказать, что программа с DCG на этапе загрузки использую механизм term expansion преобразуется в обычный прологовский код с предикатами, который далее исполняется.

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

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

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

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

Поэтому я и поднял вопрос о том, что желательно бы на них посмотреть.

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

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

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

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

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

Здравствуйте, 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>Здесь проверяется то, как из простого описания на комбинаторах мы можем раскрутить сложные описания прикладных задач. Во что нам это встанет.
Никакого множества сложных прикладных задач тут нет, речь идет о преобразовании строки в число с плавающей точкой.
Настолько трививальная задача, что она уже содержится в библиотечных функциях в большинстве языков.

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/ ?

Нет.

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>>Здесь проверяется то, как из простого описания на комбинаторах мы можем раскрутить сложные описания прикладных задач. Во что нам это встанет.
А>Никакого множества сложных прикладных задач тут нет, речь идет о преобразовании строки в число с плавающей точкой.

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

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

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

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

и не городить весь этот огород

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

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

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()

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

	От:	xonixx
	Дата:	23.05.09 21:40
	Оценка:	51 (2)

	От:	FR
	Дата:	26.05.09 08:26
	Оценка:	+1

	От:	Schade
	Дата:	26.05.09 10:32
	Оценка:	+2

От:	thesz	http://thesz.livejournal.com
Дата:	26.05.09 14:53
Оценка:

	От:	Аноним
	Дата:	28.05.09 09:30
	Оценка:

От:	D. Mon	http://thedeemon.livejournal.com
Дата:	30.05.09 04:30
Оценка: