Проверка сортировки строк матрицы или фрейма данных в R

Каков эффективный способ проверить, отсортированы ли строки в матрице? [Обновление: см. ответ Аарона на Rcpp - простой и очень быстрый]

Я переношу некоторый код, который использует issorted(,'rows') из Matlab. Поскольку кажется, что is.unsorted не выходит за пределы векторов, я пишу или ищу что-то другое. Наивный метод - проверить, что отсортированная версия матрицы (или фрейма данных) такая же, как и исходная, но это явно неэффективно.

NB: Для сортировки, а-ля sortrows() в Matlab, мой код по сути использует SortedDF (он обернут в большую функцию, которая преобразует матрицы в кадры данных, передает параметры в order и т.д.). Я не удивлюсь, если существуют более быстрые реализации (на ум приходит таблица данных).

Обновление 1: Чтобы уточнить: я не тестирую сортировку внутри строк или внутри столбцов. (Такая сортировка обычно приводит к алгебраически другой матрице.)

В качестве примера создания несортированной матрицы:

set.seed(0)
x <- as.data.frame(matrix(sample(3, 60, replace = TRUE), ncol = 6, byrow = TRUE))

Ее отсортированная версия:

y <- x[do.call(order, x),]

Правильный тест, скажем testSorted, вернет FALSE для testSorted(x) и TRUE для testSorted(y).

Обновление 2: Все приведенные ниже ответы хороши - они лаконичны и выполняют тест. Что касается эффективности, похоже, что они все-таки сортируют данные.

Я пробовал их с довольно большими матрицами, такими как 1M x 10, (просто изменив создание x выше) и все они имеют примерно одинаковые затраты времени и памяти. Особенностью является то, что все они потребляют больше времени для несортированных объектов (около 5,5 секунд для 1Mx10), чем для сортированных (около 0,5 секунд для y). Это говорит о том, что они сортируют перед тестированием.

Я протестировал, создав матрицу z:

z <- y
z[,2] <- y[,1]
z[,1] <- y[,2]

В этом случае на все методы уходит около 0,85 секунды. В любом случае, завершение за 5,5 секунд - это не ужасно (на самом деле, это, похоже, примерно время, необходимое для сортировки объекта), но знание того, что отсортированная матрица в 11 раз быстрее, позволяет предположить, что тест без сортировки может быть еще быстрее. В случае матрицы из 1M строк, первые три строки x следующие:

  V1 V2 V3 V4 V5 V6 V7 V8 V9 V10
1  3  1  2  2  3  1  3  3  2   2
2  1  1  1  3  2  3  2  3  3   2
3  3  3  1  2  1  1  2  1  2   3

Нет необходимости смотреть дальше второй строки, хотя векторизация - неплохая идея.

(Я также добавил аргумент byrow для создания x, чтобы значения ряда не зависели от размера x.)

Update 3: Другое сравнение для этого тестирования можно найти с помощью команды sort -c в Linux. Если файл уже записан (с помощью write.table()), с 1M строк, то time sort -c myfile.txt занимает 0.003 секунды для несортированных данных и 0.101 секунды для отсортированных. Я не собираюсь записывать данные в файл, но это полезное сравнение.

Обновление 4: Метод Rcpp Аарона превзошел все другие методы, предложенные здесь и опробованные мной (включая сравнение sort -c выше: ожидается, что in-memory победит on-disk). Что касается соотношения с другими методами, трудно сказать: знаменатель слишком мал для точного измерения, а я не исследовал подробно microbenchmark. Ускорение может быть очень большим (на 4-5 порядков) для некоторых матриц (например, сделанных с помощью rnorm), но это обманчиво - проверка может завершиться всего после пары строк. Я получил ускорение на примере матриц около 25-60 для несортированных и около 1.1X для сортированных, поскольку конкурирующие методы уже были очень быстрыми, если данные были отсортированы.

Поскольку это делает правильную вещь (т.е. никакой сортировки, только тестирование), и делает это очень быстро, это принятый ответ.