Methoden Zahlenpalindrom laufzeitoptimiert prüfen

T

TLS

Gast
Hallo alle zusammen,

ich arbeite gerade an einer Methode, die eine gegebene long auf ein Palindrom prüfen soll.

Nun habe ich bereits sehr viele Methoden bei google gefunden, die mir allerdings alle zu langsam sind und die Laufzeit meines Programms um 90% verlängern.

Ich hätte gerne eine schnelle überprüfung, wie es bereits in Scala möglich war:
Code:
final def isPalindrome =
    if (wrapped < 10L) true
    else if (wrapped % 10L == 0L) false
    else check(wrapped, 0L)

Ich habe bereits mehrere Möglichkkeiten in Java probiert, z.B.
Code:
        String str = String.valueOf(pal);
        StringBuffer buf = new StringBuffer(str);
        return str.equals(buf.reverse().toString());
Code:
        long palTmp = pal;
        long palRev = 0;
        while(palTmp > 0)
        {
            long temp = palTmp % 10;
            palRev = palRev * 10 + temp;
            palTmp = palTmp/10;
        }
        return pal == palRev;

Keine der beiden Lösungen war auch nur annähernd so schnell wie die Scala referenz.
Einige andere Vorschläge poste ich hier jetzt nicht, da die Laufzeit mehr als miserabel war.

Könnt ihr mir bitte helfen, die Laufzeit zu optimieren?

Grüße,
TLS
 
T

TLS

Gast
Sorry, habe die Check funktion bei Scala vergessen:

Code:
    final def check(l: Long, r: Long): Boolean = 
    if (l == r) true
    else if (l < r) false
    else {
      val rs = r * 10L + (l % 10L)
      if (l == rs) true
      else check(l / 10, rs)
    }
 
S

SlaterB

Gast
wieviel prüfst du denn, auch neben Tests in realen Umgebungen, so dass bei so einer Methode die Performance spürbar wird?

ob Scala geschlagen werden kann weiß ich nicht, aber deine beiden Java-Beispiele scheinen nicht der Scala-Variante zu entsprechen,
die quasi in der Mitte abbricht statt palRev komplett auszurechen,
schon eine direkte Übersetzung des Codes versucht? oder kannst du komplett kein Java und fragst nach den entsprechenden Befehlen?
 
Zuletzt bearbeitet von einem Moderator:
T

TLS

Gast
wieviel prüfst du denn, auch neben Tests in realen Umgebungen, so dass bei so einer Methode die Performance spürbar wird?

ob Scala geschlagen werden kann weiß ich nicht, aber deine beiden Java-Beispiele scheinen nicht der Scala-Variante zu entsprechen,
die quasi in der Mitte abbricht statt palRev komplett auszurechen,
schon eine direkte Übersetzung des Codes versucht? oder kannst du komplett kein Java und fragst nach den entsprechenden Befehlen?

Ich prüfe bis 40 stellige Zahlen und das mehrere hundert male mit dem methodenaufruf.

Ich bin leider nicht sehr versiert in Java, was Laufzeitoptimierung und gerade das handling von Zahlen betrifft.

Habe versucht mich schlau zu machen, aber habe bisher noch keine Lösung gefunden, wie auch Java nur bis zur hälfte der Zahl arbeitet.

Da ich mich mehr mit Scala auskenne, wollte ich hier mal nachfragen, ob jemand äquivalente Befehle für einen solchen algo wie in Scala kennt und mir verraten könnte ;)

MfG,
TLS
 
S

SlaterB

Gast
test1() im unteren Programm dürfte dem entsprechen,
in dem Test mit Long bis zu 18 Stellen, mehr geht nicht, gibts per Zufall zwar so gut wie keine Palindrome,
dann ist die neue Methode aber 40% schneller,

mit kleinen max, etwa die auskommentierten 1000, gibts mehr Palindrome und geringere Abweichung,
ich wollte eigentlich noch mehr testen, aber so spannend dann auch wieder nicht ;)

Java:
public class Test
{
    static int n = 10000000;
    static long[] a = new long[n];
    // static long max = 1000;
    static long max = Long.MAX_VALUE;

    public static void main(String[] args)
    {
        for (int i = 0; i < n; i++)
        {
            a[i] = (long)(Math.random() * max);
        }
        test(0);
        test(1);
        test(0);
        test(1);
    }

