3

ここでは、密なビット ベクトルを表すために任意精度の整数を使用しています。サイズは数十から数千までの範囲です。

私のコードでは、特定のビットが設定されている (または設定されていない) かどうかを頻繁に確認する必要があるため、いくつかのバリエーションが他のバリエーションよりも大幅に高速かどうかを確認するために、いくつかのマイクロ ベンチマークを実行しました。

ベンチ_1(0, _, _) :- !.
ベンチ_1(N, V, P) :- V /\ (1 << P) =\= 0, N0 は N-1, ベンチ_1(N0, V, P).

ベンチ_2(0, _, _) :- !.
ベンチ_2(N、V、P) :- (V >> P) /\ 1 =:= 1、N0 は N-1、ベンチ_2(N0、V、P)。

ベンチ_3(0, _, _) :- !.
ベンチ_3(N, V, P) :- (V >> P) /\ 1 =\= 0, N0 は N-1, ベンチ_3(N0, V, P).

ベンチ_4(0, _, _) :- !.
ベンチ_4(N, V, P) :- (V >> P) /\ 1 > 0, N0 は N-1, ベンチ_4(N0, V, P).

ベンチ_5(0, _, _) :- !.
bench_5(N, V, P) :- 1 は (V >> P) /\ 1、N0 は N-1、bench_5(N0, V, P) です。

SWI と SICStus の両方で、上記のバリアントはすべて (ほぼ) 同等に高速です。

次に、SWI-Prolog マニュアルの次の興味深い部分に出くわしました。

getbit(+IntExprV, +IntExprI)

の- 番目のビットのビット値 (0または1) に評価されます。両方の引数は、負でない整数に評価される必要があります。結果は と同等ですが、シフトされた値の具体化が回避されるため、より効率的です。IntExprIIntExprV(IntExprV >> IntExprI)/\1

将来のバージョンでは(IntExprV >> IntExprI)/\1、 への呼び出しに最適化され、getbit/2移植性とパフォーマンスの両方が提供されます。

だから私はチェックアウトしましたgetbit/2：

ベンチ_6(0, _, _) :- !.
ベンチ_6(N、V、P) :- getbit(V、P) =:= 1、N0 は N-1、ベンチ_6(N0、V、P)。

マイクロベンチマークには次のコードを使用しました。

call_indi_delta(G, What, Delta) :-
   statistics(What, [V0|_]),
   call(G),
   statistics(What, [V1|_]),
   Delta is V1 - V0.

run(Ind, Reps, Expr, Pos) :-
   Position is Pos,
   Value    is Expr,
   member(P_3, [bench_1,bench_2,bench_3,bench_4,bench_5,bench_6]),
   G =.. [P_3,Reps,Value,Position],
   call_indi_delta(G, Ind, T_ms), 
   write(P_3:Reps=T_ms), nl,
   false.

私はこれらのランタイムをrun(runtime, 10000000, 1<<1000-1, 200)観察しました：

        | | スイス | SWI | SWI -O | SICStus | SICStus |
        | | 7.3.23 | 7.3.23 | 4.3.2 | 4.3.3 |
------+-----------------+-------------------|
ベンチ_1 | 4547ミリ秒| 3704ms | 900ms |   780ms |
ベンチ_2 | 4562ms | 3619ms | 970ms | 850ms |
ベンチ_3 | 4541ms | 3603ms | 970ms | 870ms |
ベンチ_4 | 4541ms | 3633ms | 940ms | 890ms |
ベンチ_5 | 4502ms | 3632ms | 950ms | 840ms |
------+-----------------+-------------------|
ベンチ_6 | 1424ms |  797ms | な |    な|

次のように表示されます。

SICStus で同様の高速化を実現するためのより良い定式化 (算術演算など) はありますか?

前もって感謝します！

4

1 に答える 1

4

いいえ、あなたが試したものよりも速い製剤があるとは思いません. 特に、getbit/2SICStus のようなものはありません (演算をコンパイルするときに内部的に使用されることさえありません)。

PS。walltime一般に、ベンチマークには を使用します。現在の OS は、信頼性の高いruntime.

PPS。テスト済みのコード シーケンスのダミー バージョンを使用するベンチマークを追加して、テスト済みのコードが実際にベンチマーク ハーネスよりもはるかにコストがかかることを確認します。（私はそうしましたが、ビットテストをdummy/3何もしない a への呼び出しに置き換えると、はるかに高速になります。したがって、ベンチマークは問題ないようです。）

于 2016-07-07T09:03:26.070 に答える