Größtes Palindrom Produkt aus zwei dreistelligen Zahlen

[DrPils]

Moin,

Ich hänge gerade an folgender Aufgabe:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

https://projecteuler.net/problem=4

    public static boolean isPalindrome(int number) {
        int[] digitArray = splitNumberInDigitArray(number);
        for (int i = 0, j = digitArray.length - 1; i < digitArray.length / 2; i++, j--) {
            if (digitArray[i] != digitArray[j]) return false;
        }
        return true;
    }

    public static int[] splitNumberInDigitArray(int number) {
      return   Integer.toString(number)
                .chars()
                .map(c-> Character.digit(c, 10))
                .toArray();
    }

    private static int problem4() {
        for (int i = 999; i > 99; i--) {
            for (int j = 999; j >= i; j--) {
                int product = i * j;
                if (Mathematics.isPalindrome(product)) return product;
            }
        }
        throw new RuntimeException();
    }

Also isPalindrome und splitNumberInDigitArray, passen diese bestehen die Tests.

Wenn ich problem4() mit 99 Teste, bekomme ich auch das Ergebniss aus der Beschreibung.
Mit 999 bekomme ich 888888 was das Produkt aus 924 und 962 ist.
Die Lösung wird aber nicht akzeptiert.
Ich nehme an es liegt irgendwie an der Reihenfolge wie ich prüfe:

999 * 999
998 * 999
998 * 998
997 * 999
997 * 998
997 * 997
996 * 999
996 * 998
996 * 997
996 * 996
995 * 999
995 * 998
995 * 997
995 * 996
995 * 995
...

Mir leuchtet aber eigentlich nicht ein was daran falsch sein sollte.

 

[DrPils]

Ok der Fehler ist wohl 923 * 999 ist grösser als 924 * 962, habe das aber noch nicht auf Palindrom geprüft.

Wie könnte man da das nach der Größe des Produktes durchgehen?

Habe jetzt mal einfach alle Palindrom produkte von 999 * 999 - 100 * 100 in eine Liste gelegt und das größte davon genommen. Funktioniert, ist aber mist

 

[LimDul]

So eine richtig schlaue Idee hab ich nicht, weil es im Endeffekt darum geht die Schleifen für i und j zu optimieren. Und das wiederum ist Frage, wann ist ein Produkt a*b kleiner oder größer als ein Produkt c*d.

Die einzige Ad-Hoc Optimierung die mir einfällt, wenn man rausgefunden hat, dass z.B. 924*962 ein Palindrom ist, braucht man alle Produkte mit i und j kleiner als 924 nicht mehr testen. Denn das Produkt ist auf jeden kleiner als das bereits gefunden. Aber ob 923*963 kleiner oder größer als das Produkt ist, da fällt mir jetzt keine schlaue Bedingung für ein.

 

[KonradN]

Also generell kann man alles etwas einschränken:

1) das a * b = b * a ist, reicht es, alle Produkte zu prüfen für die gilt a >= b. Du startest also mit 999*999, 999*998, ... und Du startest immer mit b = a.

2) Sobald Du ein Palindrom gefunden hast, kannst Du damit Grenzen aufstellen:
Du hast 999 * 923 als Palindrom gefunden. Also kannst Du bei 999 aufhören, denn alle weiteren Palindrome mit 999 vorne wären ja kleiner.
Wenn Du nun 998 testest, dann hast Du als Grenze für die zweite Zahl: 999 * 923 / 998. Das musst Du aber nicht ausrechnen. Du kennst ja das Palindrom und wenn a *b < Palindrom ist, dann kannst Du die Schleife für b abbrechen.

Ich denke, dass Du damit schon sehr viele Versuche gar nicht erst betrachten musst.

 

[DrPils]

Also generell kann man alles etwas einschränken:

1) das a * b = b * a ist, reicht es, alle Produkte zu prüfen für die gilt a >= b. Du startest also mit 999*999, 999*998, ... und Du startest immer mit b = a.

2) Sobald Du ein Palindrom gefunden hast, kannst Du damit Grenzen aufstellen:
Du hast 999 * 923 als Palindrom gefunden. Also kannst Du bei 999 aufhören, denn alle weiteren Palindrome mit 999 vorne wären ja kleiner.
Wenn Du nun 998 testest, dann hast Du als Grenze für die zweite Zahl: 999 * 923 / 998. Das musst Du aber nicht ausrechnen. Du kennst ja das Palindrom und wenn a *b < Palindrom ist, dann kannst Du die Schleife für b abbrechen.

Ich denke, dass Du damit schon sehr viele Versuche gar nicht erst betrachten musst.

Dankeschön
Habe das mal so umgesetzt, denke ich habe dich richtig verstanden. Ist jetzt auch sehr schnell durch der Algorithmus, leserlich ist zwar anders....

    private static int problem4() {
        int lastPalindrome = 0;
        for (int i = 999; i > 99; i--) {
            for (int j = i; i >= j; j--) {
                int product = i * j;
                if (product < lastPalindrome) break;
                if (Mathematics.isPalindrome(product)) {
                    lastPalindrome = product;
                    break;
                }
            }
        }
        return lastPalindrome;
    }

 

[temi]

Ok der Fehler ist wohl 923 * 999 ist grösser als 924 * 962,

Mein Taschenrechner rechnet 923 * 999 = 922077. Das ist doch kein Palindrom.