    static void test(int m)
    {
        long time = System.currentTimeMillis();
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            long c = a[i];
            boolean b = (m == 0 ? test0(c) : test1(c));
            if (b) count++;
        }
        System.out.println("time: " + (System.currentTimeMillis() - time) + " - " + count);
    }

    static boolean test0(long pal)
    {
        long palTmp = pal;
        long palRev = 0;
        while (palTmp > 0)
        {
            long temp = palTmp % 10;
            palRev = palRev * 10 + temp;
            palTmp = palTmp / 10;
        }
        return pal == palRev;
    }

    public static boolean test1(long pal)
    {
        if (pal < 10) return true;
        if (pal % 10 == 0) return false;
        long palTmp = pal;
        long palRev = 0;
        while (palTmp > 0)
        {
            long temp = palTmp % 10;
            palRev = palRev * 10 + temp;
            if (palTmp == palRev) return true;
            palTmp = palTmp / 10;
            if (palTmp == palRev) return true;
            if (palTmp < palRev) return false;
        }
        return false;
    }
}

inwiefern du ohne Java-Kenntnisse für so eine kleine Methode überhaupt das ganze in Java brauchst
(wo baust du das ein, wie kannst du das Rest-Java-Programm gut kontrollieren?)
ist mir schleierhaft, aber auch egal
 
Zuletzt bearbeitet von einem Moderator:
Ähnliche Java Themen
  Titel Forum Antworten Datum
