🌨️ 🥋 🕵️ プロローグ解析の詳細 🦓 👼 ↪️

ここで、一般的に、500万個のフロートを含むテキストファイルの解析（およびその合計の計算）から成る簡単なタスクに出会いました。ファイルは、次の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のパフォーマンスに関する議論のコンテキストで提示されました。プロローグでは、そのようなタスクがDCGテクニック（定節文法： 1、2、3、4 ）を使用して美しく簡単に解決されることを知っていました。実際、これはプロローグ言語での文法の記述であり、プロローグの網羅的な検索原理に基づいて、それらに基づいた構文解析です。

まあ、つまり、通常は非常に簡潔かつ美しくなります（たとえば、この方法でブラケットのバランスをとる問題の解決策は次のとおりです： 7行のプログラム）、しかし、私はそれが常に高速であるとは思わなかった。実際に、私はそれをチェックアウトしたかった。

かなり迅速（約15分）に、プログラムの明白な（単純な）バージョンが作成されました。

:- set_prolog_flag (float_format, '%.15g' ). 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 ) --> float ( F1 ), ! , " " , ( sum ( S1 ) ; { S1 = 0} ), { S is F1 + S1 }. go :- read_file_to_codes ( 'numbers_large.txt' , Codes ,[]), writeln ( 'Processing...' ), sum ( S , Codes ,[]), writeln ( S ).

もちろん、私はそのような大きなファイルの解析の内訳を疑っていましたが、ジョークは以前に起こりました。 read_file_to_codes述語は、Out of globalスタックに分類されました。これは、一般に、かなり明白でした。実際のところ、SWIプロローグの私の実装では、32ビットアーキテクチャに基本的な制限があります-グローバルスタックごとに128 mb以上、ローカルスタックごとに128 mb以上を使用することはできません（64ビット軸で制限が削除されました）。後でドックで読んで、その前に-G500M-L500Mキーで再生しようとしましたが、これはもちろん保存しませんでした。メモリ内で〜82M文字を読み取るには、かなり多くのスペースが必要でした（128より）。

メーリングリストのメンバーが助けてくれました（ところで、SWI Prologの作者であるJan Wielemakerがメーリングリストに積極的に参加していることを強調したいと思います。今回も！）。

ライブラリ（pio）のphrase_from_file述語を使用することを提案しました。これはレイジースタイルのストリームで動作し、実際にはファイルからの読み取りと1つの述語の解析を組み合わせます。必要なものだけ！

さらに、彼はさらに問題を予想して、述語和を書き直しました。述語和は、同時加算で構文解析を実行し、「末尾再帰」形式で書きました。初心者については、もう少し説明します。関数型および論理型のプログラミング言語では、通常ループを作成できないため、ほとんどすべてが再帰を使用して行われます。しかし、（可能であれば）正しく記述すると、コードがループにコンパイルされるという効果を得ることができますが、外側では再帰になります。末尾再帰を書くためのプロローグでは、述語は次のように書かなければなりません。

head :- <guard goals>, !, <deterministic stuff>, head. head :- ...

実際、末尾再帰の主なことは、述語の最後に独自の呼び出しがあることです。

コードは次のように書き直されました。

:- set_prolog_flag (float_format, '%.15g' ). 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 = 3D -1} ; "" , { Sign = 3D 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 ).

ただし、今回はローカルスタック（および約130 mbのメモリ消費）が再び発生します

?- go1. 
      

        
        
        
      

     ERROR: Out of local stack 
      

        
        
        
      

     Exception: (1,973,549) sum(3943621517.84343, _G2, [45, 50, 55, 54, 57, 
      

        
        
        
      

     44, 49, 48|...], []) ?

これは、テール再帰が機能しなかったことを意味するだけであり、今回は慎重に有罪であることが判明しました（実際、早すぎる最適化はすべての病気の根源です）述語和/ 2カットオフ記号（カット！）不要な代替の検索を終了するように呼び出され、最後に配置されたのは彼であり、末尾再帰の最適化も無効にしました。

一般に、この不運な（！）を削除しますが、記号を解析する代わりにフロートに追加します（リターンポイントを記憶しないようにするため）、プログラムの最終バージョンを取得しました。

:- set_prolog_flag (float_format, '%.15g' ). 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 ).

Core2Duo @ 3Ghzでは、約1分で動作し、5 MBを超えるメモリを消費せず、約1.3 Mb / sの解析速度を実現します。 Haskellのオプションほど高速ではありませんが、私見では、解釈されたSWI-Prologにとっては悪くありません。また、RSDNのルートポストのソリューションと比較して、非常にエレガントです。

ところで、Pythonは驚くほどスピードに満足していませんでした。ナイーブ、ただし、オプション

from decimal import * getcontext().prec=15 print sum(Decimal(f.replace( ',' , '.' ) or '0' ) for f in open( 'numbers_large.txt' ).read().split( ' ' )) * This source code was highlighted with Source Code Highlighter .

236メガバイトのメモリを消費し、同じ構成で約4分間働きました。

プロローグ解析の詳細

More articles: