ich hab laufzeit...

[Hm...]

hi leute,

ich habe gerade festgestellt, dass eine meiner methoden mehrere sekunden laufzeit in anspruch nimmt. die methode berechnet die silvesterscheSiebformel.

heißt:

input:
p1,p2,p3,... wobei diese p's die jeweiligen wahrscheinlichkeiten sind, dass innerhalb eines tages ein ereignis eintritt

output:
P(alle zeiteinheiten), also die wahrscheinlichkeit, dass dieses ereignis einmal in der gesamten zeiteinheit eintrit.

mein code:

  
  
private static Double silvesterscheSiebformel(Double[] probilitys)  
	{  
		Double p=0.0;  
		  
		for(int k=1;k<=probilitys.length;k++)  
		{  
			Double z=Math.pow(-1, k-1);  
			Double n=0.0;  
			ArrayList<Double> kombis=getKombis(probilitys,k);  
			for(int i=0;i<kombis.size();i++)  
			{  
				n+=kombis.get(i);  
			}  
			p+=z*n;  
		}  
		  
		return p;  
	}  
	  
	/**  
	 * Berechnet die wahrscheinlichkeit einer jeden kombi mit k ereignissen.  
	 * @param probilitys  
	 * @param k  
	 * @return  
	 */  
	private static ArrayList<Double> getKombis(Double[] probilitys,int k)  
	{  
		ArrayList<Double> list =new ArrayList();  
		int[] zeiger=new int[k];//zeigen auf die jeweilige kombination  
		for(int i=0;i<k;i++)  
		{  
			zeiger[i]=i;  
		}  
			  
		while(1==1)//jeweils eine zul"assige kombination  
		{  
			Double p=1.0;  
			for(int i=0;i<zeiger.length;i++)  
			{  
				if(probilitys[zeiger[i]]!=null)  
					p*=probilitys[zeiger[i]];  
				else p*=0;  
			}  
			list.add(p);  
			if(zeiger[0]==probilitys.length-k) break; //abbruchbedingung  
			  
			//verschiebung der eiger f"ur next kombination  
			//bewege den indize um eins, der abstand von 1 zu next indize hat ODER bewege letzten indize um eins  
			int c=driveInd(zeiger);  
			zeiger[c]++;  
		}		  
		return list;  
	}  
	  
	/**  
	 * returnt, welcher indize um eins bewegt werden muss.  
	 * Hierbei wird jener ausgew"ahlt, welcher eine differenz von 1 zu seinem nachfolger hat ODER der letzte indize.  
	 * @param zeiger  
	 * @return  
	 */  
	private static int driveInd(int[] zeiger)  
	{  
		for(int i=0;i<zeiger.length-1;i++)  
		{  
			if(Math.abs(zeiger[i]-zeiger[i+1])>1) return (i);  
		}		  
		return (zeiger.length-1);  
	}

verbraucht ziemlich viel laufzeit, habt ihr eventuell ideen wie ich diese laufzeit verringern kann? mir fehlt derzeit noch ein passender ansatz...

[Hm...]

folgendes verwirrt mich:

ich habe eine eingabe von einem probability array der länge 40 und insgesamt (wenn ich richtig geguckt habe) eine laufzeit in laudannotation von O(probilities.length * Max(kombis.length,probilites.length²))

eigentlich sollte das schnell gehen....

[Whouzuo]

folgendes verwirrt mich:

ich habe eine eingabe von einem probability array der länge 40 und insgesamt (wenn ich richtig geguckt habe) eine laufzeit in laudannotation von O(probilities.length * Max(kombis.length,probilites.length²))

Also ich sehe da auf den ersten Blick verschachtelte Schleifen mit einer Tiefe von 4 Ebenen.
An deiner Stelle würde ich erstmal einen Profiler benutzen oder manuell an wichtigen Stellen (z.B. am Anfang jedes Durchlaufs einer Schleife) Timestamps ausgeben. Damit kannst du das Problem viel besser analysieren und eingrenzen.

[Hm...]

danke für die antwort, ich überlege gerade anders heranzugehen und die berechnungsart zu ändern.

ich habe:
Summe von 1 bis n
(-1)^(k+1)

mal summe aller k elementigen teilmengen von {1,...,n} von produkt von i bis k von p_i

