Java Komplexitätsoptimierung String vergleich

[Master1991]

ich habe für ein Projekt den Quine-McClusky Algorithmus zur Minierung von Logikfunktionen implementiert. Nun versuche ich diesen hinsichtlich Laufzeit zu optimieren. Einen Großteil der Zeit verbringt das Programm in folgender Funktion:

public int[] differsMaxOneChar(String a, String b) {
    debug.println("Comparing " + a + " to " + b);
    int[] returnValue = {1, 0};
    boolean differs = false;
    for (int i = 0; i < a.length(); i++) {
        if (!(a.charAt(i) == b.charAt(i))) {
            if (differs) {
                returnValue[0] = 0;
                break;
            } else {
                differs = true;
                returnValue[1] = i;
            }
        }
    }
    return returnValue;
}

String a und b sind immer gleichlang und bestehen aus '0', '1' und 'X'. Die Funktion prüft ob sich zwei Strings in genau einer Position unterscheiden.

Jemand Verbesserungsvorschläge?

 

[davisx2]

Ok meine Antwort war falsch, habs falsch verstanden
Glaube da ist nichts zu verbessern.
Man kann zwar das ! im if in die Klammer reinziehen, sollte aber keine Verbesserung sein und wenn schon, dann nicht spürbar.

 

[Musicon]

Hi,

a.length() -> das gehört genau dort rein -> Schleifenkopf. Dem Rest schließe ich mich an.

Es gibt andere Algos die es um ein x-faches schneller lösen -> binär.

wenn strings verglichen werden sollen/müssen, kannst du den Quine-McClusky nicht optimieren, falls du es schafst -> Nobelpreis?

 

[mxmb]

bei einem Fund wird die Schleife erst im nächsten Durchgang verlassen. Das mit "differs" kann eigentlich weg.

edit: zu spät. wenn es nur 1 Unterschied sein darf und nicht 2 oder mehr, dann stimmt es.

 

[davisx2]

@Musicon: Das Problem mit dieser Funktion kann sein, dass er ne nach Compiler und bla diese Funktion jedes mal aufruft und damit das Array mit Größe n auch n mal durchlaufen wird (hatte schon mal das Problem, obwohl es ja eigentlich nicht passieren sollte).

Und an alle: Er braucht das "differs" wegen dem Kriterium "genau in einer Position unterscheiden", deswegen darf er nicht vorher abbrechen.
Von demher war meine Antwort falsch und ich habe sie geändert. Das mit dem Schleifenkopf kann man trotzdem mal testen (wird aber bei der kleinen Datenmenge bestimmt nicht spürbar sein).

 

[Raybeez]

Der Algorithmus enthält bloß eine Schleife und die Laufzeit steigt linear mit der länge der Wörter. Da gibt es keine Optimierungsmöglichkeit, da du bei zwei gleichen Wörter zwangsläufig die komplette Schleife durchlaufen musst. Und bei zwei ungleichen Wörtern verlässt du die Schleife schon beim zweiten Unterschied.

 

[Master1991]

Danke an alle.
Hätte ja sein können, dass es bei der geringen Anzahl an möglichen Zeichen im String eine andere Möglicheit gegeben hätte.

Vielleicht habe ich den Datentyp auch "blöd" gewählt. Wäre es mit Integern schneller?
Also als zeichen dann binär: 0 und 1 und als 'X' halt representativ eine 2?

Das X brauch ich um die einzelnen Terme zusammenzufassen:

0000 und 0001 wird zu 000X --> ist es mit Integer und 0002 schneller zu realisieren?

 

[Musicon]

kurze frage prüfst du immer nur genau 2 strings gegeneinander oder läuft das program x- mal über verschiedene strings?

quasi wie nen array/objekt welches mehrere strings beinhaltet?

 

[E-tech]

Hi, ich hab leider grade keine Zeit mich genauer damit zu beschäftigen, aber die einzige Optimierung die mir gerade einfällt besteht darin, das man vor der Schleife prüft ob der Hashwert beider Strings identisch ist. Falls ja, sind diese gleich (Java verweist dann auf das gleiche Objekt im Heap) und du brauchst die Schleife gar nicht erst betreten.

Wie Java intern den Hashwert für String berechnet müsste man dann mal prüfen um zu gucken ob die nicht auch alle Buchstaben dafür nutzen

 

[Musicon]

@ E-tech: genau darauf ist miene frage aus :=)

wenn er mehrere strings vergleicht -> hash erstellen, vergleichen, fertig...

nur befürchte ich das er immer nur genau 2 strings hat die unterschiedlich lag sein können.

 

[Master1991]

kurze frage prüfst du immer nur genau 2 strings gegeneinander oder läuft das program x- mal über verschiedene strings?

quasi wie nen array/objekt welches mehrere strings beinhaltet?

Der Algo läuft sehr sehr oft über verschiedene Strings.

Zum Beispiel werden alle "Strings" mit 1ner '1' mit allen mit 2 '1en' verglichen

0100
1000
0010
0001

mit

0011
0110
1100
1001
...

 

[max40]

ich bin der Meinung mit dem

debug.println("Comparing " + a + " to " + b);

wird er ein vielfaches mehr Zeit benötigen als für den Rest der Methode.

 

[Master1991]

ich bin der Meinung mit dem

debug.println("Comparing " + a + " to " + b);

wird er ein vielfaches mehr Zeit benötigen als für den Rest der Methode.

Ja, das weiß ich deshalb ist es nur aus debugging zwecken dort Per Flag abschaltbar.

 

[max40]

was bedeutet per flag? ich sehe kein schalter.
per schalter müsste es ungefähr so aussehen:

 if(flag) debug.println("Comparing " + a + " to " + b);

 

[Master1991]

public void println(String str){
         if(active){
            System.out.println(str);
        }
    }

Teil meiner Debugger Klasse. Wie du siehst wird das Flag dort geprüft.

 

[Musicon]

dann schalte vor die buchstabenprüfung, eine Funktion die dir den haswert beider strings berechnet die du vergleichen kannst, falls der hash identisch ist kannst du dir schonmla 1 run sparen.

 

[Master1991]

dann schalte vor die buchstabenprüfung, eine Funktion die dir den haswert beider strings berechnet die du vergleichen kannst, falls der hash identisch ist kannst du dir schonmla 1 run sparen.

Ich danke dir und E-tech für eure Idee. Die Strings können jedoch niemals identisch sein, bringt also nichts.
Ich nehme die Funktion jetzt als nicht weiter optimierbar an

Ich danke euch allen für das Gedankengut.

 

[max40]

public void println(String str){
         if(active){
            System.out.println(str);
        }
    }

Teil meiner Debugger Klasse. Wie du siehst wird das Flag dort geprüft.

klasse. Damit hast du schonmal eine Bremse, weil er die Strings ("Comparing " + a + " to " + b) erstmal zusammenbaut ohne das er sie benötigt. Damit braucht die Methode min. 4 mal länger als nötig in meinem Test.

 

[HorstSch87]

Du kannst die Strings gleichzeitig von Links und Rechts prüfen, damit brauchst du dann zumindestens nur noch halb so viele Schleifendurchläufe im Worst Case. An der generellen Komplexitätsklasse ändert das aber nichts.

 

[Master1991]

klasse. Damit hast du schonmal eine Bremse, weil er die Strings ("Comparing " + a + " to " + b) erstmal zusammenbaut ohne das er sie benötigt. Damit braucht die Methode min. 4 mal länger als nötig in meinem Test.

Okay, das hilft dann tatsächlich enorm. Danke für die Info, das wusste ich nicht. Wird auskommentiert ist nun eh unnötig.