EDIT:

Der größte Wert scheint 993 * 913 = 906609 zu sein. Ok, muss nicht so sein

Oder hab ich das alles falsch verstanden?

 

[DrPils]

Mein Taschenrechner rechnet 923 * 999 = 922077. Das ist doch kein Palindrom.

Sagte ja niemand, die Möglichkeit besteht aber bevor du es in den Taschenrechner tippst

993 * 913 = 906609 zu sein

ist richtig, Problem war dann nach meinem zweiten Post eher die Effizienz der Lösung, was @KonradN ja sehr gut optimiert hat

 

[httpdigest]

Man kann das ganze Problem auch von der andere Seite aus lösen: Also nicht zwei Nummern finden, die zusammenmultipliziert ein Palindrom ergeben, sondern: Palindrome konstruieren und den größten dreistelligen Teiler finden:

Spoiler

public class Palindrome {
    private static int reverseInt(int v) {
        int r, res = 0;
        while (v > 0) {
            r = v % 10;
            res = res * 10+ r;
            v /= 10;
        }
        return res;
    }
    private static int build3x3Palindrome(int num) {
        return num * 1000 + reverseInt(num);
    }
    private static int findFirstDivisor(int palindrome, int v) {
        for (int i = 999; i >= 100 && i > v; i--)
            if (palindrome % i == 0)
                return i;
        return -1;
    }
    public static int findLargest3x3Palindrome() {
        for (int v = 999; v > 0; v--) {
            int p = build3x3Palindrome(v);
            int d = findFirstDivisor(p, v);
            if (d != -1)
                return p;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(findLargest3x3Palindrome());
    }
}

 

[httpdigest]

Und eine sehr große Zeit geht durch deinen eher suboptimalen Test verloren, ob die Zahl ein Parlindrom ist. Gerade, weil das ja der Teil ist, der am häufigsten ausgeführt wird, weil es direkt in der innersten Schleife ist, solltest du hier noch optimieren. Hier solltest du eher nicht etwas mit Streams und nach Array konvertieren machen, sondern einfach eine Methode schreiben, die einen Integer "umdreht" und dann mittels == prüfen, ob der umgedrehte Integer gleich dem Original ist.

Spoiler

Z.B. so:

private static int reverseInt(int v) {
    int r, res = 0;
    while (v > 0) {
        r = v % 10;
        res = res * 10 + r;
        v /= 10;
    }
    return res;
}
public static boolean isPalindrome(int number) {
    return number == reverseInt(number);
}

 

[Arrive5784]

Ok der Fehler ist wohl 923 * 999 ist grösser als 924 * 962, habe das aber noch nicht auf Palindrom geprüft.

Ich komme da auf (99, 91) und (993, 913). Btw., man ändert immer zuerst die zweite Variable. :

import java.util.Arrays;

public class PalindromeProduct {
    public int[] find(int digits) {
        int fence = 0;
        int r1 = -1, r2 = -1;
        int a = (int) Math.pow(10, digits) - 1;
        int b = (int) Math.pow(10, digits) - 1;
        for (int i = a; i > 0; i--) {
            for (int j = b; j > 0; j--) {
                int p = i * j;
                if (p > fence) {
                    if (palindrome(p)) {
                        fence = p;
                        r1 = i;
                        r2 = j;
                    }
                } else {
                    break;
                }
            }
        }
        return new int[] {r1, r2};
    }

    public boolean palindrome(int p) {
        String s = String.valueOf(p);
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        PalindromeProduct tester = new PalindromeProduct();
        System.out.println(Arrays.toString(tester.find(2)));
        System.out.println(Arrays.toString(tester.find(3)));
    }
}

 

[Arrive5784]

Btw obiger Code ist nur bis digits=4 korrekt. Darüber hinaus brauchen wir schwere Geschütze (Kanonen, Moerser, Artillerie).

 

[Jw456]

Btw obiger Code ist nur bis digits=4 korrekt. Darüber hinaus brauchen wir schwere Geschütze (Kanonen, Moerser, Artillerie).

Ja der Algorithmus ist es weniger. Sonder der Datentyp int der dann nicht mehr reicht da 99999*99999 den Wertebereich von int ist.

BigInteger könnte da helfen.

 

[LimDul]

Spannend wäre - aber das sprengt den Scope der Aufgabe - sich mal mathematisch zu überlegen, ob es da Regeln gibt, wann ein Produkt ein Palindrom ist. Ich mein, die Zahl muss ja ein Form wie diese n=abccba, Sprich es gilt:
n=a + 10*b + 100*c + 1000*c + 10000*b+100000*a = a*100001 + b*10010 + c*1100

Keine Ahnung ob man daraus was bzgl. Teiler & Co ableiten kann.

 

[Arrive5784]

Da:

import java.math.BigInteger;
import java.util.Arrays;

public class PalindromeProduct {
    public int[] find(int digits) {
        BigInteger fence = BigInteger.ZERO;
        int[] r = {-1, -1};
        int a = (int) Math.pow(10, digits) - 1;
        System.out.println("a = " + a);
        for (int i = a; i > 0; i--) {
            BigInteger b = BigInteger.valueOf(i);
            if (b.multiply(b).compareTo(fence) <= 0) {
                break;
            }
            for (int j = i; j > 0; j--) {
                BigInteger p = b.multiply(BigInteger.valueOf(j));
                if (p.compareTo(fence) > 0) {
                    if (palindrome(p)) {
                        fence = p;
                        r[0] = i;
                        r[1] = j;
                    }
                } else {
                    break;
                }
            }
        }
        return r;
    }

