Java Komplexitätsoptimierung String vergleich

Raybeez · 11. Oktober 2017

Musicon schrieb:
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.

Das klingt nach einer Verschlechterung der Performance.

Wenn die Strings lang sind und gleiche Strings nicht zu selten auftreten könnte man alle Strings hashen (außerhalb der Compare-Funktion), den Hashwert speichern (was aber zusätzlichen Speicherplatz benötigt) und dann in der Compare-Funktion erstmal den Hashwert vergleichen.
Aber das hashen kostet eben einiges, während der Hash-Vergleich selber recht günstig ist.

max40 · 11. Oktober 2017

wofür ist das int[] gut?
ggf. durch ein int ersetzen. sollte dann nochmal ein wenig schneller sein.

Code:

    public static int differsMaxOneChar(String a, String b) {
    	int merk = 0;
        for (int i = 0; i < a.length(); i++) {
            if (!(a.charAt(i) == b.charAt(i))) {
                merk++;
            	if (merk > 1){
                    break;
                } 
            }
        }
        return merk;
    }

Master1991 · 11. Oktober 2017

max40 schrieb:
wofür ist das int[] gut?
ggf. durch ein int ersetzen. sollte dann nochmal ein wenig schneller sein.

Ich brauche einmal als Rückgabe ein "boolean" und einmal den Index wo der Fund war:

Code:

