Logarithmus oder Schleife?

[Ishildur (PassLost)]

Hallo zusammen, ich muss in einer Bytevariablen die Position des ersten positiven Bits von Links beginnend bei 0 ermitteln. Ich habe zwei mögliche Varianten programmiert, frage mich allerdings welche denn nun schneller ist:

byte pos = (byte)(Math.floor(Math.log(prm)/Math.log(2)));

for(byte i=0;i<8;++i){
 if(prm & (0x80 >> i) != 0x00)
  pos = 7 - i; 
}

Lg Ishildur

 

[Beni]

Ich würde mal vermuten, dass der Logarithmus nicht so schnell ist.
Der Code aus "highestOneBit" dürfte noch etwas schneller sein als deine Variante (der hat weniger Befehle und keine Sprünge).

byte x = ...
int pos = Integer.highestOneBit( x );

Allerdings frag ich mich, wieso du das wissen willst. Optimierungen auf dieser Ebene bringen so gut wie garnichts...

 

[@Beni]

Hey, danke vielmals, das war genau, was ich gesucht hatte. Ich benötige dies, um Polynomdivisionen zu bewerkstelligen...

 

[SlaterB]

mit einfachen Tests kann man da aber auch was rausfinden:

class Test {

	public static void main(String[] args) throws Exception {
		long time = 0;
		time = System.currentTimeMillis();
		for (int j = 0; j < 10000; j++) {
			for (int i = -120; i < 120; i++) {
				byte b = (byte) i;
				pos2(b);
			}
		}
		System.out.println("time: " + (System.currentTimeMillis() - time));

		time = System.currentTimeMillis();
		for (int j = 0; j < 10000; j++) {
			for (int i = -120; i < 120; i++) {
				byte b = (byte) i;
				pos1(b);
			}
		}
		System.out.println("time: " + (System.currentTimeMillis() - time));

	}

	private static int pos1(byte prm) {
		return (int) (Math.floor(Math.log(prm) / Math.log(2)));
	}

	private static int pos2(byte prm) {
		for (byte i = 0; i < 8; ++i) {
			if ((prm & (0x80 >> i)) != 0x00) {
				return 7 - i;
			}
		}
		return -1;
	}

}

wären die Zahlen eng, müsste man evtl. noch die Schleifenlogik usw. mal leer zählen,
außerdem mal die Reihenfolge vertauschen und ähnliche Gegentests,
aber hier ist das Ergebnis recht deutlich

150ms Bitrechnung
>3000ms Math

die Math-Variante liefert außerden bei negativen bytes 0, die andere 7,
Integer.highestOneBit() kann ich mangels Java 1.5 grad nicht testen aber kann ja schnell eingefügt werden

------

	static double log2 = Math.log(2);

	private static int pos1(byte prm) {
		return (int) (Math.floor(Math.log(prm) / log2));
	}

wäre bisschen schneller

 

[Ark]

Darf ich auch mitspielen?!

@SlaterB: Könntest Du bitte folgende Methode auf Geschwindigkeit überprüfen? Ich bin schon gespannt auf das Ergebnis.

private static int pos3(byte prm) {
	if(prm==0) return -1;
	int i=7;
	while(prm>=0){
		prm<<=1;
		i--;
	}
	return i;
}

Ich konnte mal wieder meine Assembler-Kenntnisse nicht zurückhalten. ^^

MfG
Ark

 

[SlaterB]

zu faul selber Eclipse einzuschalten?

ein Vergleich bei längerer Laufzeit:

time: 490 // leere Vergleichsoperation die direkt prm zurückgibt
time: 2244 // deine pos3
time: 3414 // pos2 (die beim ersten Vergleich 150 hatte)

Werte schwanken natürlich um +-200 je nach Zufall

 

[Ark]

EDIT:

Nö. Ich verwende nämlich, wenn schon, NetBeans. :bae: (Obwohl ich schon mal überlegt habe, auf Eclipse umzusteigen …)

public class Test {

	public static void main(String[] args) throws Exception {
      long time = 0;
	  int dummy;
	for(int times=0;times<3;times++){
	
      time = System.currentTimeMillis();
      for (int j = 0; j < 100000; j++) {
         for (byte i = (byte)-127; i != (byte)128; i++) {
            dummy=pos1(i);
         }
      }
      System.out.println("time: " + (System.currentTimeMillis() - time));

	        time = System.currentTimeMillis();
      for (int j = 0; j < 100000; j++) {
         for (byte i = (byte)-127; i != (byte)128; i++) {
            dummy=pos2(i);
         }
      }
      System.out.println("time: " + (System.currentTimeMillis() - time));

      time = System.currentTimeMillis();
      for (int j = 0; j < 100000; j++) {
         for (byte i = (byte)-127; i != (byte)128; i++) {
            dummy=pos3(i);
         }
      }
      System.out.println("time: " + (System.currentTimeMillis() - time));

      time = System.currentTimeMillis();
      for (int j = 0; j < 100000; j++) {
         for (byte i = (byte)-127; i != (byte)128; i++) {
            dummy=Integer.highestOneBit(i);
         }
      }
      System.out.println("time: " + (System.currentTimeMillis() - time));
	}
   }

   
   