    public boolean palindrome(BigInteger p) {
        String s = String.valueOf(p);
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        PalindromeProduct tester = new PalindromeProduct();
        System.out.println(Arrays.toString(tester.find(2)));
        System.out.println(Arrays.toString(tester.find(3)));
        System.out.println(Arrays.toString(tester.find(4)));
        System.out.println(Arrays.toString(tester.find(5)));
        System.out.println(Arrays.toString(tester.find(6)));
        System.out.println(Arrays.toString(tester.find(7)));
        System.out.println(Arrays.toString(tester.find(8)));
    }
}

a = 99
[99, 91]
a = 999
[993, 913]
a = 9999
[9999, 9901]
a = 99999
[99979, 99681]
a = 999999
[999999, 999001]
a = 9999999
[9998017, 9997647]
a = 99999999
[99999999, 99990001]

Kann es denn wirklich sein, dass jedes zweite Produktepaar der Gestalt (99999..9, 9990..01) ist? Das ist ja fast trivial.^^

BTW: Ich habe den Code jetzt weitestgehend optimiert. Aber er ist dennoch wegen dem Einsatz von BigInteger langsam. Für digits > 8 müsste man sich was anderes überlegen.

 

[Arrive5784]

Gerade gefunden https://mathematica.stackexchange.c...e-which-is-the-product-of-two-2-digit-numbers

Wolfram Alpha kann das wohl auch... aber es ist... kompliziert.

 

[DrPils]

Ich komme da auf (99, 91) und (993, 913). Btw., man ändert immer zuerst die zweite Variable. :

import java.util.Arrays;

public class PalindromeProduct {
    public int[] find(int digits) {
        int fence = 0;
        int r1 = -1, r2 = -1;
        int a = (int) Math.pow(10, digits) - 1;
        int b = (int) Math.pow(10, digits) - 1;
        for (int i = a; i > 0; i--) {
            for (int j = b; j > 0; j--) {
                int p = i * j;
                if (p > fence) {
                    if (palindrome(p)) {
                        fence = p;
                        r1 = i;
                        r2 = j;
                    }
                } else {
                    break;
                }
            }
        }
        return new int[] {r1, r2};
    }

    public boolean palindrome(int p) {
        String s = String.valueOf(p);
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        PalindromeProduct tester = new PalindromeProduct();
        System.out.println(Arrays.toString(tester.find(2)));
        System.out.println(Arrays.toString(tester.find(3)));
    }
}

Wo ist eigentlich der Unterschied zu meiner implementierung?

 

[Arrive5784]

Wo ist eigentlich der Unterschied zu meiner implementierung?

Weiß ich nicht genau, weil ich from Scratch begonnen hatte... Meine funktioniert^^

 

[DrPils]

Meins doch auch....

 

[Arrive5784]

Meins doch auch....

Nö,

Mit 999 bekomme ich 888888 was das Produkt aus 924 und 962 ist.
Die Lösung wird aber nicht akzeptiert.

... sonst hätte ich mir die Arbeit doch gar nicht gemacht...

 

[DrPils]

So ein Thread hat meistens mehrere Beiträge...

https://www.java-forum.org/thema/groesstes-palindrom-produkt-aus-zwei-dreistelligen-zahlen.197595/#post-1309502

 

[Arrive5784]

Hatte meine Lösung aber schon vor deinem Posting fertig, diese allerdings zeitlich verzögert gepostet...

 

[MarvinsDepression]

Der Spoiler von

Man kann das ganze Problem auch von der andere Seite aus lösen: Also nicht zwei Nummern finden, die zusammenmultipliziert ein Palindrom ergeben, sondern: Palindrome konstruieren und den größten dreistelligen Teiler finden:

hat mich dann doch gejuckt das selbst zusammen zu zimmern. Ging mir dann doch nicht so leicht von der Hand, ermöglicht nun dafür einen direkten Laufzeitvergleich der unterschiedlichen Herangehensweisen. Die MainKlasse mit dem ursprünglichen LösungsAnsatz. Die Other...Klasse mit der angedeuteten schnelleren Methode.
Trotz verschiedener Optimierungsversuche (MainKlasse: checkPalindrome1..4() ) ist der Laufzeitunterschied eklantant. Die Other...Klasse benötigt gerade mal 2% der gesamten Programmlaufzeit.


ursprünglichen LösungsAnsatz

public class TestOmania {
    
    private static final int MAX_LENGTH = 9;
    private final int length, maxValue, minValue;
    
    
    public TestOmania(int l) {
        length = l;
        maxValue = (int)(Math.pow(10, length) - 0.5);
        minValue = maxValue / 10 + 1;
    }
    
    
    public NumberTripple solve() {
        var tripple = new NumberTripple();
        long product;
        
        for (int x = maxValue; x >= minValue; x--) {
            for(int y = x; y >= minValue; y--) {
                product = (long)x * y;
                if (product < tripple.product) break;
                if (checkSymmetry4(product)) {
                    tripple = new NumberTripple(product, x, y);
                    break;
                }
            }
        }
        return tripple;
    }
    
