0

私のコードが遅い場所を最初に検索したとき、これは予想外でしたが、累乗 (または乗算) がより高速になる可能性があるため、シフト コードの何かが本当に遅いことに本当に驚きました。

(整数) べき乗のコード

{-# OPTIONS_GHC -O2 #-}

import System.Environment(getArgs)

main = do
  [a,b] <- getArgs
  let c = ( read a::Integer ) ^ ( read b::Int )
  print ( mod c 2 )

シフトのサンプルコード

{-# OPTIONS_GHC -O2 #-}

import Data.Bits
import System.Environment(getArgs)

main = do
  [a,b] <- getArgs
  let c = shift ( read a::Integer ) ( read b::Int )
  print( mod c 2 )

私の実行は、古いものと最新の haskell で実行されます。

c:\ghc\ghc-6.10.4\bin>cmd /v:on /c "echo !TIME! & pow.exe 33 40000000 & echo !TIME!"
1:24:29,02
1
1:24:41,48
-- 12.46 秒 電源用

c:\ghc\ghc-6.10.4\bin>cmd /v:on /c "echo !TIME! & shift.exe 3 200000000 & echo !TIME!"
1:27:08,76
0
1:27:22,06
-- 13.30 秒 シフト用

c:\ghc\ghc-7.6.3\bin>cmd /v:on /c "echo !TIME! & pow.exe 33 40000000 & echo !TIME!"
2:19:29,39
1
2:19:37,06
-- 7.67 秒 動力用（動力が少し改善されます）

c:\ghc\ghc-7.6.3\bin>cmd /v:on /c "echo !TIME! & shift.exe 3 200000000 & echo !TIME!"
2:20:49,61
0
2:20:49,69
-- 0.08 秒 シフト用 (つまり、約 150 倍の速度アップを意味します)

または（ここでは20億ビットシフト）：
c:\ghc\ghc-7.6.3\bin>cmd /v:on /c "echo !TIME! & shift.exe 3 2000000000 & echo !TIME!"
3:07:22,05
0
3:07:22,56
-- 0.51 秒

実行中の数値は、長い実行時間を確認するために非常に大きくなります。最初のコードでは 33^40000000 (mod 2) を計算し、2 番目のコードでは 3*2^200000000 (mod 2) を計算します。mod 操作 (または他の何か) は、not 0 の時間を確認する必要があります (その場合、haskell はそれを計算しないため)。そして、前述のように、電力供給はより高速であり、その場合、33^40000000 は 3*2^200000000 よりも大きいことに注意してください。さらに、メモリ使用量については、最新の haskell でも 3^200000000 が計算されていることがわかります。したがって、ここには深い最適化のトリックはありません。

この古いバージョンの Haskell でスピードアップすることは可能でしょうか? 私は両方向に (大きな整数を) シフトすることに興味があり、64 ビット (または 63 または 32 または 31; haskell の整数表現の単語のサイズ) の倍数でシフトすると仮定できるので、ラップアラウンドではありません。

2^n を計算してから乗算 (または除算) を実行してシフトを実行しようとしましたが、古い Haskell では高速化されませんでした。

-v フラグを指定してコンパイラを実行しているUPDATE
は次のように印刷を開始します: (残りのものも投稿できます) Glasgow Haskell Compiler, Version 6.10.4, for Haskell 98, stage 2 booted by GHC version 6.10.1 パッケージ構成ファイルを使用: C :\ghc\ghc-6.10.4\package.conf パッケージ base-3.0.3.1 を非表示にして、後のバージョン base-4.1.0.0 との競合を回避します。パッケージ integer は integer-0.1.0.1 にマッピングされます。 wire-in パッケージ base は base-4.1.0.0 にマッピングされます。 wire-in パッケージ rts は rts-1.0 にマッピングされます。 wire-in パッケージ haskell98 は haskell98-1.0.1.0 にマッピングされます。 syb-0.1.0.1 ワイヤードイン パッケージ template-haskell は template-haskell-2.3.0.1 にマッピングされます ワイヤードイン パッケージ dph-seq は dph-seq-0.3 にマッピングされます ワイヤードイン パッケージ dph-par は dph-par-0.3 Hsc にマッピングされます静的フラグ: -static

4

1 に答える 1