int[] result = differsMaxOneChar(gsA.getBinaryString(), gsB.getBinaryString());
    if (result[0] == 1) {
        creating = true;
        if (newColumnFlag) {
            newColumnFlag = false;
            debug.println("Created new Column");
            columnData.add(new ArrayList<>());
        }
        if (newGroupFlag) {
            newGroupFlag = false;
            debug.println("Created new Group");
            columnData.get(currentColumn + 1).add(new TreeSet<>());
            currentTargetGroup++;
        }
        gsA.setUsed(true);
        gsB.setUsed(true);
        StringBuilder tempString = new StringBuilder(gsA.getBinaryString());
        tempString.setCharAt(result[1], 'X');
        GroupSet gs = createGroupSet(gsA.getIndex(), gsB.getIndex(), tempString);
        columnData.get(currentColumn + 1).get(currentTargetGroup - 1).add(gs);

Das sieht wohl jetzt ohne zusammenhang etwas wirr aus. Aber ich brauche halt die Daten zum weiterverarbeiten

Darlis · 11. Oktober 2017

Nächster Ansatz mit einem int:

Code:

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

Wenn ich jetzt keinen Denkfehler gemacht habe, wäre dann
-1 keine Differenz,
>=0 eine Differenz mit Index
-2 mehr als eine Differenz.

Killkrog · 11. Oktober 2017

Du sagtest ja bereits, dass die Strings alle die selbe Länge haben.
Wie lang sind sie denn? Eventuell kann man mit einer anderen Datenstruktur ein wenig mehr Geschwindigkeit rausholen.
Außerdem: Sind die Strings, die verglichen werden, lang oder kurzlebig?

asdfman · 11. Oktober 2017

Sry falls blöde Frage, habe keine Ahnung von Java. Aber ist x.length() eine Konstante oder eine Funktion? Im letzteren Fall wäre es vielleicht sinnvoll, das einmal in eine Konstante zu schieben und die dann zum Iterieren zu benutzen?

Darlis · 11. Oktober 2017

length() ist eine Funktion, dahinter steckt aber quasi eine Konstante weil Strings in Java unveränderlich sind. Bin mir ziemlich sicher, dass der Compiler das schon optimiert.

Master1991 · 11. Oktober 2017

Killkrog schrieb:
Du sagtest ja bereits, dass die Strings alle die selbe Länge haben.
Wie lang sind sie denn? Eventuell kann man mit einer anderen Datenstruktur ein wenig mehr Geschwindigkeit rausholen.
Außerdem: Sind die Strings, die verglichen werden, lang oder kurzlebig?

Das kommt auf die Eingabe an (Anzahl Bits). In Normalfall aber zwischen 4-15 wobei eher 4 als 15 da der Algorithmus im Bereich n^3 arbeitet, 15 ist da schon schmerzhaft.

Die Strings sind alle in eigenen Objekten gespeichert. Wenn ein Hit beim compare kommt wird ein neues Objekt erstellt mit dem neuen String. Das heißt alle Strings bzw. die Objekte leben bis zum Ende des Algorithmus.

wiztm · 11. Oktober 2017

Zwei Dinge möchte ich anmerken.
Du könntest die beiden Aufrufe von charAt(i) wegoptimiere. Die charAt(i) Methode führt zwei Prüfungen durch und addiert zwei Integer wenn ich richtig informiert bin.
Würdest du beide Strings als char Array übergeben könntest du durch direkte Zugriffe auf das Array pro Loop also 4 Prüfungen und zwei Additionen sparen.
Natürlich fraglich ob man das wirklich spüren würde. Kommt vielleicht auf die Datenmenge an.

Master1991 schrieb:
Wird auskommentiert ist nun eh unnötig.

Den debug Aufruf auszukommentieren ist ohne Frage die schnellste Lösung.
Aber vielleicht kann ich eine Möglichkeit vorschlagen für die Zukunft wo eine optionale Ausgabe erwünscht ist:

Code:

	public void debug(Supplier<String> stringSupplier) {
	    if (active) {
	        System.out.println(stringSupplier.get());
	    }
	}

aufgerufen wird es durch

Code:

		debug(() -> "Comparing " + a + " to " + b);

Nun wird der String erst zusammengesetzt wenn das Flag erfolgreich verprobt wurde.

Master1991 · 12. Oktober 2017

wiztm schrieb:
Würdest du beide Strings als char Array übergeben könntest du durch direkte Zugriffe auf das Array pro Loop also 4 Prüfungen und zwei Additionen sparen.
Natürlich fraglich ob man das wirklich spüren würde. Kommt vielleicht auf die Datenmenge an.

Die Datenmenge ist immens.
Worst case bei n=4 --> 488 Aufrufe
Worst case bei n=5 --> 4.750 Aufrufe
Worst case bei n=6 --> 60.474 Aufrufe
n=7 --> 931.634 Aufrufe
n=8 --> 20.181.740 Aufrufe
n=9 --> 655.239.908 Aufrufe

Also alles was es irgendwie beschleunigen könnte nehm ich gern

wiztm schrieb:
Aber vielleicht kann ich eine Möglichkeit vorschlagen für die Zukunft wo eine optionale Ausgabe erwünscht ist:

Code:

debug(() -> "Comparing " + a + " to " + b);

Nun wird der String erst zusammengesetzt wenn das Flag erfolgreich verprobt wurde.

Danke. Von der Klasse habe ich noch nie gehört. Werde ich sicherlich nutzen

Killkrog · 12. Oktober 2017

Hallo OP!

Da hast du dir aber ein schönes Problemchen überlegt, hat mir einfach keine Ruhe gelassen

Es ist schon spät/früh, daher führe ich jetzt nichts mehr großartig aus, sondern lasse den Code für sich sprechen.

Ah, doch noch etwas vorweg, zumindest auf meinem Rechner sind die Zeiten für diese Testumgebung wie folgt:

Meine Variante: 1s 089ms 768μs 893ns
Deine Variante: 31s 356ms 687μs 058ns

Hier und da sind ein paar meiner eigenen Bibliotheken verwendet worden, die musst du dir dann halt einfach wegdenken. Machen aber nix wichtiges.

ExampeStructure.java

Code:

package com.killkrog.string_compare;

public class ExampleStructure {

    // ===================================================================
    // {[> Attributes
    // ==============
    private int b0, b1, b2;
    private int length;



    // ===================================================================
    // {[> Initializers and Constructors
    // =================================
    public ExampleStructure(String s) {

        length = s.length();
        int tmp;

        for (int i = 0; i < length; i++) {

            tmp = 1 << (length - i - 1);

            if (s.substring(i, i + 1).equals("0")) {
                b0 |= tmp;
            } else if (s.substring(i, i + 1).equals("1")) {
                b1 |= tmp;
            } else if (s.substring(i, i + 1).equals("2")) {
                b2 |= tmp;
            }
        }
    }



    // ===================================================================
    // {[> Public Methods
    // ==================
    public int[] compare(ExampleStructure o) {

        int[] returnValue = {1, 0};

        int xor0 = b0 ^ o.b0;
        int xor1 = b1 ^ o.b1;
        int xor2 = b2 ^ o.b2;

        if (Integer.bitCount(xor0) > 1) {
            returnValue[0] = 0;
        } else if (Integer.bitCount(xor1) > 1) {
            returnValue[0] = 0;
        } else if (Integer.bitCount(xor2) > 1) {
            returnValue[0] = 0;
        }

        if (returnValue[0] == 0) {

            int highestOneBit = Integer.highestOneBit(xor0);
            highestOneBit |= Integer.highestOneBit(xor1);
            highestOneBit |= Integer.highestOneBit(xor2);

            int numLeadingZeros = Integer.numberOfLeadingZeros(highestOneBit);

            returnValue[1] = length - (32 - numLeadingZeros);
        }

        return returnValue;
    }
}

TestEnvironment.java

Code:

package com.killkrog.string_compare;

import com.killkrog.klib.date.KTimer;
import com.killkrog.klib.math.KMathTools;

public class TestEnvironment {

    // ===================================================================
    // {[> Attributes
    // ==============
    private static final int WORD_LENGTH = 10;
    private static final int NUM_WORDS = 40000;

    private ExampleStructure[] data1 = new ExampleStructure[NUM_WORDS];
    private String[] data2 = new String[NUM_WORDS];



    // ===================================================================
    // {[> Initializers and Constructors
    // =================================
    public TestEnvironment() throws Exception {

        generateRandomData();

        KTimer timer = new KTimer(true);
        for (int i = 0; i < NUM_WORDS; i++) {
            for (int j = 0; j < NUM_WORDS; j++) {
                data1[i].compare(data1[j]);
            }
        }
        timer.stop();

        timer.start();
        for (int i = 0; i < NUM_WORDS; i++) {
            for (int j = 0; j < NUM_WORDS; j++) {
                differsMaxOneChar(data2[i], data2[j]);
            }
        }
        timer.stop();
    }



    // ===================================================================
    // {[> Public Static Methods
    // =========================
    public static void main(String[] args) throws Exception {
        new TestEnvironment();
    }



    // ===================================================================
    // {[> Private Methods
    // ===================
    private int[] differsMaxOneChar(String a, String 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;
    }

    private void generateRandomData() {

        String s;

        for (int i = 0; i < NUM_WORDS; i++) {

            s = "";

            for (int n = 0; n < WORD_LENGTH; n++) {
                s += KMathTools.random(0, 2);
            }

            data1[i] = new ExampleStructure(s);
            data2[i] = s;
        }
    }
}

John Reese · 12. Oktober 2017

Ich könnte mir gut vorstellen, dass durch die in Java 9 eingeführten "Compact Strings" [1] die Performance zunimmt.

[1] http://openjdk.java.net/jeps/254

Master1991 · 13. Oktober 2017

Killkrog schrieb:
Es ist schon spät/früh, daher führe ich jetzt nichts mehr großartig aus, sondern lasse den Code für sich sprechen.

Ich hatte heute keine Zeit, konnte gerade nur kurz gucken. Aber das sieht fantastisch aus auf den ersten Blick. Ich schau es mir morgen an. Die Frage ist wie schnell kann der Konstruktor abgearbeitet werden. Aber da Verhältnismäßig deutlich weniger Objekte erstellt werden sollte das keine Rolle spielen. Sehr gut. Danke schonmal. Mehr morgen

Killkrog · 13. Oktober 2017

Master1991 schrieb:
Die Frage ist wie schnell kann der Konstruktor abgearbeitet werden.

Da hast du natürlich recht!
Ich hab den eigentlich auch nur als "Quick'n'Dirty" Methode angesehen, um von deinem Format in meines konvertieren zu können. Ich hoffe einfach, dass du in der Generierung der Daten so frei bist, dass du da eventuell eine performantere Lösung findest.

Aber selbst wenn nicht, ich habe gerade mal gestoppt, wie lange es dauert, die Konstrukturen für alle Objekte in der obigen Testumgebung abzuarbeiten, und das waren nur 14ms. Das ist bei dem restlichen Geschwindigkeitsgewinn vernachlässigbar. Und der Konstruktur ist auch nicht im geringsten optimiert, eventuell kann man da auch noch ein Quäntchen Geschwindigkeit rausholen.

Ansonsten bin ich gespannt auf deinen Bericht morgen!

Master1991 · 13. Oktober 2017

Killkrog schrieb:
Das ist bei dem restlichen Geschwindigkeitsgewinn vernachlässigbar.
Ansonsten bin ich gespannt auf deinen Bericht morgen!

Vollkommen vernachlässigbar.

Ich danke dir auf jedenfall, die Methode von dir ist wesentlich besser und die Idee dahinter auch top. Werde ich so implementieren. Musste die Methode jedoch etwas anpassen, habe mich wohl nicht präzise genug ausgedrückt was die exakte Funktion ist.

Habe außerdem die Idee eines Vorposters übernommen und den Rückgabewert auf einen int reduziert.

Code:

public int compare(ExampleStructure o) {
        int xor0 = b0 ^ o.b0;
        int xor1 = b1 ^ o.b1;
        int xor2 = b2 ^ o.b2;

        int orSum = xor0 | xor1 | xor2;
        int orBitCount = Integer.bitCount(orSum);

        if (!(orBitCount == 1)) {
            return -1;
        }

        int highestOneBit = Integer.highestOneBit(orSum);
        int numLeadingZeros = Integer.numberOfLeadingZeros(highestOneBit);
        return length - (32 - numLeadingZeros);
    }

Die Methode braucht leider 4x so lang wie deine, wenngleich ich nicht recht verstehe wieso

Trotzdem ein enormer Geschwindigkeitszuwachs

Killkrog · 13. Oktober 2017

Master1991 schrieb:
Musste die Methode jedoch etwas anpassen, habe mich wohl nicht präzise genug ausgedrückt was die exakte Funktion ist.

Kannst du das bitte genau erklären? Ich hatte eigentlich einen Test geschrieben, der sicherstellt, dass meine Methode die selben Resultate wie die deine liefert.
Besonders verwirrt bin ich, weil deine neue Methode aus dem letzten Post andere Ergebnisse liefert als deine ursprüngliche. Bitte erklären!

Ansonsten hab ich ne gute Idee, was deine Performance killt in der Methode, ich teste es und schreib dann hier wieder...

Master1991 · 13. Oktober 2017

Killkrog schrieb:
Kannst du das bitte genau erklären? Ich hatte eigentlich einen Test geschrieben, der sicherstellt, dass meine Methode die selben Resultate wie die deine liefert.
Besonders verwirrt bin ich, weil deine neue Methode aus dem letzten Post andere Ergebnisse liefert als deine ursprüngliche.

Warte, jetzt bin ich verwirrt

Die tut doch das selbe

Im Endeffekt stelle ich gerade aber auch fest geht es eig nur um einen Fall bei n=8 ist der Algo nicht nennenswert verzögert. n=9 konnte ich jetzt von 40sek auf 20sek reduzieren. n=10 dauert so lange das es nicht wirklich sinnvoll ist diesen Fall im worst case laufen zu lassen

Vielleicht ist das ganze auch übertriebener Aufwand. Naja interessehalber jetzt trotzdem:

Also die jeweils untereinanderstehenden werden verglichen. Durchnummeriert von links nach rechts

0001 0X01 0000 XX10
0001 0101 010X XX00

1. Wäre ungültig weil gleich (soll sich aber genau in einer Position unterscheiden - meine Methode war scheiße bennant habe ich festgestellt) - Der Fall kann aber nicht auftreten
2. Wäre gültig mit Rückgabe von 1 (da Pos 1 sich unterscheidet)
3. Wäre falsch da mehr als eine Position abweicht.
4. Wäre zB auch richtig

Killkrog · 13. Oktober 2017

Ah, alles klar. Mir war nicht bewusst, dass der Fall von gleichen Strings nicht auftreten kann.

Deine allererste Methode hätte in dem Fall nämlich [1,0] zurückgeben, deine zweite Methode allerdings nicht. Daher meine Verwirrung...

Bezüglich der Geschwindigkeit:

Du benutzt keine Abbruchbedingungen innerhalb deiner Methode, so dass sie immer die Laufzeit O(n) hat. Die Methode, die ich am Ende dieses Posts anhängen werde, hat O(log(n)).
(!(orBitCount == 1)) ist tatsächlich (marginal) langsamer als (orBitCount != 1)
Mehrere return Anweisungen sind meist langsamer als nur eine einzige am Ende. Ich weiß, klingt komisch, besonders wenn man C gewohnt ist, wo bei einem return der Wert einfach in den V0 Register geschossen wird und das war's. Bei Java passiert da noch ein bisschen mehr im Hintergrund.

Ich habe nun bei der Generierung der Testdaten darauf geachtet, dass niemals der selbe String miteinander verglichen werden kann. Das hat das ganze natürlich etwas näher in Richtung Worst-Case getrieben und dementsprechend die Zeiten verändert.

Dennoch, hier die Zeiten:
Es werden 500 Millionen mal Strings der Länge 10 miteinander verglichen. Wie gesagt, es werden niemals zwei gleiche Strings miteinander verglichen.

Deine alte differsMaxOneChar(): 22s 750ms 120μs 204ns
Deine angepasste compare(): 8s 638ms 678μs 356ns
Meine neue differs(): 6s 889ms 653μs 510ns

Ich glaube, wir sind jetzt langsam am Ende der Optimierungsmöglichkeiten angelangt.

TestEnvironment.java

Code:

public class TestEnvironment {

    // ===================================================================
    // {[> Attributes
    // ==============
    private static final int NUM_WORDS = 100000;
    private static final int WORD_LENGTH = 10;
    private static final int REPETITIONS = 5000;

    private String[] stringData1, stringData2;
    private Struct[] structData1, structData2;



    // ===================================================================
    // {[> Initializers and Constructors
    // =================================
    public TestEnvironment() throws Exception {

        generateRandomData();

        KTimer.run(() -> {
            for (int r = 0; r < REPETITIONS; r++) {
                for (int i = 0; i < NUM_WORDS; i++) {
                    structData1[i].differs(structData2[i]);
                }
            }
        });
        
        KTimer.run(() -> {
            for (int r = 0; r < REPETITIONS; r++) {
                for (int i = 0; i < NUM_WORDS; i++) {
                    structData1[i].compare(structData2[i]);
                }
            }
        });
        
        KTimer.run(() -> {
            for (int r = 0; r < REPETITIONS; r++) {
                for (int i = 0; i < NUM_WORDS; i++) {
                    differsMaxOneChar(stringData1[i], stringData2[i]);
                }
            }
        });
    }



    // ===================================================================
    // {[> Public Static Methods
    // =========================
    public static void main(String[] args) throws Exception {
        new TestEnvironment();
    }



    // ===================================================================
    // {[> Private Methods
    // ===================
    private int[] differsMaxOneChar(String a, String 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;
    }

    private void generateRandomData() {

        stringData1 = new String[NUM_WORDS];
        stringData2 = new String[NUM_WORDS];

        structData1 = new Struct[NUM_WORDS];
        structData2 = new Struct[NUM_WORDS];



        String s;

        for (int i = 0; i < NUM_WORDS; i++) {

            s = "";

            for (int n = 0; n < WORD_LENGTH; n++) {
                s += KMathTools.random(0, 2);
            }

            stringData1[i] = s;
            structData1[i] = new Struct(s);
        }

        for (int i = 0; i < NUM_WORDS; i++) {

            s = "";

            for (int n = 0; n < WORD_LENGTH; n++) {
                s += KMathTools.random(0, 2);
            }

            if (stringData1[i].equals(s)) {
                i--;
                continue;
            }

            stringData2[i] = s;
            structData2[i] = new Struct(s);
        }
    }
}

Struct.java

Code:

public class Struct {

    // ===================================================================
    // {[> Attributes
    // ==============
    private int char0, char1, char2;
    private int length;



    // ===================================================================
    // {[> Initializers and Constructors
    // =================================
    public Struct(String s) {

        length = s.length();
        int tmp;

        for (int i = 0; i < length; i++) {

            tmp = 1 << (length - i - 1);

            if (s.substring(i, i + 1).equals("0")) {
                char0 |= tmp;
            } else if (s.substring(i, i + 1).equals("1")) {
                char1 |= tmp;
            } else if (s.substring(i, i + 1).equals("2")) {
                char2 |= tmp;
            }
        }
    }



    // ===================================================================
    // {[> Public Methods
    // ==================
    public int compare(Struct o) {

        int xor0 = char0 ^ o.char0;
        int xor1 = char1 ^ o.char1;
        int xor2 = char2 ^ o.char2;

        int orSum = xor0 | xor1 | xor2;
        int orBitCount = Integer.bitCount(orSum);

        if (!(orBitCount == 1)) {
            return -1;
        }

        int highestOneBit = Integer.highestOneBit(orSum);
        int numLeadingZeros = Integer.numberOfLeadingZeros(highestOneBit);
        return length - (32 - numLeadingZeros);
    }

    public int differs(Struct o) {

        int retVal = -1;
        
        int xor0 = char0 ^ o.char0;

        if (Integer.bitCount(xor0) < 2) {

            int xor1 = char1 ^ o.char1;

            if (Integer.bitCount(xor1) < 2) {

                int xor2 = char2 ^ o.char2;
                int xor = xor0 | xor1 | xor2;

                if (Integer.bitCount(xor) == 1) {
                    retVal = length - (32 - Integer.numberOfLeadingZeros(Integer.highestOneBit(xor)));
                }
            }
        }

        return retVal;
    }
}

Master1991 · 13. Oktober 2017

Ich danke dir für deinen Arbeitsaufwand.

So hätte ich das nie versucht, denn:

1. Ich hätte gedacht das eine Bitweise verknüpfung deutlich schneller ist als neue if und Integer.BitCount aufrufe.
2. Das ein einziges return schneller ist als mehrere finde ich tatsächlich auch witzig

Ich habe jedenfalls was gelernt. Danke dir...es wird sicher nicht der letzte Thread zu dem Thema sein

Mal sehen wie der Rest nun voranschreitet

EDIT// Deine Methode funktioniert nicht

ich weiß aber nicht warum

EDIT2// Nimm

0000
0001

Dann ist xor0 = 1
aber xor1 ebenfalls 1, wodurch diff auf 2 springt obwohl der vergleich valide wäre

Killkrog · 13. Oktober 2017

Du hattest Recht, hatte einen bösen Denkfehler drin.
Habe meinen letzten Beitrag editiert mit den entsprechenden Korrekturen.
Die Zeiten sind gleich gelieben.

Ergänzung (14. Oktober 2017)

Killkrog schrieb:
Ich glaube, wir sind jetzt langsam am Ende der Optimierungsmöglichkeiten angelangt.

Haha, denkste!

Also, ich hab mal ein bisschen rumüberlegt, wie wir das Ganze noch ein wenig aufpeppen können.
Unsere letzte Optimierung bestand ja darin, je nach Fall möglichst wenige Binäroperationen durchzuführen, was wir mithilfe von ein paar Bedingungen erreicht haben.

Dann dachte ich mir, gehen wir noch einen Schritt weiter...
Bisher benutzen wir drei Integer (für jeden möglichen Buchstaben einen) und speichern darin unsere Positionen.

Wenn wir von einer maximalen Wortlänge von 10 ausgehen, bei drei verschiedenen Buchstaben, brauchen wir 30 Bit, um das darstellen zu können. Hmm... 30 Bit passen noch immer bequem in einen Integer!

Ich habe nun also anstatt drei verschiedener Integer die bisherigen Daten in nur einen Integer reingeschoben, einfach durch zwei Bit-Shifts.

Das bedeutet allerdings auch, dass wir nicht mehr über die Wortlänge von 10 hinauskommen. Sollte das gewollt sein, dann muss anstatt eines Integer ein Long benutzt werden, dann haben wir eine maximale Wortlänge von 64 / 3 = 21.

Okay, was folgt nun daraus? Die compare() Methode ist unglaub simpel geworden. Ein XOR mit den übergebenen Objekt. Wenn es genau zwei gesetzte Bits darin gibt, haben wir einen Treffer und können schauen, wo. Das funktioniert genau wie zuvor, nur dass wir nun eventuell den Index ein wenig anpassen müssen. Das ist so, weil wir ja nun die drei Infoblöcke mit den Positionen nebeneinander gespeichert haben und nicht mehr separat.

Alles in allem bin ich nun von einem Faktor 3,3 auf einen Faktor 8,6 mehr Geschwindigkeit gekommen.

Selbe Testbedingungen wie zuvor, neue Zeiten:

Struct.compare: 1s 445ms
differsMaxOneChar: 12s 468ms

TestEnvironment.java

Code:

public class TestEnvironment {

    // ===================================================================
    // {[> Attributes
    // ==============
    private static final int NUM_WORDS = 100000;
    private static final int WORD_LENGTH = 10;
    private static final int REPETITIONS = 5000;

    private String[] stringData1, stringData2;
    private Struct[] structData1, structData2;



    // ===================================================================
    // {[> Initializers and Constructors
    // =================================
    public TestEnvironment() throws Exception {

        Struct.setWordLength(WORD_LENGTH);
        generateRandomData();

        System.gc();

        KTimer.run(() -> {
            for (int r = 0; r < REPETITIONS; r++) {
                for (int i = 0; i < NUM_WORDS; i++) {
                    structData1[i].compare(structData2[i]);
                }
            }
        });

        System.gc();

        KTimer.run(() -> {
            for (int r = 0; r < REPETITIONS; r++) {
                for (int i = 0; i < NUM_WORDS; i++) {
                    differsMaxOneChar(stringData1[i], stringData2[i]);
                }
            }
        });
    }



    // ===================================================================
    // {[> Public Static Methods
    // =========================
    public static void main(String[] args) throws Exception {
        new TestEnvironment();
    }



    // ===================================================================
    // {[> Private Methods
    // ===================
    private int[] differsMaxOneChar(String a, String 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;
    }

    private void generateRandomData() {

        stringData1 = new String[NUM_WORDS];
        stringData2 = new String[NUM_WORDS];

        structData1 = new Struct[NUM_WORDS];
        structData2 = new Struct[NUM_WORDS];



        String s;

        for (int i = 0; i < NUM_WORDS; i++) {

            s = "";

            for (int n = 0; n < WORD_LENGTH; n++) {
                s += KMathTools.random(0, 2);
            }

            stringData1[i] = s;
            structData1[i] = new Struct(s);
        }

        for (int i = 0; i < NUM_WORDS; i++) {

            s = "";

            for (int n = 0; n < WORD_LENGTH; n++) {
                s += KMathTools.random(0, 2);
            }

            if (stringData1[i].equals(s)) {
                i--;
                continue;
            }

            stringData2[i] = s;
            structData2[i] = new Struct(s);
        }
    }
}

Struct.java

Code:

public class Struct {

    // ===================================================================
    // {[> Attributes
    // ==============
    private static int wordLength, dataOffset;

    private int data;



    // ===================================================================
    // {[> Initializers and Constructors
    // =================================
    public Struct(String s) {

        int tmp, c0, c1, c2;

        c0 = c1 = c2 = 0;

        for (int i = 0; i < wordLength; i++) {

            tmp = 1 << (wordLength - i - 1);

            if (s.charAt(i) == '0') {
                c0 |= tmp;
            } else if (s.charAt(i) == '1') {
                c1 |= tmp;
            } else if (s.charAt(i) == '2') {
                c2 |= tmp;
            }
        }

        data |= c0;
        data <<= wordLength;

        data |= c1;
        data <<= wordLength;

        data |= c2;
    }



    // ===================================================================
    // {[> Public Static Methods
    // =========================
    public static void setWordLength(int wordLength) {
        Struct.wordLength = wordLength;
        Struct.dataOffset = wordLength - 32;
    }



    // ===================================================================
    // {[> Public Methods
    // ==================
    public int compare(Struct o) {

        int rv = -1;

        int xor = data ^ o.data;

        if (Integer.bitCount(xor) == 2) {

            rv = dataOffset + Integer.numberOfLeadingZeros(Integer.highestOneBit(xor));

            if (rv < 0) {
                rv += wordLength;
                if (rv < 0) {
                    rv += wordLength;
                }
            }
        }

        return rv;
    }
}

Java Komplexitätsoptimierung String vergleich

Lt. Junior Grade

Lt. Junior Grade

Lieutenant

Commodore

Lt. Junior Grade

Commander

Commodore

Lieutenant

Lieutenant

Lieutenant

Lt. Junior Grade

Lt. Commander

Lieutenant

Lt. Junior Grade

Lieutenant

Lt. Junior Grade

Lieutenant

Lt. Junior Grade

Lieutenant

Lt. Junior Grade

Ähnliche Themen