    private boolean checkSymmetry1(long value) {
        char[] number = Long.toString(value).toCharArray();
        
        for (int i = 0; i < number.length / 2; i++) {
            if (number[i] != number[number.length - 1 - i]) return false;
        }
        return true;
    }
    
    private boolean checkSymmetry2(long value) {
        final int[] number = new int[length * 2];
        int len = 0;
        while (value > 0) {
            number[len++] = (int)(value % 10);
            value /= 10;
        }
        for (int i = 0; i < len / 2; i++) {
            if (number[i] != number[len - 1 - i]) return false;
        }
        return true;
    }
    
    private boolean checkSymmetry3(final long value) {
        long copy = value;
        long eulav = 0;
        
        while(copy > 0) {
            eulav *= 10;
            eulav += copy % 10;
            copy /= 10;
        }
        return value == eulav;
    }
    
    private boolean checkSymmetry4(long value) {
        if (value < 10) return true;
        
        int eulav = 0;
        for (int i = 0; i < length; i++) {
            eulav *= 10;
            eulav += value % 10;
            value /= 10;
        }
        return value == eulav;
    }
    
    private static void printValues(int length, NumberTripple values) {
        System.out.println("Length = "+ length + ": "
                    + values.factorA +" * "
                    + values.factorB +" = "
                    + values.product);
    }
    
    public static void main(String[] args) {
        for (int i = 1; i <= MAX_LENGTH; i++) {
            printValues(i, new TestOmania(i).solve());
            printValues(i, new OtherTestOmania(i).solve());
            System.out.println();
        }
    }
}

hier können vier verschiedene checkSymmetry-Methoden durchprobiert werden. Die ersten beiden sind gleich schnell, aber auch die langsamsten.
Die dritte benötigt schon 25% weniger Zeit, die vierte spart (durch Halbierung der benötigten Anzahl an Divisionen) insgesamt 55%. Aber eben alles Peanuts im Vergleich zur folgenden Klasse.

hier beginnt der Spoilerbereich

public class OtherTestOmania {
    
    private final int length, maxValue, minValue;
    
    
    public OtherTestOmania(int l) {
        length = l;
        maxValue = (int)(Math.pow(10, length) - 0.5);
        minValue = maxValue / 10 + 1;
    }
    
    
    public NumberTripple solve() {
        for (int i = maxValue; i >= minValue; i--) {
            long product = buildPalindrome(i);
            
            for (int x = maxValue; x >= minValue; x--) {
                long y = product / x;
                if (y > x) break;
                if (y >= minValue && x * y == product)
                    return new NumberTripple(product, x, (int)y);
            }
        }
        return new NumberTripple();
    }
    
    private long buildPalindrome(int leftPart) {
        if (leftPart < 10) return (long)leftPart;
        
        long palindrome = (long)leftPart;
        
        while (leftPart > 0) {
            palindrome *= 10;
            palindrome += leftPart % 10;
            leftPart /= 10;
        }
        return palindrome;
    }
}

kleine Hilfsklasse

package homebrew.testomania;

public class NumberTripple {
    public final long product;
    public final int factorA, factorB;

    public NumberTripple(long p, int a, int b) {
        product = p;
        factorA = a;
        factorB = b;
    }

    public NumberTripple() {
        this(0, 0, 0);
    }
}

für mich wars interessant ...

 

[MarvinsDepression]

Seh gerade. Die Konsolenausgabe wollte ich auch rein nehmen.

-------------------< homebrew.testomania:testOmania >-------------------
Building testOmania 1.0-SNAPSHOT
--------------------------------[ jar ]---------------------------------

--- exec-maven-plugin:3.0.0:exec (default-cli) @ testOmania ---
Length = 1: 3 * 3 = 9
Length = 1: 9 * 1 = 9

Length = 2: 99 * 91 = 9009
Length = 2: 99 * 91 = 9009

Length = 3: 993 * 913 = 906609
Length = 3: 993 * 913 = 906609

Length = 4: 9999 * 9901 = 99000099
Length = 4: 9999 * 9901 = 99000099

Length = 5: 99979 * 99681 = 9966006699
Length = 5: 99979 * 99681 = 9966006699

Length = 6: 999999 * 999001 = 999000000999
Length = 6: 999999 * 999001 = 999000000999

Length = 7: 9998017 * 9997647 = 99956644665999
Length = 7: 9998017 * 9997647 = 99956644665999

Length = 8: 99999999 * 99990001 = 9999000000009999
Length = 8: 99999999 * 99990001 = 9999000000009999

Length = 9: 999980347 * 999920317 = 999900665566009999
Length = 9: 999980347 * 999920317 = 999900665566009999

------------------------------------------------------------------------
BUILD SUCCESS
------------------------------------------------------------------------
Total time:  06:17 min
Finished at: 2022-05-24T23:11:48+02:00
------------------------------------------------------------------------

Mein PC hat jetzt auch schon ein paar Jahre... Ist ein i5 4. Gen. Hat mal jemand einen Zeitvergleich mit ner halbwegs aktuellen CPU?

 

[DrPils]

Mein PC hat jetzt auch schon ein paar Jahre... Ist ein i5 4. Gen. Hat mal jemand einen Zeitvergleich mit ner halbwegs aktuellen CPU?

Wie machst du die Zeitmessung? Habe mal deinen letzten Algorithmus durchlaufen lassen. Die 8-Stelligen sind sofort da, fuer die 9 Stelligen werden ca 5s gebraucht. i7 12.Gen

 

[MarvinsDepression]

Stimmt, war nicht dabei.

