2

スペースで区切られた整数のリストを標準出力に出力したいと考えています。リストの生成が速いので、この問題を [1..200000] のシーケンスで解決しようとしました。

C では、次のように実装できます。

#include "stdio.h"
int main()
{
  int i;
  for(i = 0; i <= 200000; ++i)
    printf("%d ", i);
  return 0;
}

私が実装できる Haskell で最速のソリューションは、約 3 倍遅くなります。

import Data.List (intercalate)
main = putStr . intercalate " " . map (show) $ [1..(200000)]

いくつかの方法で ByteStrings を試しましたが、さらに遅くなりました。大きな問題は、show を使用した整数の文字列への変換 (または ByteStrings への変換) のようです。

Cに接続せずにこれを高速化する方法について何か提案はありますか? 複雑になりすぎないようにしてください (可能な限り短く美しく、他の Haskell モジュールを使用してもかまいません)。

4

5 に答える 5

4

さて、コードを少し書き直すことができます：

import Data.List (intercalate)
main = output
output = putStr one_string
one_string = intercalate " " strings
strings = map show $ [1..2000000]

次に、「ghc -O2 -prof -auto-all .hs」を使用してプロファイリングできます。

COST CENTRE                    MODULE               %time %alloc

one_string                     Main                  42.2   55.9
strings                        Main                  39.2   43.1
output                         Main                  18.6    1.0

インターカレートが実行時間のかなりの半分を占めていることがわかります。ただし、低レベルのトリックに頼らなければ、全体を高速化することはできないと思います。より高速なインターカレートに切り替える場合 (たとえば、Data.ByteString.Lazy.Char8 から)、低速の Int -> String 変換を使用する必要があります。

于 2010-11-26T15:09:53.573 に答える
2

ghc-6.12.1の代わりにghc-6.10.4を使用すると、このプログラムの実行速度が大幅に向上します。IIRC 6.12行では、Unicode対応のIOが導入されました。これは、速度低下の多くを説明していると思います。

私のシステム：

C  (gcc -O2):        0.141s
HS (ghc-6.10.4 -O2): 0.191s (ave.)
HS (ghc-6.12.1 -O2): 0.303 (ave.)

ghc-6.10を使用すると、結果はCにかなり匹敵します。Haskellが文字列を使用しているため（そしておそらく実行時のオーバーヘッドも）、違いがあると思います。

そのコンパイラからより良いパフォーマンスを得たい場合は、ghc-6.12のI/OでのUnicode変換をバイパスすることが可能だと思います。

于 2010-11-26T17:23:22.813 に答える
1

最初の質問:

コードを投稿してください!!!

(delnan によると :)、次のことが発生するため遅いと思います (バイト文字列を使用しない場合は、手順 4 をスキップしてください)。

  1. すべての数値は 1 つずつ変換されます。出力はリストです。
  2. 要素 (スペース!) を追加するため、出力のリストを再度トラバースする必要があります。
  3. リストを連結するため、リストを再度トラバースする必要があります
  4. リストはバイト文字列に変換されるため、再度packトラバースする必要があります ( )
  5. 全体がプリントアウトされます。

バイト文字列を使用すると高速になる可能性がありますが、おそらくshowバイト文字列で動作する独自の を実装する必要があります。次に、非常に賢く、複数のトラバーションを避け、リストが作成されたら空白を入力します。

多分このように：

import qualified Data.Bytestring.Lazy.Char8 as B

showB :: Int -> Bytestring -- Left as an exercise to the reader

main = B.putStr $ pipeline [0..20000] where
  pipeline = B.tail . B.concat . map (B.cons' ' ') . map showB

これはテストされていないので、プロファイル!!! ご覧のとおり、to マップは融合できるため、リストはおそらく 2 回走査されます。

于 2010-11-26T14:25:37.697 に答える
0

このバージョンは、あなたのバージョンよりも少し優れています。私はそれを改善する一つの方法だと思います。

showWithSpaces        :: (Show a) => [a] -> ShowS
showWithSpaces []     = showString ""
showWithSpaces (x:xs) = shows x . showChar ' ' . showWithSpaces xs

main = putStrLn $ showWithSpaces [1..2000000] $ ""
于 2010-11-27T22:59:35.923 に答える
0

これは、文字列サフィックスの共有を悪用しようとする、同じ問題に対する別のアプローチです。私のマシンでは、元の Haskell よりも約 1/3 速くなりましたが、確かに C バージョンからはまだ離れています。1 から 999999 以外の数を実行することは、演習として残されています。

basic :: [Char]
basic = ['0'..'9']

strip :: String -> String
strip = (' ' :) . dropWhile (== '0')

numbers :: Int -> [String]
numbers 0 = [""]
numbers n = [x : xs | x <- basic, xs <- rest]
  where
    rest = numbers (n - 1)

main = mapM_ (putStr . strip) (tail $ numbers 6)
于 2010-11-26T16:33:10.977 に答える