der binominalkoeffizient nimmt sein maximum bei k=n/2 an (n über k), also baue ich mir erstmal ein double array mit n/2 elementen und versuche irgendwie diese doubles passend in der hinteren summe aufzurufen, so dass nicht soviel berechnet werden muss....

[bubble]

private static Double silvesterscheSiebformel(Double[] probilitys)
{
/* ... /
for(int k=1;k<=probilitys.length;k++)
{
Double z=Math.pow(-1, k-1);
/ ... /
p+=zn;
}
/* ... */
}

  

> verbraucht ziemlich viel laufzeit, habt ihr eventuell ideen wie ich diese laufzeit verringern kann? mir fehlt derzeit noch ein passender ansatz...  
  
Math.pow() könnte da - je nach dem wie oft das wirklich aufgerufen wird - relativ zeitfressend sein.  
  
Schnell und schmutziger Test:  
~~~java
public class Test {  
	public static void main(String[] args) {  
		{  
			long start = System.currentTimeMillis();  
			double z = 0;  
			for(int i=0; i<10000000; i++) {  
				for(int k=1; k<40; k++) {  
					z = Math.pow(-1, k-1);  
				}  
			}  
			System.out.println(System.currentTimeMillis()-start);  
		}  
		  
		{  
			long start = System.currentTimeMillis();  
			double z = 0;  
			for(int i=0; i<10000000; i++) {  
				for(int k=1; k<40; k++) {  
					z = k % 2 == 0 ? -1 : 1;  
				}  
			}  
			System.out.println(System.currentTimeMillis()-start);  
		}  
	}  
}

Liefert mir als Ausgabe:
7983
2

MfG
bubble

[bubble]

Liefert mir als Ausgabe:
7983
2

Jvisualvm meinte übrigens, dass Math.pow() 7977,35ms und z = k % 2 == 0 ? -1 : 1  2,24ms brauchte.

MfG
bubble

[MudGuard]

Hi,

wenn ich das richtig sehe, wechselt z zwischen 1 und -1, und startet mit 1 im ersten Schleifendurchlauf.

  

> 	double z = 0;  
> 	for(int k=1; k<40; k++)  
> 	{  
> 		z = k % 2 == 0 ? -1 : 1;  
> 	}  

Also

  
double z = -1;  
  
for (int k=1; k<40; k++)  
{  
   z = 0 - z;  
   //whatever ...  
}  

Ganz ohne Division (ja, auch % ist eine Division)

cu,
Andreas

[bubble]

wenn ich das richtig sehe, wechselt z zwischen 1 und -1, und startet mit 1 im ersten Schleifendurchlauf.

Jup.

double z = -1;

for (int k=1; k<40; k++)
{
   z = 0 - z;
   //whatever ...
}

> Ganz ohne Division (ja, auch % ist eine Division)  

Auf die Lösung wäre ich wohl nie gekommen, da wirds dann aber langsam mit dem Zeitmessen schwer (obwohls logisch ist, dass das die schnellste Methode ist) ;p  
  
MfG  
bubble

-- 
If "god" had intended us to drink beer, he would have given us stomachs. - David Daye

[MudGuard]

Hi,

wenn ich das richtig sehe, wechselt z zwischen 1 und -1, und startet mit 1 im ersten Schleifendurchlauf.
Jup.

double z = -1;

for (int k=1; k<40; k++)
{
   z = 0 - z;
   //whatever ...
}

> > Ganz ohne Division (ja, auch % ist eine Division)  
> Auf die Lösung wäre ich wohl nie gekommen, da wirds dann aber langsam mit dem Zeitmessen schwer (obwohls logisch ist, dass das die schnellste Methode ist) ;p  
  
Generell: soll eine Variable x zwischen den Zahlen a und b wechseln (z.B. 5 und 3):  
  
Initialisierung:  
x = a;  //z.B. x = 5;  
  
und dann zum Wechseln:  
x = (a + b) - x; //z.B. x = 8 - x;  
  
In dem hier vorliegenden Fall ist a = -1, b = 1, a+b = 0.  
  
cu,  
Andreas