    private static void printValues(long time, int length, NumberTripple values) {
        time = System.currentTimeMillis() - time;
        System.out.println(time +"ms  ,"
                +"Length = "+ length + ": "
                + values.factorA +" * "
                + values.factorB +" = "
                + values.product);
    }
    
    public static void main(String[] args) {
        long time;
        for (int i = 1; i <= MAX_LENGTH; i++) {
            time = System.currentTimeMillis();
            printValues(time, i, new TestOmania(i).solve());
            time = System.currentTimeMillis();
            printValues(time, i, new OtherTestOmania(i).solve());
            System.out.println();
        }
    }

Die 2. Methode lediglich 25s benötigt.

 

[Arrive5784]

Also, du musst schon genau angeben, welche zwei Methoden du genau vergleichen möchtest.

und hier stimmt was nicht:

time = System.currentTimeMillis();
printValues(time, i, new TestOmania(i).solve());
time = System.currentTimeMillis();

die erste Zuweisung an time ist sinnlos, weil sie von der zweiten überschrieben wird...

Eine Zeitmessung geht für Gewöhnlich so:

long t0 = System...;
methodCall();
long t1 = System...;
sout (t1 - t0);

 

[KonradN]

die erste Zuweisung an time ist sinnlos, weil sie von der zweiten überschrieben wird...

Deine Aussage ist schlicht falsch, denn die Variable time wird ja als Parameter übergeben und da genutzt. Und wenn Du in die Methode geschaut hättest, hättest Du dort die Berechnung gesehen.

 

[Arrive5784]

Die Aussage ist nicht falsch, sie ist aber vielleicht etwas zu streng formuliert: Für Gewöhnlich macht man die Zeitmessung anders, also nicht so. Demzufolge ist das

time = System.currentTimeMillis();
somethingWith(time );
time = System.currentTimeMillis();

schlicht falsch.

Ich befürchte fast, dass, wenn ich die Zeitmessung nochmal mit meiner Methode aus #14 machen würde, das Ergebnis umgekehrt wäre. Das soll natürlich nicht heißen, dass der Top-Down-Ansatz in irgendeiner Weise falsch wäre - sondern nur, dass hier kein korrektes Benchmarking gemacht wurde.

 

[KonradN]

Der Code ist aber nicht falsch, nur weil es nicht so ist, wie Du ihn erwarten würdest. Und entweder Du bist überzeugt worden, dass es zu streng formuliert wurde (Erste Aussage) - dann sollte man diese aber nicht erneut genau so wiederholen - oder man formuliert besser.

So bleibt es bei meiner Aussage: Deine Aussage ist schlicht und einfach falsch. Der Code macht genau das, was Dein in #26 skizzierter Code auch macht. Und ja - das ist kein korrektes Benchmarking - genau so wie eben auch Dein skizziertes Vorgehen kein korrektes Benchmarking ist.

 

[Arrive5784]

Du musst schon genau lesen. Ich sprach in #26 nur von der Zeitmessung, nicht von einem vollumfänglichen Benchmarking. Aber #26 geht schon eher in die richtige Richtung eines akzeptablen Benchmarkings.

 

[Arrive5784]

Aber ich teste das jetzt mal mit https://www.baeldung.com/java-microbenchmark-harness , und melde mich gleich nochmal.

 

[KonradN]

Kann es sein, dass Du den Code, den du kritisierst, nicht verstanden hast? Sonst hättest Du ja gesehen, dass der Code streng genommen nichts anderes macht als Du skizziert hast. Nur eben ist die zweite Zeitmessung in die Methode gezogen worden und der Aufruf der zu testenden Methode findet sich in dem Parameter.

Das mag Dir vom Aufbau her nicht gefallen (mir auch nicht), aber das macht es eben nicht "falsch".

 

[Arrive5784]

@MarvinsDepression Ich will nix sagen, aber bei deiner Methode funktioniert gar nichts... Das ist mir beim Test schreiben aufgefallen:

    public int[] findTopDown(int digits) {
        int[] r = {-1, -1};
        int a = (int) (Math.pow(10, digits) - 0.5);
        int b = a / 10 + 1;

        for (int i = a; i >= b; i--) {
            long product = buildPalindrome(i);

            for (int x = a; x >= b; x--) {
                int y = (int) (product / x);
                // if (y > x) break;
                if (y >= a && (long) x * y == product) {
                    r[0] = x;
                    r[1] = y;
                    return r;
                }
            }
        }
        return r;
    }

    private long buildPalindrome(int leftPart) {
        if (leftPart < 10) return leftPart;

        long palindrome = leftPart;

        while (leftPart > 0) {
            palindrome *= 10;
            palindrome += leftPart % 10;
            leftPart /= 10;
        }
        return palindrome;
    }

Hab nur das if (y > x) break; aus kommentiert.

Könntest du das bitte nochmal ändern, damit man ein Benchmarking machen kann...

 

[Arrive5784]

Ein Benchmark, so er funktionieren würde, würde dann in etwa so aussehen:

package PalindromeProduct;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.infra.Blackhole;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import org.openjdk.jmh.runner.options.TimeValue;

import java.math.BigInteger;
import java.util.Arrays;

@State(Scope.Benchmark)
public class BenchmarkPalindromeProduct {
    @Param({"1", "2", "3", "4", "5"})
    public int arg;

