24

私は SPOJ の PRIME1 の問題に対してかなり貧弱な試みを行ってきました。ByteString を使用すると、問題のテキストを読み取る際のパフォーマンスが大幅に向上することがわかりました。ただし、ByteString を使用して結果を書き出すと、実際には Prelude 関数を使用するよりもわずかに遅くなります。私はそれが間違っているのか、それともこれが期待されているのかを理解しようとしています.

(putStrLn.show) と同等の ByteString を 3 つの異なる方法で使用して、プロファイリングとタイミングを実行しました。

  1. 各候補をテストして、それが素数かどうかを確認します。もしそうなら、それをリストに追加して (putStrLn . show) で書き出します。
  2. すべての素数のリストを作成し、(putStrLn . unlines. show) を使用してリストを書き出します。
  3. すべての素数のリストを作成し、map (putStrLn . show) を使用してリストを書き出します。

ある関数でリストを作成し、別の関数でそれを使用しているため、番号 2 と 3 のパフォーマンスが遅くなると予想しました。数値を生成しながら出力することで、リストにメモリを割り当てないようにしています。一方、putStrLn を呼び出すたびにシステム コールを呼び出しています。右？それでテストしたところ、実際には＃1が最速でした。

オプション #1 と Prelude ([Char]) 関数を使用すると、最高のパフォーマンスが得られました。ByteString を使用したオプション #1 が最高のパフォーマンスになると予想していましたが、そうではありませんでした。私は怠惰な ByteString のみを使用しましたが、これが問題になるとは思いませんでした。そうでしょうか？

いくつかの質問：

  • 大量の整数を stdout に書き込むために、ByteStrings のパフォーマンスが向上すると思いますか?
  • パフォーマンスの向上につながる回答を生成して書き出す方法のパターンがありませんか?
  • 数値をテキストとして書き出すだけの場合、ByteString を使用する利点はいつありますか?

私の作業仮説は、Integer を ByteString で書き出すのは、それらを他のテキストと組み合わせていない場合は遅くなるというものです。Integers と [Char] を組み合わせると、ByteString を使用した方がパフォーマンスが向上します。つまり、次の ByteString の書き換え:

putStrLn $ "the answer is: " ++ (show value)

上記のバージョンよりもはるかに高速になります。これは本当ですか？

読んでくれてありがとう！

4

2 に答える 2

21

データが密集しているため、ディスクからメモリにシャッフルするデータが少なくなるため、通常、バイト文字列を使用すると一括入力が高速になります。

ただし、データを出力として書き込む場合は少し異なります。通常、構造体をシリアル化し、多くの小さな書き込みを生成します。したがって、その場合、バイト文字列の高密度の一括書き込みはあまり役に立ちません。レギュラーStringsでもインクリメンタル出力で十分です。

しかし、すべてが失われるわけではありません。メモリ内にバイト文字列を効率的に構築することで、高速な一括書き込みを回復できます。このアプローチは、さまざまな*-builderパッケージで採用されています。

値を多数の小さなバイト文字列に変換して一度に 1 つずつ書き出す代わりに、変換を成長し続けるバッファーにストリーミングし、そのバッファーを 1 つの大きな断片に書き込みます。これにより、IO オーバーヘッドが大幅に削減され、文字列 IO よりもパフォーマンスが (多くの場合大幅に) 向上します。

この種のアプローチは、Haskell の Web サーバーや効率的な HTML システムblazeなどで採用されています。

また、一括書き込みを行った場合でも、パフォーマンスは型とバイト文字列間の変換関数の効率に依存します。の場合Integer、単にメモリ内のビット パターンを出力にコピーするか、代わりに非効率的なデコーダを経由する可能性があります。その結果、Char/String IO を使用するか bytestring IO を使用するかだけでなく、使用しているエンコーディング関数の品質について少し考える必要がある場合があります。

于 2011-05-12T00:04:52.723 に答える
7

ByteStringとの主な違いはパフォーマンスではないことに注意してくださいString。前者はバイナリ データ用で、後者は Unicode テキスト用です。バイナリ データの場合は を使用ByteStringし、Unicode テキストの場合はtext パッケージTextのタイプを使用します。

于 2011-05-12T08:15:23.013 に答える