-- 
[Warum nennt sich Andreas hier MudGuard?](http://MudGuard.de/)  
[O o ostern ...](http://ostereier.andreas-waechter.de/)  
  
Fachfragen per Mail sind frech, werden ignoriert. Das Forum existiert.  

[Matthias Apsel]

Om nah hoo pez nyeetz, MudGuard!

double z = 0;  
for(int k=1; k<40; k++)  
{  
  z = k % 2 == 0 ? -1 : 1;  
}  

> Also  
> ~~~java
  

> double z = -1;  
>   
> for (int k=1; k<40; k++)  
> {  
>    z = 0 - z;  
> }  
> 

Ganz ohne Division (ja, auch % ist eine Division)

Und auch ohne Vergleich mit anschließender Verzweigung.

Matthias

[JürgenB]

Hallo,

z = 0 - z;

und weil wir geizig sind:

z = -z;

Gruß, Jürgen

[Matthias Apsel]

Om nah hoo pez nyeetz, JürgenB!

und weil wir geizig sind:
z = -z;

Genau, vor allem beim Speicherplatz

  
byte z = -1;  
  
for (byte k=1; k<40; k++)  
{  
    z = z ^ (1 << 8);  
}  

Matthias

[bubble]

und weil wir geizig sind:
z = -z;
Genau, vor allem beim Speicherplatz

byte z = -1;

for (byte k=1; k<40; k++)
{
    z = z ^ (1 << 8);
}

  
Hat man dabei aber nicht wieder Performance-Einbüßung? Bit-Shift + XOR vs. Subtraktion?  
  
(Des Weiteren meine ich mal irgendwo aufgeschnappt zu haben, dass bytes bei mathematischen Ausdrücken auch als ints gehandhabt werden, leider finde ich die Quelle nicht mehr :( )  
  
MfG  
bubble

-- 
If "god" had intended us to drink beer, he would have given us stomachs. - David Daye

[MudGuard]

Hi,

z = z ^ (1 << 8);

> Hat man dabei aber nicht wieder Performance-Einbüßung? Bit-Shift + XOR vs. Subtraktion?  
  
(1 << 8) sollte vom Compiler einmalig berechnet werden, nicht erst bei jedem Schleifendurchgang.  
  
cu,  
Andreas

-- 
[Warum nennt sich Andreas hier MudGuard?](http://MudGuard.de/)  
[O o ostern ...](http://ostereier.andreas-waechter.de/)  
  
Fachfragen per Mail sind frech, werden ignoriert. Das Forum existiert.  

[Matthias Apsel]

Om nah hoo pez nyeetz, MudGuard!

z = z ^ (1 << 8);

> > Hat man dabei aber nicht wieder Performance-Einbüßung? Bit-Shift + XOR vs. Subtraktion?  
  
Man müsste es halt mal [schnell und schmutzig](https://forum.selfhtml.org/?t=215103&m=1472566) testen.  
  

> (1 << 8) sollte vom Compiler einmalig berechnet werden, nicht erst bei jedem Schleifendurchgang.  
  
Stimmt.  
  
Matthias

-- 
Der Unterschied zwischen Java und JavaScript ist größer als der zwischen [Boll und Bollerwagen](http://selfhtml.apsel-mv.de/java-javascript/index.php?buchstabe=B#boll).  
![](http://www.billiger-im-urlaub.de/kreis_sw.gif)  

[MudGuard]

Hi,

z = 0 - z;

und weil wir geizig sind:

Die 0 hatte ich schon in Hinblick auf die Verallgemeinerung, also aus didaktischen Gründen, dringelassen. ;-)

cu,
Andreas

[bubble]

Die 0 hatte ich schon in Hinblick auf die Verallgemeinerung, also aus didaktischen Gründen, dringelassen. ;-)

Wird wahrscheinlich eh durch den .... uhmm compiler kann man es ja eigentlich nicht nennen ... "bytecoder" weg-optimiert oder?
Ich meine wenn er/sie/es Sting-Verknüpfungen in StingBuilder-Code umoptimieren kann, schafft sowas auch.

MfG
bubble

[MudGuard]

Hi,

Ganz ohne Division (ja, auch % ist eine Division)
Und auch ohne Vergleich mit anschließender Verzweigung.

Wobei bei vielen Prozessoren die Division meist deutlich teurer ist, so daß deren Wegfallen einen deutlicheren Performance-Gewinn bringt als das Weglassen eines Vergleichs oder einer Addition.

cu,
Andreas