    @Benchmark
    public void findBottomUp(Blackhole blackhole) {
        blackhole.consume(findBottomUp(arg));
    }

    @Benchmark
    public void findTopDown(Blackhole blackhole) {
        blackhole.consume(findTopDown(arg));
    }

    public void checkResults() {
        for (int i = 1; i < 5; i++) {
            System.out.println(i + " " + Arrays.equals(findBottomUp(i), findTopDown(i)));
        }
    }

    public int[] findBottomUp(int digits) {
        BigInteger fence = BigInteger.ZERO;
        int[] r = {-1, -1};
        int a = (int) Math.pow(10, digits) - 1;

        for (int i = a; i > 0; i--) {
            BigInteger b = BigInteger.valueOf(i);
            if (b.multiply(b).compareTo(fence) <= 0) {
                break;
            }
            for (int j = i; j > 0; j--) {
                BigInteger p = b.multiply(BigInteger.valueOf(j));
                if (p.compareTo(fence) > 0) {
                    if (palindrome(p)) {
                        fence = p;
                        r[0] = i;
                        r[1] = j;
                    }
                } else {
                    break;
                }
            }
        }
        return r;
    }

    public boolean palindrome(BigInteger p) {
        String s = String.valueOf(p);
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }

    public int[] findTopDown(int digits) {
        int[] r = {-1, -1};
        int a = (int) (Math.pow(10, digits) - 0.5);
        int b = a / 10 + 1;

        for (int i = a; i >= b; i--) {
            long product = buildPalindrome(i);

            for (int x = a; x >= b; x--) {
                int y = (int) (product / x);
                // if (y > x) break;
                if (y >= a && (long) x * y == product) {
                    r[0] = x;
                    r[1] = y;
                    return r;
                }
            }
        }
        return r;
    }

    private long buildPalindrome(int leftPart) {
        if (leftPart < 10) return leftPart;

        long palindrome = leftPart;

        while (leftPart > 0) {
            palindrome *= 10;
            palindrome += leftPart % 10;
            leftPart /= 10;
        }
        return palindrome;
    }

    public static void main(String[] args) throws Exception {
        new BenchmarkPalindromeProduct().checkResults();

        Options opt = new OptionsBuilder()
                .include(BenchmarkPalindromeProduct.class.getSimpleName())
                .forks(1)
                .warmupIterations(1)
                .measurementIterations(1)
                .measurementTime(TimeValue.seconds(10))
                .build();

        new Runner(opt).run();
    }
}

Wobei ich dann fairerweise vorher noch BigInteger entfernen muss.

 

[M.L.]

Die Rätsel von Projekt Euler wollen (idR) mit möglichst wenig und vor allem geschickten Additions- und/oder Multiplikationsschritten bearbeitet werden. Und man kann Zusammenhänge nutzen um möglichst viele Rechenschritte am besten gar nicht erst ausführen zu müssen.

Das kleinste Ergebnis wäre 10.000 (100 * 100), das grösste 998.001 (999 * 999). Das Ergebnis hat -zwecks Palindrom Eigenschaft- die bereits genannte Struktur abccba (mit a>=b > c). Da 998.899 entfällt (grösser als erlaubt) käme 997.799 als (vrmtl. erste) zu prüfende Zahl für die passende Multiplikation infrage.

 

[Arrive5784]

@M.L. Das Problem ist an sich, dass @MarvinsDepression einen Algorithmus getestet hat, der überhaupt nicht funktioniert. Und das ist so Murks, dass ich auch nicht weiß, wie der zu verbessern wäre...

Zu Projekt Euler kann ich nicht viel sagen, bin ja kein Mathematiker. =)

 

[temi]

Das Problem ist an sich

steht ganz oben

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

 

[Arrive5784]

steht ganz oben

siehe

Zu Projekt Euler kann ich nicht viel sagen, bin ja kein Mathematiker. =)

 

[DrPils]

@MarvinsDepression Ich will nix sagen, aber bei deiner Methode funktioniert gar nichts... Das ist mir beim Test schreiben aufgefallen:

Keine Ahnung was du da geändert hast, aber ich hatte den Code 1:1 rauskopiert und er funktioniert Wunderbar. Wieso änderst du überhaupt seinen Code wenn du ihn testen willst?

 

[Arrive5784]

@httpdigest Liegt's an mir - oder funktioniert auch deine Variante nicht?

package PalindromeProduct;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.infra.Blackhole;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import org.openjdk.jmh.runner.options.TimeValue;

import java.math.BigInteger;
import java.util.Arrays;

@State(Scope.Benchmark)
public class BenchmarkPalindromeProduct {
    @Param({"2", "3", "4", "5"})
    public int arg;

    @Benchmark
    public void findBottomUp(Blackhole blackhole) {
        blackhole.consume(arriveVariant(arg));
    }

    @Benchmark
    public void findTopDown(Blackhole blackhole) {
        blackhole.consume(httpdigestVariant(arg));
    }

