Schnelles Vergleichen

Hi!

Ich habe momentan ein kleines Problem. Ich habe eine Klasse (Burrows-Wheeler Transformation) in der ich extrem viele Vergleiche durchführen muss, zumindest im Worst und Average Case. Momenatn hab ich mirn eigenes CompareTo geschrieben, das zwei Objekte byteweise vergleicht. Das ist mir aber ansich zu langsam. Habt ihr eine Idee wies schneller geht?

Greetz, der Hühneradel

Hallo Chickenlord,

1.) Möglichkeit: wenn du ein Objekt mehrmals mit anderen Objekten verlgeichst, könntest du von diesem Objekt zuerst eine Art Hashcode berechnen und diesen zum Vergleichen nehmen.

2.) Möglichkeit: du versuchst deinen Algorithmus zu optimieren, sodass es weniger Vergleiche werden (du könntest ja etwas genauer schreiben, wie dein Programm/Algorithmus aussieht)

3.) Möglichkeit: Du könntest versuchen Kriterien zu finden, die oft unterschiedlich sind und den Vergleich mit diesen beginnen. Dann erkennt das Programm schneller, wenn zwei Objekte NICHT gleich sind.

4.) Möglichkeit: Kombinationen aus den Möglichkeiten 1,2 und 3 😉

Gruß
Preli

Naja also ablaufen tut das ganze folgendermaßen. Man nimmt eine Menge an original Daten und lässt sie jeweils um eine Stelle nach rechts rotieren und speichert jede Rotation in einer Liste, bis man wieder bei der Ausgangsmenge ist. Also ein total simples Beispiel wie eine Liste für die Eingabe "Hallo" aussehen würde:

Hallo
oHall
loHal
lloHa
alloH

Diese daraus entstehende Liste muss ich jetzt sortieren. Man kann sich vorstellen, wie viel das wird, wenn man z.B. 1mb Daten hat (Worst Case 1099511627776 Vergleiche). Dabei ist wichtig, das man sich natürlich nicht jedesmal einen neuen String speichert, sondern nur ein neues Objekt mit Referenz auf den Original String (oder byte array) und einem Index, wo der rotierte Wert startet. Hashen kann man leider nicht. Es ist zwar unwahrscheinlich, dass es gleiche Hashs für unterschiedliche Werte gibt, aber möglich. Und das darf nicht passieren, weil dann die Rücktransformation schiefgeht. Nach Kriterien hab ich schon gesucht, leider aber noch keine Gefunden. Mal zum anschauen meine CompareTo Methode, vielleicht hilfts:

//val ist string object und für alle Objekte vom Typ BWR bei einem Vergleich der selbe string.
//Pointer ist ein integer, der ein Rotations-Offset angibt. Im Regelfall nicht relevant, aber der volsständigkeit halber.
 public int CompareTo(BWR b)
        {
            if (b.Get(0) < this.Get(0))
            {
                return 1;
            }
            else if (b.Get(0) > this.Get(0))
            {
                return -1;
            }
            else
            {
                if (this.pointer == b.GetPointer())
                    return 0;
                int i = 1;
                while (i<val.Length)
                {
                    if (b.Get(i) < this.Get(i))
                        return 1;
                    else if (b.Get(i) > this.Get(i))

                        return -1;
                    else
                        i++;
                }
                return 0;
            }
        }

Achja, die Sachen stehen in einer List<T>.

Greetz, der Chicken

Also bei deinen 1.099.511.627.776 Vergleichen im Worst Case gehst du aber von einem Polynomiellen Sortieralgorithmus aus.
Vielleicht solltest du dich mehr ins Thema Sortieralgorithmus einlesen. Ich denke da ist das größte Potential (performancemäßig) rauszuholen. Wenn du nämlich einen Algorithmus nimmst, der nur n*log(n) als Laufzeit hat, hast du im Worst case plötzlich nur mehr 20.971.520 Vergleiche.

Interessant wäre sicher:

• Quicksort (sehr schnell, aber im schlechtesten Fall quadratische Laufzeit)
• Mergesort (im Gegensatz zu Quicksort stabiles Sortierverfahren und auch im worst case n*log(n) Laufzeit)
• Radixsort (sehr interessant, da LINEARE Laufzeit, aber es gibt dafür andere Einschränkungen, da es kein vergleichender Algorithmus ist)
• Heapsort (auch n*log(n) Laufzeit)

Du findest bei wikipedia zu jedem dieser Stickworte mehr Informationen.
Ach ja, und bei Quicksort ist der worst case bei nicht schon sortierten Werten soooooo unwahrscheinlich, dass er eigentlich zu vernachlässigen ist.

Gruß
Preli

Hi Chickenlord,

da wir hier vom Sortieren von versetzten Daten reden, kann man das natürlich auch algorithmisch ausnutzen.

Der hier passenden Algorithmus ist Suffix Sorting. Der ist nochmal wesentlich effizienter, als die allgemeinen Sortierverfahren (Und Suffix Arrays spielen auch da mit rein)

Zwar erscheinen

[PRE]Hallo
alloH
lloHa
loHal
oHall[/PRE]

nicht als Suffixe von "Hallo", aber man kann diese versetzen zyklischen Substrings in Suffixe umwandeln. Dazu verdoppelt man einfach den Ausgangsstring:

[PRE]HalloHallo
 alloHallo
  lloHallo
   loHallo
    oHallo[/PRE]

Bei der Sortierung kommt natürlich das selbe raus. Aber für letztes gibt es eben SuffixSorting. (Man kann das verdoppeln auch bestimmt irgendwie nur implizit machen, sodass man es nicht real durchführen muss.)

Aber Google ist wie immer dein Freund. =)

beste Grüße
zommi

Hallo Chickenlord

Erstmal grundlegend:
Wie vergleichst du deine Werte denn miteinander? Verwendest du verschachtelte Schleifen?

Grüße
Flo

Besten dank an zommi, das werd ich doch mal googln.
Welchen algorithmus ich atm benutze, ist eine gute Frage. Ich mach einfach List.Sort(). Die ganzen Algorithmen kenne ich sonst auch, da ich grade eine Klausur darüber schreiben durfte... Ansonsten vergleiche ich die Werte, wie oben zu sehen, mit einer simplen While(eigentlich for) Schleife. Aber auf jedenfall schonmal danke, für die Antworten.

Nur der Vollständigkeit halber: List.Sort benutzt Array.Sort, was wiederum Quicksort benutzt, was wiederum zu den schnellsten vergleichenden Sortieralgorithmen gehört.

Auf Suffix Sorting hätt ich eigentlich auch kommen können 🤔
Ich hab sowas zwar noch nie eingesetzt (war noch nie notwendig), sollen aber performancemäßig echt der Hammer sein.

Gruß
Preli