次の関数を使用して、整数の底 2 の対数を計算します。
public static int log2(int n){
if(n <= 0) throw new IllegalArgumentException();
return 31 - Integer.numberOfLeadingZeros(n);
}
最適なパフォーマンスが得られますか?
誰かがその目的のために準備ができているJ2SE API関数を知っていますか?
UPD1 驚いたことに、浮動小数点演算は整数演算よりも高速に見えます。
UPD2 コメントがあったため、より詳細な調査を行います。
UPD3 私の整数算術関数は、Math.log(n)/Math.log(2) よりも 10 倍高速です。
これは、この計算に使用する関数です。
public static int binlog( int bits ) // returns 0 for bits=0
{
int log = 0;
if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
if( bits >= 256 ) { bits >>>= 8; log += 8; }
if( bits >= 16 ) { bits >>>= 4; log += 4; }
if( bits >= 4 ) { bits >>>= 2; log += 2; }
return log + ( bits >>> 1 );
}
これは、Integer.numberOfLeadingZeros（）（20-30％）よりもわずかに高速であり、次のようなMath.log（）ベースの実装よりもほぼ10倍高速（jdk 1.6 x64）です。
private static final double log2div = 1.000000000001 / Math.log( 2 );
public static int log2fp0( int bits )
{
if( bits == 0 )
return 0; // or throw exception
return (int) ( Math.log( bits & 0xffffffffL ) * log2div );
}
両方の関数は、すべての可能な入力値に対して同じ結果を返します。
更新：
Java 1.7サーバーJITは、いくつかの静的数学関数をCPU組み込み関数に基づく代替実装に置き換えることができます。それらの関数の1つは、Integer.numberOfLeadingZeros（）です。したがって、1.7以降のサーバーVMでは、問題のような実装は実際にはbinlog上記よりもわずかに高速です。残念ながら、クライアントJITにはこの最適化がないようです。
public static int log2nlz( int bits )
{
if( bits == 0 )
return 0; // or throw exception
return 31 - Integer.numberOfLeadingZeros( bits );
}
この実装は、上記で投稿した他の2つの実装と同じ、2^32の可能な入力値すべてに対して同じ結果を返します。
これが私のPC（Sandy Bridge i7）の実際のランタイムです：
JDK 1.7 32ビットクライアントVM：
binlog: 11.5s
log2nlz: 16.5s
log2fp: 118.1s
log(x)/log(2): 165.0s
JDK 1.7 x64サーバーVM：
binlog: 5.8s
log2nlz: 5.1s
log2fp: 89.5s
log(x)/log(2): 108.1s
これはテストコードです：
int sum = 0, x = 0;
long time = System.nanoTime();
do sum += log2nlz( x ); while( ++x != 0 );
time = System.nanoTime() - time;
System.out.println( "time=" + time / 1000000L / 1000.0 + "s -> " + sum );
整数演算に浮動小数点を使用することを考えている場合は、注意が必要です。
私は通常、可能な限り FP 計算を避けるようにしています。
浮動小数点演算は正確ではありません。何が(int)(Math.log(65536)/Math.log(2))評価されるかを確実に知ることはできません。たとえば、Math.ceil(Math.log(1<<29) / Math.log(2))私の PC では 30 ですが、数学的には正確に 29 になるはずです。(int)(Math.log(x)/Math.log(2))失敗する x の値は見つかりませんでした (「危険な」値が 32 個しかないため)。どのPCでも同じです。
ここでの通常のトリックは、丸めの際に「イプシロン」を使用することです。Like(int)(Math.log(x)/Math.log(2)+1e-10)は決して失敗してはなりません。この「イプシロン」の選択は簡単な作業ではありません。
より一般的なタスクを使用したより多くのデモンストレーション - 実装しようとしていますint log(int x, int base):
テストコード:
static int pow(int base, int power) {
int result = 1;
for (int i = 0; i < power; i++)
result *= base;
return result;
}
private static void test(int base, int pow) {
int x = pow(base, pow);
if (pow != log(x, base))
System.out.println(String.format("error at %d^%d", base, pow));
if(pow!=0 && (pow-1) != log(x-1, base))
System.out.println(String.format("error at %d^%d-1", base, pow));
}
public static void main(String[] args) {
for (int base = 2; base < 500; base++) {
int maxPow = (int) (Math.log(Integer.MAX_VALUE) / Math.log(base));
for (int pow = 0; pow <= maxPow; pow++) {
test(base, pow);
}
}
}
対数の最も単純な実装を使用すると、
static int log(int x, int base)
{
return (int) (Math.log(x) / Math.log(base));
}
これは次のように表示されます：
error at 3^5
error at 3^10
error at 3^13
error at 3^15
error at 3^17
error at 9^5
error at 10^3
error at 10^6
error at 10^9
error at 11^7
error at 12^7
...
エラーを完全に取り除くには、1e-11 と 1e-14 の間のイプシロンを追加する必要がありました。テストの前にこれを言うことができましたか？私は絶対にできませんでした。
試すMath.log(x) / Math.log(2)
あなたはアイデンティティを使用することができます
log[a]x
log[b]x = ---------
log[a]b
したがって、これは log2 に適用されます。
log[10]x
log[2]x = ----------
log[10]2
これをJava Math log10メソッドに差し込むだけです....
なぜだめですか：
public static double log2(int n)
{
return (Math.log(n) / Math.log(2));
}
追加しましょう:
int[] fastLogs;
private void populateFastLogs(int length) {
fastLogs = new int[length + 1];
int counter = 0;
int log = 0;
int num = 1;
fastLogs[0] = 0;
for (int i = 1; i < fastLogs.length; i++) {
counter++;
fastLogs[i] = log;
if (counter == num) {
log++;
num *= 2;
counter = 0;
}
}
}
ソース: https://github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java