    public void checkResults() {
        for (int i = 2; i <= 5; i++) {
            int[] a = arriveVariant(i);
            int[] b = httpdigestVariant(i);
            System.out.println(i + " " + Arrays.toString(a) + " " + Arrays.toString(b) + " " + Arrays.equals(a, b));
            System.out.println(b[0] * b[1]);
        }
    }

    public int[] arriveVariant(int digits) {
        BigInteger fence = BigInteger.ZERO;
        int[] r = {-1, -1};
        int a = (int) Math.pow(10, digits) - 1;

        for (int i = a; i > 0; i--) {
            BigInteger b = BigInteger.valueOf(i);
            if (b.multiply(b).compareTo(fence) <= 0) {
                break;
            }
            for (int j = i; j > 0; j--) {
                BigInteger p = b.multiply(BigInteger.valueOf(j));
                if (p.compareTo(fence) > 0) {
                    if (palindrome(p)) {
                        fence = p;
                        r[0] = i;
                        r[1] = j;
                    }
                } else {
                    break;
                }
            }
        }
        return r;
    }

    public boolean palindrome(BigInteger p) {
        String s = String.valueOf(p);
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }


    public int[] httpdigestVariant(int digits) {
        int upperBound = (int) Math.pow(10, digits) - 1;
        for (int v = upperBound; v > 0; v--) {
            int p = buildPalindrome(v, upperBound + 1);
            int d = findFirstDivisor(p, v, upperBound);
            if (d != -1) {
                return new int[]{d, v};
            }
        }
        return new int[]{-1, -1};
    }

    public int reverseInt(int v) {
        int r, res = 0;
        while (v > 0) {
            r = v % 10;
            res = res * 10 + r;
            v /= 10;
        }
        return res;
    }

    public int buildPalindrome(int num, int upperBound) {
        return num * upperBound + reverseInt(num);
    }

    public int findFirstDivisor(int palindrome, int v, int upperBound) {
        for (int i = upperBound; i >= (upperBound / 10 + 1) && i > v; i--)
            if (palindrome % i == 0)
                return i;
        return -1;
    }


    public static void main(String[] args) throws Exception {
        new BenchmarkPalindromeProduct().checkResults();
        System.exit(0);

        Options opt = new OptionsBuilder()
                .include(BenchmarkPalindromeProduct.class.getSimpleName())
                .forks(1)
                .warmupIterations(1)
                .measurementIterations(1)
                .measurementTime(TimeValue.seconds(10))
                .build();

        new Runner(opt).run();
    }
}

(Wollte diese nur generisch machen...)

 

[Arrive5784]

Keine Ahnung was du da geändert hast, aber ich hatte den Code 1:1 rauskopiert und er funktioniert Wunderbar. Wieso änderst du überhaupt seinen Code wenn du ihn testen willst?

Ich glaub, du hast zu viel Bier getrunken, wenn das bei dir funktionieren soll. =)

 

[DrPils]

Wie beeinflusst bitte mein Bier Konsum die jvm?

 

[httpdigest]

@httpdigest Liegt's an mir - oder funktioniert auch deine Variante nicht?
(Wollte diese nur generisch machen...)

Liegt an dir. Du lieferst in meinem von dir veränderten Code die zwei Werte:

return new int[]{d, v};

zurück und glaubst, dass das die beiden Faktoren sind. Sind sie aber nicht. `v` ist nicht ein Faktor des Palindroms, sondern die eine "Seite" des Palindroms, also bei 9009 wäre v = 90. Die Faktoren sind aber d = 99 und p/d = 91. p/d rechne ich aber niemals aus, weil es eben von der Aufgabenstellung überhaupt nicht gefordert war. Die Aufgabenstellung verlangte, dass man das Palindrom ermittelt. Nicht, dass man die Faktoren des Palindroms ermittelt/zurückgibt.

 

[Arrive5784]

interessant, danke für die Richtigstellung... hier nun der Vergleich:

package PalindromeProduct;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.infra.Blackhole;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import org.openjdk.jmh.runner.options.TimeValue;

import java.util.Arrays;

@State(Scope.Benchmark)
public class BenchmarkPalindromeProduct {
    @Param({"2", "3", "4", "5", "6", "7", "8"})
    public int arg;

    @Benchmark
    public void findBottomUp(Blackhole blackhole) {
        blackhole.consume(arriveVariant(arg));
    }

    @Benchmark
    public void findTopDown(Blackhole blackhole) {
        blackhole.consume(httpdigestVariant(arg));
    }

    public void checkResults() {
        for (int i = 2; i <= 8; i++) {
            int[] a = arriveVariant(i);
            int[] b = httpdigestVariant(i);
            System.out.println(i + " " + Arrays.toString(a) + " " + Arrays.toString(b) + " " + Arrays.equals(a, b));
            System.out.println((long) b[0] * b[1]);
        }
    }

    public int[] arriveVariant(int digits) {
        long fence = 0;
        int[] r = {-1, -1};
        int a = (int) Math.pow(10, digits) - 1;

        for (int i = a; i > 0; i--) {
            if ((long) i * i <= fence) {
                break;
            }
            for (int j = i; j > 0; j--) {
                long p = (long) i * j;
                if (p > fence) {
                    if (palindrome(p)) {
                        fence = p;
                        r[0] = i;
                        r[1] = j;
                    }
                } else {
                    break;
                }
            }
        }

        return r;
    }

    public boolean palindrome(long p) {
        String s = String.valueOf(p);
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }

