Laufzeit verkürzen

[Esto]

Hallo,

wir haben in der Uni eine Aufgabe zu lösen.
"Schreiben Sie ein Java Programm, welches für positive ganze Zahlen (in Dezimalschreibweise) ermittelt, ob sie gleich
der Summe all Ihrer Ziffern jeweils mit sich selbst potenziert sind "
Beispiel: 3435 = 3^3 + 4^4 +3^3 + 5^5
Ferner wurde definiert, dass 0^0 = 0 ist. Weiter wurde uns gesagt, dass es genau 3 Zahlen gibt. Die größte hat 9 Stellen.


Die Aufgabe habe ich gelöst, allerdings möchte ich gerne die Laufzeit verkürzen. (Es gibt Zusatzpunkte)
Hier mein kommentierter Quelltext:

public class Xxxx {
	
	public static void main (String []args){
		
		long[] pot = {0 , 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489}; 
		// die Zahlen 0 - 9 mit sich selber multipliziert
		long zahl; //die zu untersuchende Zahl
		long zahl2; // zahl 2 wird verglichen mit zahl
		int stelle; // die ziffer innerhalb der zahl
		
		
		for(long i = 1; i < 999999999; ++i ){ // untersuche alle Zahlen von 1 bis 999999999
			 zahl = i;
			 zahl2 = 0;
			 
			//System.out.println("=> i = " + i);
			while (zahl != 0){
				
				 stelle = (int)(zahl % 10); // 1. berechne die jeweiligen Stellen
				
				 zahl = zahl / 10;  // 2. und dividiere die Zahlen anschließend durch 10
				 					// wiederhole 1. und 2. solange zahl != 0
				
					switch (stelle){ 
					case 0: zahl2 += pot[0]; break;
					case 1: zahl2 += pot[1]; break;
					case 2: zahl2 += pot[2]; break;
					case 3: zahl2 += pot[3]; break;
					case 4: zahl2 += pot[4]; break;
					case 5: zahl2 += pot[5]; break;
					case 6: zahl2 += pot[6]; break;
					case 7: zahl2 += pot[7]; break;
					case 8: zahl2 += pot[8]; break;
					case 9: zahl2 += pot[9]; break;
					}
					// die entsprechende Stelle i (0-9) wird mit sich selbst potenziert
					// und zur zahl2 addiert

			}
			
			if(i == zahl2){ // wenn i == zahl2 ->Ausgabe
				System.out.print(i + "  ");
		
			}

			
		}
		
	}

}

Das Programm terminiert bei mir nach etwas über 2 Minuten. Wie kann ich die Laufzeit verkürzen?
Meine Ideen:
- Uns wurde gesagt, dass es genau drei Zahlen gibt, also könnte ich noch eine weiter Zählvariable einführen, die
wenn sie ==3 die for-Schleife mit einem break verlässt, ich werde es auch gleich testen, aber ich vermute, dass das nicht viel Einsparung bringt
- ein Knackpunkt könnte die for-Schleife sein (lineare Suche)..... es wurde angedeutet man könne dies optimieren,
aber wie????

Habt ihr vielleicht ein paar Denkanstöße? Gibt es noch weitere möglich Optimierungen?

Danke

 

[tfa]

Wenn zahl2 > i kannst du die while-Schleife abbrechen.
Außerdem kannst du dein switch-Statement wegoptimieren und ganz leicht mit einer Zeile schreiben (nur mal so als Anregung).

 

[Esto]

package prAufgabe4;

public class Zahlen {
	
	public static void main (String []args){
		
		long[] pot = {0 , 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489}; 
		// die Zahlen 0 - 9 mit sich selber multipliziert
		long zahl; //die zu untersuchende Zahl
		long zahl2; // zahl 2 wird verglichen mit zahl
		int stelle; // die ziffer innerhalb der zahl
		
		
		for(long i = 1; i < 999999999; ++i ){ // untersuche alle Zahlen von 1 bis 999999999
			 zahl = i;
			 zahl2 = 0;
			 
			//System.out.println("=> i = " + i);
			while ( zahl != 0 ){
				
				 stelle = (int)(zahl % 10); // 1. berechne die jeweiligen Stellen
				
				 zahl = zahl / 10;  // 2. und dividiere die Zahlen anschließend durch 10
				 					// wiederhole 1. und 2. solange zahl != 0
				
				 zahl2 += pot[stelle];
				 if(zahl2 > i)
					 break; 
				

			}
			
			if(i == zahl2){ // wenn i == zahl2 ->Ausgabe
				System.out.print(i + "  ");
		
			}

			
		}
		
	}

}

Änderungen:
- Switch Anweisung ersetzt durch zahl2 += pot[stelle];
-

 if(zahl2 > i)
 break;

