8

Haskellのacm.timus.ruから問題1330を解決しようとしています。基本的に、これは次のように要約されます。1）stdinから長さN（N <10 ^ 4）の配列Aと整数のMペア（M <10 ^ 5）を読み取ります。2）各（from、to）ペアについて、サブ配列A[from..to]の合計をstdoutに出力します。

SOでは、この質問の一部として2つを超えるURLを投稿することはできないため、以下のGithubリポジトリ内のファイルを参照します。

私は、ほとんどのコードを共有する2つのソリューションを考え出しました。最初のもの（1330_slow.hs）はプレリュード関数（getLine / read / words）を使用しており、やや遅いです：

$ ./bench.sh slow_hs
slow_hs
    Time inside the program: 2.18
MD5 (output.slow_hs.txt) = 89bcf8fd69a7fce953595d329c8f033a

もう1つのソリューション（1330.hs）は、これらの関数を破棄し、同等のData.ByteString.Char8（B.getLine / B.readInt / B.words）に置き換えて、適切に実行します。

$ ./bench.sh hs
hs
    Time inside the program: 0.27
MD5 (output.hs.txt) = 89bcf8fd69a7fce953595d329c8f033a

この問題の制限時間は500ミリ秒なので、270ミリ秒は十分に高速ですが（C ++やGoなどの他の言語の私のソリューションに匹敵します）、2180ミリ秒では問題は解決しません。では、なぜ私の最初の解決策はとてつもなく遅いのですか？Real World Haskellのプロファイリングのヒントに従ったとしても、これを理解することはできません（私が理解できたのは、時間の大部分がreadIntPair関数に費やされたということだけでしたが、あまり役に立ちませんでした）。

独自のテストを行いたい場合は、Python入力ジェネレーター（gen_test.py）と、Pythonがインストールされていない場合に備えて事前に生成された入力ファイル（input.txt）があります。そして、2つのソリューション間の差分（slow_fast_diff.txt）。

4

2 に答える 2

8

ByteStringとStringの対比（つまり、Stringが遅いのはなぜですか？）

BytestringIOには、Cで慣れているように、パックされたバッファへのデータの読み取りが含まれます。 String一方、IOを複雑にするだけでなく、処理のための文字のリンクリストであるため、メモリ、処理、キャッシュの使用量が増える可能性があります。おそらく分岐、そしてGC。

ByteStringが高速なのはなぜですか？

別の言い方をすれByteStringば、同じ理由unsigned char * で高速ですC。

于 2013-01-27T04:54:55.490 に答える
8

他の人が言っているように、それByteStringは速いというわけではありません、それStringは非常に、非常に遅いです。

AByteStringは、文字ごとに1バイトと、簿記のオーバーヘッドを格納します。AStringは、1文字あたり12バイトのようなものを格納します（32ビットモードと64ビットモードのどちらで実行しているかによって異なります）。また、各文字を非連続メモリに格納するため、各文字に個別にスペースを割り当て、ガベージコレクタによって個別にスキャンし、最終的には再度個別に割り当てを解除する必要があります。これは、キャッシュの局所性が低く、アロケータの時間が長く、ガベージコレクションの時間が長いことを意味します。要するに、それは地獄のように非効率的です。

基本的に、ByteStringCが行うこと、Javaが行うこと、C ++が行うこと、C＃が行うこと、VBが行うこと、および他のほぼすべてのプログラミング言語が文字列を使用して行うことを行います。私が知っている他の言語には、Haskellほど非効率的なデフォルトの文字列型がありません。（Haskell方言であるフレーゲでさえ、より効率的な文字列型を使用しています。）

ByteString.Char8ラテン1文字のみを処理することを指摘しておく必要があります。ランダムなUnicode文字にはまったく対応していません。これは、このようなプログラミングの課題ではおそらく問題ではありませんが、「実際のシステム」では問題になる可能性があります。ByteStringエキゾチックな文字や異なる文字エンコードなどは実際には扱いません。プレーンASCIIが必要であると想定しているだけです。これは以前は安全な仮定でした。今日はそんなにありません。

于 2013-01-27T09:49:02.960 に答える