8u3631984 Prüfen ob min. ein Element eines Sets in einem anderen Set enh Allgemeine Java-Themen 4
OnDemand Prüfen ob Bild defekt ist Allgemeine Java-Themen 4
N Prüfen, ob ein String 2x das selbe Zeichen hat Allgemeine Java-Themen 10
W Classpath Reflexion - Prüfen ob man auf ein Feld ändern kann Allgemeine Java-Themen 2
OnDemand Bild prüfen ob defekt Allgemeine Java-Themen 3
B Java Mail: Prüfen, ob Email hat ein Anhang oder nicht Allgemeine Java-Themen 2
Bluedaishi Prüfen ob Datei noch geöffnet ist Allgemeine Java-Themen 59
Stonie Prüfen von direkter Implementierung eines Interfaces Allgemeine Java-Themen 7
J Mit Lombok Integer Range prüfen Allgemeine Java-Themen 6
S Prüfen ob Textfile existiert Allgemeine Java-Themen 9
E Programm auf Installation prüfen Allgemeine Java-Themen 1
S Binärbaum prüfen Allgemeine Java-Themen 0
L String auf zahlenwert prüfen Allgemeine Java-Themen 13
W Datum prüfen + zweistellig Allgemeine Java-Themen 11
perlenfischer1984 Functionsparameter prüfen und eine Exception werfen !? Allgemeine Java-Themen 11
Z Java Exceptions - Auf leeres Feld prüfen Allgemeine Java-Themen 10
F Wie kann ich auf einem System prüfen, ob eine lib verfügbar ist? Allgemeine Java-Themen 2
P Prüfen ob es Variable mit Namen gibt der als String übergeben wird Allgemeine Java-Themen 7
M .jar nach Datei prüfen Allgemeine Java-Themen 2
B Existenz eines Files max 30 sec prüfen Allgemeine Java-Themen 5
B Prüfen, ob ein Element in der Liste nicht existiert Allgemeine Java-Themen 3
F Cardlayout prüfen ob schon vorhanden, keine doppelten Allgemeine Java-Themen 3
turmaline Regex gegen Regex prüfen Allgemeine Java-Themen 4
S Lambda Ausdrücke: @FunctionalInterface Instanzen auf null prüfen Allgemeine Java-Themen 9
D ArrayList index auf gültigkeit prüfen Allgemeine Java-Themen 12
C Best Practice [Arrays] Wie sinnvoll prüfen, ob Array primitive Datentypen enthält? Allgemeine Java-Themen 6
L Prüfen, ob Programm über 32bit oder 64bit Java ausgeführt wird Allgemeine Java-Themen 4
K Methoden Arrays auf true Werte prüfen Allgemeine Java-Themen 4
Y Prüfen ob ein Graph immer einen von mehren Enden erreicht Allgemeine Java-Themen 4
O Prüfen ob String eine Zahl mit maximal 2 Nachkommastellen ist Allgemeine Java-Themen 4
M datei aufruf prüfen Allgemeine Java-Themen 9
D Best Practice Prüfen ob jar nachträglich geändert wurde Allgemeine Java-Themen 2
B Dateien prüfen auf Gleichheit Allgemeine Java-Themen 5
H String auf Zahlen prüfen Allgemeine Java-Themen 4
T auf Valides Datum prüfen Allgemeine Java-Themen 12
N Java Version Prüfen lassen Allgemeine Java-Themen 11
S Variablen Prüfen ob Number vom Typ Integer, Float, Double, ... ist Allgemeine Java-Themen 2
E selber Klassen kompilieren/ prüfen Allgemeine Java-Themen 5
O Variablen Originalname einer übergebenen Variable prüfen Allgemeine Java-Themen 9
U ResourceBundles auf vollständigkeit prüfen Allgemeine Java-Themen 2
C jollyday: prüfen, ob Datum = Feiertag Allgemeine Java-Themen 8
C Prüfen ob sich ein Punkt innerhalb einer Kugel befindet (Java3D,nicht-lineare GLS) Allgemeine Java-Themen 5
M Objekt prüfen auf null ->Invocation Target Exception??? Allgemeine Java-Themen 2
E Prüfen ob Fenster mit Namen offen ist Allgemeine Java-Themen 2
M Binärbaum auf vollständigkeit prüfen Allgemeine Java-Themen 4
S Mail Adressen Syntax prüfen Allgemeine Java-Themen 22
O Text mit Wildcard gegen regulären Ausdruck prüfen Allgemeine Java-Themen 3
N List auf null prüfen Allgemeine Java-Themen 2
B generischen Typ prüfen Allgemeine Java-Themen 7
D prüfen, ob Enums bestimmte Elemente enthalten Allgemeine Java-Themen 3
N Prüfen ob Methode ausgeführt wird und diese ggf. abbrechen? Allgemeine Java-Themen 8
B Prüfen ob ein Programm gestartet wurde Allgemeine Java-Themen 23
N ArrayList nach Reihenfolge prüfen Allgemeine Java-Themen 2
C Prüfen auf Zahl und 6 stellig fehlerhaft? warum? Allgemeine Java-Themen 7
D Wie prüfen, ob ein String Teil eines Enum Types ist? Allgemeine Java-Themen 12
H Prüfen, ob doppete Werte in int-Array vorhanden sind Allgemeine Java-Themen 16
data89 Bilder mit Java prüfen - suche dringend Hilfe Allgemeine Java-Themen 8
S Prüfen auf Hex-Wert fester Länge! Allgemeine Java-Themen 5
M Prüfen, welche anderen Programme laufen Allgemeine Java-Themen 5
K Zip dateien prüfen Allgemeine Java-Themen 3
G ZIP Archiv auf Konsistenz prüfen Allgemeine Java-Themen 2
T Parameter einer Klasse auf Interface prüfen Allgemeine Java-Themen 6
L Passwort mit Regulärem Ausdruck prüfen Allgemeine Java-Themen 6
P Sound Buffer prüfen Allgemeine Java-Themen 12
B PrintService - Wie prüfen ob Drucker online ist? Allgemeine Java-Themen 2
A Textfeld prüfen, ob ein Punkt eingegeben wurde Allgemeine Java-Themen 8
flashfactor Prüfen ob bereits eine Instanz gestartet ist Allgemeine Java-Themen 2
C Prüfen, ob eine Methode eine andere überschreibt! WIE? Allgemeine Java-Themen 8
T Prüfen, ob Char ein Quantifier ist Allgemeine Java-Themen 6
N Prüfen ob Objekt in Liste enthalten ist Allgemeine Java-Themen 17
G Prüfen welche JRE-Version gebraucht wird Allgemeine Java-Themen 19
J Mit Patternmatching einen Satz prüfen Allgemeine Java-Themen 12
G Prüfen ob Ziffern einer Zahl pandigital sind? Allgemeine Java-Themen 15
M Prüfen ob Variable vorhanden / initalisiert ist Allgemeine Java-Themen 4
J Wie prüfen ob eine Datei vom OS fertig geschrieben wurde? Allgemeine Java-Themen 6
TheJavaKid Zeile auf existenz von String prüfen. Allgemeine Java-Themen 19
A Weshalb man Parameter auf Gültigkeit prüfen sollte Allgemeine Java-Themen 6
N Prüfen ob ein String in einen Integer umgewandelt werden kan Allgemeine Java-Themen 4
O String auf zahlen prüfen (java 1.3) Allgemeine Java-Themen 4
G Datei Zugriffsrechte prüfen Allgemeine Java-Themen 2
Linad Bilder auf Gleichheit prüfen Allgemeine Java-Themen 6
G ResultSet auf Inhalt prüfen? Allgemeine Java-Themen 2
H Prüfen, ob es sich um ein Integer handelt Allgemeine Java-Themen 4
C String str prüfen Allgemeine Java-Themen 3
H Prüfen ob ein String grösser als 4 Zeichen ist Allgemeine Java-Themen 3
F Prüfen, ob Windows oder UNIX Allgemeine Java-Themen 2

Ähnliche Java Themen

Neue Themen


Oben