eingefügt

Na klar, du hast recht. Vor allem das mit der Switchanweisung ! Da hätte ich auch selber drauf kommen können.
Das und die Abbruchbedingung der whileSchleife hat die Laufzeit schon erheblich verkürzt! Vielen Dank!

Gibt es noch weitere Möglichkeiten & Tipps?

 

[Marco13]

Vorher auf einen Quadcore 32 Sekunden, jetzt 7

import java.util.*;
import java.util.concurrent.*;

public class Xxxx
{
    public static void main(String[] args)
    {
        long before = System.nanoTime();
        doit();
        long after = System.nanoTime();
        System.out.println("Took " + (after - before) / 1e9);
    }

    private static void doit()
    {
        //doit(1, 999999999);
        doitMT(1, 999999999);
    }


    private static void doitMT(long min, long max)
    {
        int numProcessors = Runtime.getRuntime().availableProcessors();
        int numBatches = numProcessors * 2;
        ExecutorService e = Executors.newFixedThreadPool(numBatches);
        long batchSize = (long)Math.ceil((double)(max-min) / numBatches);
        List<Callable<Object>> tasks = new ArrayList<Callable<Object>>();
        for (int i=0; i<numBatches; i++)
        {
            final long minLocal = (i+0)*batchSize;
            final long maxLocal = Math.min(max, (i+1)*batchSize);
            Runnable runnable = new Runnable()
            {
                @Override
                public void run()
                {
                    doit(minLocal, maxLocal);
                }
            };
            tasks.add(Executors.callable(runnable));
        }
        try
        {
            e.invokeAll(tasks);
        }
        catch (InterruptedException e1)
        {
            Thread.currentThread().interrupt();
        }
    }

    private static void doit(long min, long max)
    {
        long[] pot = { 0, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489 };
        long zahl;
        long zahl2;
        int stelle;

        for (long i = min; i < max; ++i)
        {
            zahl = i;
            zahl2 = 0;

            while (zahl != 0)
            {
                stelle = (int) (zahl % 10);
                zahl = zahl / 10;
                zahl2 += pot[stelle];
                if (zahl2 >= i) break;
            }

            if (zahl == 0 && i == zahl2)
            {
                System.out.print(i + "  ");
            }
        }
    }


}

Weitere Abbruchkriterien könnte man sich vielleicht noch ausdenken. Theoretisch kann man da sicher noch einiges machen, könnte aber aufwändiger werden...

 

[Lumaraf]

Man könnte evtl noch etwas Performance rausholen wenn man Bereiche überspringt die definitv keinen Treffer mehr haben können.

Wenn man sich z.b. das Berechnungsergebniss für 40 anschaut kann man sich leicht vorstellen das man bis 99 keinen Treffer finden kann.

 

[SlaterB]

dieses Überspringen habe ich interessehalber gemacht, zudem die Ziffern in einem Array gespeichert,
anfangs dauerte es bei mir 170 sec oder so bis zur höchsten Zahl 438579088, lahmer Rechner,

jetzt sind es knapp 20 sec

edit: aber nicht korrekt, es wird zuviel übersprungen, die wenigen Positiv-Einträge sind noch drin,
sonst wäre es ja gleich aufgefallen

public class Test {
    public static void main(String[] args)   {
        long[] pot =  {0, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489};

        final int[] z = new int[18];
        final int nmax = z.length - 1;
        int nmin = nmax;
        long timeStart = System.currentTimeMillis();

        long zahl = 0;
        while (true)  {
            for (int n = nmax; n >= 0 && (n >= nmin || z[n] > 0); n--)   {
                if (n < nmin)   {
                    nmin = n;
                    System.out.println((long)Math.pow(10, nmax - nmin) + ", time: " + (System.currentTimeMillis() - timeStart));
                }
                if (z[n] == 10)  {
                    z[n] = 0;
                    z[n - 1]++;
                }
            }

            if (zahl == 0) {
                for (int n = nmin; n <= nmax; n++) {
                    zahl = 10 * zahl + z[n];
                }
            }

            long zahl2 = 0;
            int n = nmin;
            for (; n <= nmax; n++) {
                zahl2 += pot[z[n]];
                if (zahl2 > zahl) break;
            }

            if (zahl2 > zahl)   {
                z[n] = 10;
                zahl = 0;
                continue;
            }

            if (zahl2 == zahl)  {
                System.out.println("found: " + zahl + ", time: " + (System.currentTimeMillis() - timeStart));
            }
            zahl++;
            z[nmax]++;
        }
    }
}

 

[Marco13]

@Lumaraf und SlaterB: Kann man das (mit der 40, oder das was SlaterB dort "überspringt") mit Worten begründen, die bezüglich ihrer Überzeugungskraft irgendwo unterhalb eines formalen mathematischen Beweises, aber doch etwas über "Das sieht man doch" liegen?

