SORU
22 Temmuz 2010, PERŞEMBE


Nasıl tamsayılar için Java 2 tabanı hesaplamak günlük musunuz?

Aşağıdaki fonksiyon tam sayılar için temel 2 günlük hesaplamak için kullanın:

public static int log2(int n){
    if(n <= 0) throw new IllegalArgumentException();
    return 31 - Integer.numberOfLeadingZeros(n);
}

En iyi performans var mı?

Biri bu amaç için hazır J2SE API işlevi biliyor mu?

UPD1Benim için şaşırtıcı bir şekilde, kayan nokta aritmetiği tamsayı aritmetiği daha hızlı görünüyor.

UPD2Yorumlar sayesinde daha detaylı araştırma yapacağım.

UPD3Tamsayı aritmetik görevim Matematik 10 kat daha hızlı.log(n)/Matematik.günlük(2).

CEVAP
22 Temmuz 2010, PERŞEMBE


Bu hesaplama için kullandığım fonksiyon

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 );
}

Tamsayı göre biraz daha hızlı.() numberOfLeadingZeros (20-30%) ve 10 kat daha hızlı (fırsatlar 1.6 x 64) bir Matematik daha neredeyse.() günlük uygulama bu gibi:

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 );
}

Her iki işlevi bütün olası giriş değerleri için aynı sonuçları döndürür.

Güncelleme: Java 1.7 server JİT alternatif uygulamalar CPU ön tanımlı dayalı birkaç statik matematik fonksiyonlarını değiştirmek mümkün. Bu fonksiyonların bir Tamsayı.() numberOfLeadingZeros. 1.7 veya daha yeni bir sunucu VM, soru gibi bir uygulama aslında binlog yukarıda daha biraz daha hızlı. Ne yazık ki, istemci TAM bu iyileştirme var gibi görünmüyor.

public static int log2nlz( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return 31 - Integer.numberOfLeadingZeros( bits );
}

Bu uygulama da yukarıda yayınlanan diğer iki uygulamaları olarak 2^32 olası tüm giriş değerleri için aynı sonuç verir.

İşte benim PC gerçek çalışma zamanları (Sandy Bridge i7):

1.7 32 Bit istemci VM GÖRDÜM:

binlog:         11.5s
log2nlz:        16.5s
log2fp:        118.1s
log(x)/log(2): 165.0s

1.7 x 64 sunucu VM GÖRDÜM:

binlog:          5.8s
log2nlz:         5.1s
log2fp:         89.5s
log(x)/log(2): 108.1s

Bu test kodu:

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 );

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Autocar

    Autocar

    11 Mart 2006
  • Richard Laxa

    Richard Laxa

    30 AĞUSTOS 2012
  • Thehalopianoplayer

    Thehalopiano

    4 ŞUBAT 2011