Testen, ob Zeilen einer Matrix oder eines Datenrahmens in R sortiert sind

Was ist ein effizienter Weg zu testen, ob Zeilen in einer Matrix sortiert sind? [Update: siehe Aarons Rcpp Antwort - einfach & amp; sehr schnell.]

Ich portiere Code, der issorted(,'rows') von Matlab verwendet. Wie es scheint, dass sich is.unsorted nicht über Vektoren hinaus erstreckt, schreibe ich oder suche nach etwas anderem. Die naive Methode besteht darin, zu überprüfen, ob die sortierte Version der Matrix (oder des Datenrahmens) die gleiche ist wie das Original, aber das ist offensichtlich ineffizient.

Hinweis: Zum Sortieren, a la sortrows() in Matlab , wird im Wesentlichen mein Code verwendet SortedDF <- DF[do.call(order, DF),] (es ist in eine größere Funktion eingebunden, die Matrizen in Datenrahmen umwandelt, übergibt Parameter an order usw.). Ich wäre nicht überrascht, wenn es schnellere Implementierungen gibt (Datentabelle kommt mir in den Sinn).

Update 1: Zur Klarstellung: Ich prüfe nicht, ob Intra-Zeilen oder Intra-Spalten sortiert werden sollen. (Eine solche Sortierung führt im Allgemeinen zu einer algebraisch anderen Matrix.)

Als Beispiel für die Erstellung einer unsortierten Matrix:

Seine sortierte Version ist:

Ein richtiger Test, sagen wir testSorted , würde FALSE für testSorted(x) und TRUE für testSorted(y) zurückgeben.

Update 2: Die Antworten unten sind alle gut - sie sind kurz und machen den Test. Was die Effizienz anbelangt, sieht es so aus, als würden diese die Daten schließlich sortieren.

Ich habe diese mit ziemlich großen Matrizen, wie 1M x 10, versucht (nur die Erzeugung von x oben ändernd) und alle haben ungefähr die gleichen Zeit- und Speicherkosten. Das Besondere ist, dass alle mehr Zeit für unsortierte Objekte benötigen (etwa 5,5 Sekunden für 1M × 10) als für sortierte (etwa 0,5 Sekunden für y ). Dies deutet darauf hin, dass sie vor dem Testen sortieren.

Ich habe getestet, indem ich eine z -Matrix erstellt habe:

In diesem Fall benötigen alle Methoden ca. 0,85 Sekunden. Wie auch immer, das Beenden in 5,5 Sekunden ist nicht schrecklich (in der Tat scheint das recht zu sein bezüglich der Zeit, die nötig ist, um das Objekt zu sortieren), aber zu wissen, dass eine sortierte Matrix 11X schneller ist, legt nahe, dass ein Test, der nicht sortiert, gerade sein kann schneller. Im Falle der 1M Zeilenmatrix sind die ersten drei Zeilen von x :

Es muss nicht über Zeile 2 hinaus geschaut werden, obwohl die Vektorisierung keine schlechte Idee ist.

(Ich habe auch das Argument byrow für die Erstellung von x hinzugefügt, damit die Zeilenwerte nicht von der Größe von x abhängen.)

Update 3: Ein weiterer Vergleich für diesen Test kann mit dem Befehl sort -c in Linux gefunden werden. Wenn die Datei bereits (mit write.table() ) und mit 1M Zeilen geschrieben wurde, benötigt time sort -c myfile.txt 0,003 Sekunden für die unsortierten Daten und 0,101 Sekunden für die sortierten Daten. Ich habe nicht die Absicht, in eine Datei zu schreiben, aber es ist ein nützlicher Vergleich.

Update 4: Aarons Rcpp-Methode hat alle anderen hier angebotenen und getesteten Methoden übertroffen (einschließlich des sort -c -Vergleichs oben: In-memory wird voraussichtlich auf der Platte schlagen). Was das Verhältnis zu anderen Methoden betrifft, ist es schwer zu sagen: Der Nenner ist zu klein, um eine genaue Messung zu liefern, und ich habe microbenchmark nicht ausführlich untersucht. Die Beschleunigungen können sehr groß sein (4-5 Größenordnungen) für einige Matrizen (z. B. eine, die mit rnorm erstellt wurde), aber dies ist irreführend - die Überprüfung kann nach nur ein paar Zeilen beendet werden. Ich hatte Beschleunigungen mit den Beispielmatrizen von ungefähr 25-60 für die unsortierten und ungefähr 1.1X für die sortierten, da die konkurrierenden Methoden bereits sehr schnell waren, wenn die Daten sortiert sind.

Da dies das Richtige tut (d. h. keine Sortierung, nur Testen) und es sehr schnell macht, ist es die akzeptierte Antwort.