Ich mache gerade etwas ShearSorting und kann nicht herausfinden, wann diese Operation mit einer n x n-Matrix durchgeführt werden soll.
Was ich gerade mache, ist das Kopieren derMatrix am Anfang jeder Iteration der Schleife zu einer Temp-Matrix und dann am Ende jeder Iteration der Schleife I "m, die sowohl die ursprünglichen als auch die Temp-Matrizen vergleicht, und wenn sie gleich sind, bricht ich aus der Schleife aus und Ich mag diesen Ansatz nicht, da wir am Ende immer eine zusätzliche Iteration durchlaufen, nachdem die Matrix sortiert und fertig ist, was eine Verschwendung von CPU-Zeit und -Zyklen bedeutet.
Es muss einen besseren Weg geben, diese Überprüfung durchzuführen. Ich finde ständig Verweise auf log (n), um anzuzeigen, wie viele Iterationen wir benötigen, aber ich glaube nicht, dass sie tatsächlich log (n) als log (5) für eine 5x5-Matrix in 0,69 bedeuten, was für die Anzahl der Iterationen unmöglich ist.
Irgendwelche Vorschläge?
Antworten:
0 für die Antwort № 1SO weiß ich, dass shearSort Log (n) Iterationen ausführtFür den Fall der 5x5-Matrix haben wir 3 Läufe für Zeilen und 3 Läufe für Spalten. Aber was ist, wenn die 5x5-Matrix, die ich erhalten habe, fast sortiert ist und nur noch ein oder zwei weitere Iterationen erforderlich ist, dann sehe ich nicht den Punkt, bei dem ich 6 Mal durchlaufen muss, da dies eine Verschwendung von CPU-Energie wäre und Zyklen.
Wir haben auch die folgende Lösung: Wenn wir die Matrix zu Beginn jeder Iteration der shearSort-Funktion in eine temporäre Matrix kopieren und am Ende jeder Iteration die beiden Matrizen miteinander vergleichen und sie gleich sind, wissen wir, dass wir fertig sind Sowohl für eine Zeile als auch für eine Spaltensortierung als Matrix ist möglicherweise zunächst keine Zeilensortierung erforderlich. In diesem Fall würden wir die CPU-Zyklen beibehalten, falls die Matrix keine N + 1-Iterationen benötigt. Diese Lösung würde jedoch ein Problem darstellen. Die zusätzlichen 2 Iterationen wären eine, um zu prüfen, ob 2 Matrizen für die Zeile und eine für die Spalte gleich sind.
Um dies zu lösen, müssten wir eine Kombination beider Lösungen verwenden:
Wir würden die Matrix beim Start immer noch kopierenWenn wir sie am Ende mit der temporären Matrix vergleichen, und wenn sie gleich sind, bevor wir zu den N + 1-Iterationen gelangen, sind wir fertig und müssen nicht weiter fortfahren. Wenn sie nicht gleich sind, gehen wir zur N + 1-Iteration und stoppen Sie danach, da wir zu diesem Zeitpunkt wissen, dass die Matrix nach N + 1-Iterationen sortiert werden soll.