EDIT @SlaterB: Bei mir scheint das erstmal nicht schneller zu sein... ???:L
1000000000, time: 40924
Vorher bis 999999999 ca. 32 sec. ... Vielleicht täusche ich mich auch...

 

[SlaterB]

@Marco13
interessanter Einwand, dabei fällt mir auf dass ich wohl falsch liege, worauf du vielleicht schon anspielst,
ich hatte vorher eine nicht ganz so schnelle Version, indem ich als Grenze nicht die Zahl selber, sondern die nächsthöhere Zehnerpotenz genommen hatte,
für 45978 etwa 100.000,
damit dürfte klar sein, dass egal welche Ziffer man auf 9 erhöht, die Zahl selber immer noch unter der Grenze liegt, die Potenzsumme dazu aber noch größer wird, also über der Grenze liegt,

damit dauert es 35-40 sec bei mir (bis 438579088 gefunden ist), schade dass die gepostete 20 sec-Variante dann nicht sicher funktioniert,
also: sie ist falsch, denn wenn man eine frühe Ziffer erhöht, erhöht das auch die Grenze ungemein

edit: hmmpf, auch dies ist falsch, denn wenn man frühe Ziffern erhöht überspringt man viel zu viel,
von 428999 auf 498999 erhöht (Ziffer 2) überspringt auch 430000 welche ja viel niedrigere Potenzsumme hat
'damit dürfte klar sein' ist also nie zu vertrauen

edit: übersprungen werden kann, nun hoffentlich mal was richtiges, wenn allein der Faktor für eine Ziffer größer ist als die nächsthöhere Zehnerpotenz der ganzen aktuellen Zahl,
z.B. bei 900.001, der Faktor zur 9 ist mit 387.420.489 alles überstrahlend, da kann man sich die nächsten 100.000 Zahlen sparen und zur Zahl 1.000.000 übergehen,
spart gerade um 10% in einem gewissen Bereich, bei sehr vielen Ziffern ist zumindest dieser Trick für sich auch nicht mehr anzuwenden


----

was ich eigentlich gerade posten wollte:

eine ganz andere Idee mal nur als Vorschau:
alle möglichen Ziffer-Kombinationen X durchlaufen, bei maximal 18 Zifffern (bei mehr wirds übel mit long ):
18x 0
17x 0, 1x 1
16x 0, 2x 1
16x 0, 1x 1, 1x 2
16x 0, 0x 1, 2x 2
15x 0, 3x 1
...
1x 8, 17x9
0x 8, 18x9


für jede Kombination ergibt sich direkt die Potenzsumme,
14x 0, 2x 3, 1x 4, 1x 5 = 3435 und man kann genauso ziemlich direkt prüfen, ob diese Potenzsumme genau die passenden Ziffern hat,
alle anderen Zahlen aus diesen Ziffen wie 3345, 5334 oder auch 33000000050004 sind nie zu prüfen

hängt jetzt davon ab, wieviele Kombinationen X es gibt, extrem wenig werden es auch nicht sein,
aber bestimmt doch weniger als Zahlen einzeln anzuschauen, selbst mit Überspringen (edit: was man anscheinend gar nicht tun sollte..)

 

[Marco13]

Hey, 3 edit's Aber so ähnlich ging's mit bei dem Nachsatz, den ich zur Miltithreading-Variante schreiben wollte, auch: Ich wollte noch ein paar der möglichen Abbruchkriterien aufzählen, aber bei jedem kam dann dieses "Ach moment, das geht ja DOCH nicht..."

Irgendwelche "trivialen" Übersprinungen,a la "man braucht nur jede Zahl zu testen, die x modulo y ist" oder so, sind mir spontan nicht eingefallen (was nicht heißt, dass es keine gibt...).

Dann hatte ich überlegt, ob man mit dynamischer Programmierung was machen könnte: "Wenn man für n schon ein Ergebnis hat, kann man daraus schließen, dass es für n+x keine Lösung geben kann" (EDIT> Oder auch "wenn man für x und y schon keine Lösung gefunden hat, kann es auch für x+y keine geben" <EDIT) aber auch da müßte man genauer überlegen.

Ich dachte dann auch daran, die Ziffern in einen Array zu packen - aber diesen noch aufsteigend zu sortieren. Da könnte man vielleicht (!) noch einiges rausholen, aber das Zerlegen und in einen Array packen zusammen mit einer Sortierung könnte die Zeit auffressen, die man spart - da die Alternative ja in bezug auf den Rechenaufwand ja eigentlich "trivial", es geht ja nur darum, dass es zu viele Zahlen sind.