    public int[] httpdigestVariant(int digits) {
        int upperBound = (int) Math.pow(10, digits) - 1;
        for (int v = upperBound; v > 0; v--) {
            long p = buildPalindrome(v, upperBound + 1);
            int d = findFirstDivisor(p, v, upperBound);
            if (d != -1) {
                return new int[]{d, (int) (p / d)};
            }
        }
        return new int[]{-1, -1};
    }

    public int reverseInt(int v) {
        int r, res = 0;
        while (v > 0) {
            r = v % 10;
            res = res * 10 + r;
            v /= 10;
        }
        return res;
    }

    public long buildPalindrome(int num, int upperBound) {
        return (long) num * upperBound + reverseInt(num);
    }

    public int findFirstDivisor(long palindrome, int v, int upperBound) {
        for (int i = upperBound; i >= (upperBound / 10 + 1) && i > v; i--)
            if (palindrome % i == 0)
                return i;
        return -1;
    }

    public static void main(String[] args) throws Exception {
        new BenchmarkPalindromeProduct().checkResults();

        Options opt = new OptionsBuilder()
                .include(BenchmarkPalindromeProduct.class.getSimpleName())
                .forks(1)
                .warmupIterations(1)
                .measurementIterations(1)
                .measurementTime(TimeValue.seconds(10))
                .build();

        new Runner(opt).run();
    }
}

Benchmark                                                  (arg)   Mode  Cnt        Score   Error  Units
PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp      2  thrpt       1887737,694          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp      3  thrpt          6442,840          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp      4  thrpt         13794,175          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp      5  thrpt            28,274          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp      6  thrpt            90,531          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp      7  thrpt             0,097          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp      8  thrpt             0,711          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findTopDown       2  thrpt       3128905,902          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findTopDown       3  thrpt         37814,461          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findTopDown       4  thrpt         30451,355          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findTopDown       5  thrpt          2376,012          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findTopDown       6  thrpt           244,949          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findTopDown       7  thrpt            12,071          ops/s
PalindromeProduct.BenchmarkPalindromeProduct.findTopDown       8  thrpt             1,924          ops/s

Je nach Input variieren die Zeiten natürlich stark. Aber für digits=7 ist deine Variante ca. 120mal schneller als mein Ansatz. Dem ist wohl nichts hinzuzufügen.

 

[Arrive5784]

Wie beeinflusst bitte mein Bier Konsum die jvm?

Naja, weil es sehr schlecht programmiert war, nicht funktionierte und du das obendrein offensichtlich nicht erkannt hast?

 

[DrPils]

Naja, weil es sehr schlecht programmiert war, nicht funktionierte und du das obendrein offensichtlich nicht erkannt hasa

Wieso war sein Code schlecht programmiert?
War aufjedenfall besser als deine Lösung die du ja von mir kopiert hast, äh sorry zeitversetzt gepostet hast. Funktionieren tut er ja auch.
Sein Code läuft bei ihm, ich kopiere sein Code, der Code läuft. Du kopierst ihn, änderst paar Sachen, er funktioniert nichtmehr....
Wo liegt der Fehler?

 

[Arrive5784]

ja schon gut, ich will mich nicht weiter streiten

 

[Arrive5784]

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Ich finde, man kann das so oder so lesen, also, dass sowohl die numbers/factors gesucht sind als auch das palindrome. Ohne die Faktoren kann ich doch gar nicht verifizieren, ob das ein gültiges Palindrom ist...

@httpdigest Wo kommen die Zeitunterschiede her? Wenn ich das richtig sehe, ist deins wie meins in O(n²). Dein Ansatz ist aber durchschnittlich doppelt so schnell.

arg	Mode	Score A	Score B	A/B
6	avgt	0,011	0,004	2,75
7	avgt	10,768	0,089	120,9
8	avgt	1,424	0,527	2,7

 

[MarvinsDepression]

Wenn ich mich nochmal dazu schalten darf (als Murkser, der Code schreibt, welcher opensightly nur auf dem eigenen Rechner funktioniert ):
Von Benchmarks hab ich tatsächlich keine Ahnung. Was sagt so ein Score aus. Sekunden/Durchlauf? Oder ganz was anderes?

 

[KonradN]

Also wenn Du Dich für Benchmarks interessierst, dann kannst Du ein paar Links dazu betrachten:

Microbenchmarking with Java | Baeldung

Learn about JMH, the Java Microbenchmark Harness.

www.baeldung.com

https://jenkov.com/tutorials/java-performance/jmh.html

GitHub - Michael-Frank/jmh-Introduction: JMH introduction and collection of various jmh benchmarks

JMH introduction and collection of various jmh benchmarks - Michael-Frank/jmh-Introduction

github.com

Java JMH Benchmark Tutorial - Mkyong.com

- Java JMH Benchmark Tutorial

mkyong.com

Aber das ist ein Thema, ohne das man auch sehr gut klar kommt (um es mal so einfach auszudrücken).

Zumindest ich würde andere Themen als deutlich wichtiger ansehen, wie z.B. Clean Code, OO Design und so. Das ist um ein vielfaches wichtiger (in meinen Augen). Und bezüglich diesen Benchmarks würde ich einfach das Thema Optimizations zitieren, zu dem schlicht gesagt wird: Don't do it. (Und für Experten, die wissen, was sie tun: Don't do it, yet)