   private static int pos1(byte prm) {
      return (int) (Math.floor(Math.log(prm) / Math.log(2)));
   }

   private static int pos2(byte prm) {
      for (byte i = 0; i < 8; ++i) {
         if ((prm & (0x80 >> i)) != 0x00) {
            return 7 - i;
         }
      }
      return -1;
   }

   private static int pos3(byte prm) {
	   if(prm==0) return -1;
	   int i=7;
	   while(prm>=0){
	      prm<<=1;
	      i--;
	   }
	   return i;
	} 
}

Meine Testmethode, läuft alles, wie man sieht, dreimal durch. ^^

Ergebnis:

time: 17395
time: 721
time: 590
time: 932
time: 16854
time: 701
time: 601
time: 931
time: 16865
time: 721
time: 600
time: 952

Juhuu, meine Methode scheint sogar schneller als die der Standardbibliothek zu sein.
@Beni: Wie Du siehst, kann sich so etwas lohnen.
Und wie man sieht, sind die Methoden der Standardbibliothek relativ langsam. Ich meine, die von Sun werden ja wohl nicht jeden Idioten da programmieren lassen, oder? ???:L

Sieht aus, als täten sie's doch. :lol:
Ark

EDIT2: Hm, na gut, meine Methode ist ja private, die mitgelieferte jedoch public … wird vllt. doch etwas schwieriger einzuschätzen.

 

[Beni]

Die Methode von Integer arbeitet mit einem int, der ist 4mal länger als dein kleiner byte
Schreib die Methode mal für byte um :wink:

 

[Ark]

Hm, stimmt.

Ich würde es zu gerne machen, nur checke ich nicht ganz den Code. @_@

Hier aus dem Quelltext java.lang.Integer:

public static int highestOneBit(int i) {
	// HD, Figure 3-1
	i |= (i >>  1);
	i |= (i >>  2);
	i |= (i >>  4);
	i |= (i >>  8);
	i |= (i >> 16);
	return i - (i >>> 1);
}

Schreibe das mal bitte jemand für byte i um? Ich kann gerade nicht, keine Zeit.

MfG
Ark

EDIT: Ach so, jetzt verstehe ich das!
EDIT2: Dann müsste das für byte wohl so aussehen:

public static int pos4(byte i) {
		i |= (i >>  (byte)1);
		i |= (i >>  (byte)2);
		i |= (i >>  (byte)4);
	return i - (i >>> (byte)1);

Ergebnis:

time: 18176
time: 771
time: 641
time: 531
time: 17945
time: 772
time: 640
time: 521
time: 18467
time: 901
time: 701
time: 531

Das scheint bisher also am schnellsten. (@Beni: :applaus: ) Aber kommt dabei auch tatsächlich das raus, was wir wissen wollten? ???:L

Ark

EDIT3: Quark!
Integer.highestOneBit(int) errechnet eine Zahl, die als einziges das höchste der in der eingehenden Zahl vorkommenden gesetzten Bits gesetzt hat, jedoch nicht die Stelle dieses Bits! Nur das höchste gesetzte Bit bleibt gesetzt erhalten, alle anderen Bits werden gelöscht.

Darum ist dieser Algorithmus nicht mit den anderen hier genannten vergleichbar; sie lösen völlig verschiedene Probleme.

--> Mein Algorithmus ist der beste.


Ark

EDIT4: Hier mal eine Skizze, wie das in Assembler aussehen könnte:
benötigt: Zählerregister, Akku
Eingabe: Akku mit zu untersuchender Zahl

Zählerregister mit 7 laden
Akku OR Akku
wenn Zero-Flag, dann zu .trivial
wenn Negative-Flag, dann zu .ende

.schleife:
Akku SHL 1
Zählerregister dekrementieren
wenn nicht Negative-Flag, dann zu .schleife

.ende:
Rücksprung

.trivial:
Zählerregister mit -1 (Zweierkomplement) laden
Rücksprung

Ausgabe: Zählerregister mit Position
verändert: Akku


Ark