Der "cheat"-Ansatz sollte aber auch in Erwägung gezogen werden - wenn es eine Aufgabe ist, besteht sie vielleicht auch darin, zu wissen, wo man nach solchen Sachen suchen kann: Vielleicht findet man ausgehend von https://oeis.org/search?q=0++1++3435++438579088++&language=english&go=Search unter den Referenzen ein paar hilfreiche Hinweise....


EDIT: Auch noch eins Das mit den "Alle Kombimationen" konnte ich spontan jetzt nicht nachvollziehen... Wären das nicht gerade alle 18stelligen Zahlen? Oder ging es nur darum, "aus einer anderen Richtung" an das Problem zu gehen, nämlich nicht zu überprüfen, ob eine gegebene Zahl die Ziffernpotenzsumme ist, sondern Ziffernpotenzsummen zu bilden, und zu schauen, ob eine durch die passende Zahl entstanden ist?
Irgendwas "branch-and-bound"-artiges kam mir auch in den Sinn, aber langsam verfalle ich wohl ins Name-dropping

 

[SlaterB]

Hey, 3 edit's

Änderungszeitpunkt
		- 	SlaterB 	24.11.2011 16:49
		- 	SlaterB 	24.11.2011 16:48
		- 	SlaterB 	24.11.2011 16:47
		- 	SlaterB 	24.11.2011 16:46
		- 	SlaterB 	24.11.2011 16:32
		- 	SlaterB 	24.11.2011 16:32
		- 	SlaterB 	24.11.2011 16:23
		- 	SlaterB 	24.11.2011 16:22
		- 	SlaterB 	24.11.2011 16:22
		- 	SlaterB 	24.11.2011 16:19
Ursprünglicher Beitrag 	SlaterB 	24.11.2011 16:16

 

[Marco13]

Joa, das sind ja nur 3 oder 4 -Tippfehler eine Minute später zählen ja nicht (Außer, wenn es 20 aufeinanderfolgende Minuten sind )

EDIT: Hab' oben noch ein EDIT zum kombinations-Ansatz drin...

 

[Esto]

Hey,

vielen Dank erstmal für die vielen Ideen.

Ich habe noch mal genauer gelesen und da steht es sollen die ERSTEN drei Zahlen mit dieser Eigenschaft ausgegeben werden. Also muss man nicht bis 999999999 gehen.

Und dann bin ich mir nicht sicher, ob gefordert ist, dass wirklich alle Zahlen auf diese Eigenschaft untersucht werden sollen. Wenn dies zuträfe, dann kann man leider nicht irgendwelche Intervalle überspringen Ich werd mal nachfragen.

 

[Lumaraf]

Hab einen alternativen Algorithmus gefunden der das Problem in wenigen Millisekunden lösen kann.

Wenn man damit anfängt alle möglichen Ziffernpotenzsummen zu berechnen und diese dann überprüft ob diese Zahlen ihrerer eigenen Ziffernpotenzsumme entsprechen kommt man genauso zum Ergebniss. Bei dem Ansatz ist es dann auch sehr einfach die Zahlen herauszufiltern die sowieso zur selben Ziffernpotenzsumme führen würden. Es ist egal ob man den Wert für 12, 21 oder 102 berechnet, das Ergebniss wäre in allen fällen 5.

public class Test
{
	private static long[] pot = { 0, 1, 4, 27, 256, 3125, 46656, 823543,
			16777216, 387420489 };

	public static void main(final String[] args)
	{
		calc(0, 9, 0, 0);
	}

	public static void calc(final int level, final int max, final long value,
			final long sum)
	{
		if (level == 9) {
			if (check(sum))
				System.out.println(sum);
			return;
		}

		for (int n = 0; n <= max; n++)
			calc(level + 1, n, value * 10 + n, sum
					+ pot[n]);
	}

	public static boolean check(final long value)
	{
		if (value <= 0)
			return false;

		long sum = 0;
		long num = value;
		while (num > 0) {
			sum += pot[(int) (num % 10)];
			num /= 10;
		}
		return sum == value;
	}
}

 

[Marco13]

Das wäre dann ja das...

Oder ging es nur darum, "aus einer anderen Richtung" an das Problem zu gehen, nämlich nicht zu überprüfen, ob eine gegebene Zahl die Ziffernpotenzsumme ist, sondern Ziffernpotenzsummen zu bilden, und zu schauen, ob eine durch die passende Zahl entstanden ist?

...aber dass es so einfach und schnell ist, hätte ich nicht gedacht

 

[Esto]

wow gute Arbeit. Nur kann ich das leider nicht als Lösung abgeben Dann würde ich mich ja mit fremden Federn schmücken. Aber ich habe wenigstens was dazugelernt ))) Danke