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

Question

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

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

NB. Для сортировки, например sortrows() в Matlab , мой код по существу использует SortedDF <- DF[do.call(order, DF),] (он заключен в большую функцию, которая преобразует матрицы в кадры данных, передает параметры в 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

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

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

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

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

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

Answer 1

Если y отсортирован, то do.call (order, y) возвращает 1: nrow (y).

 testSorted = function(y){all(do.call(order,y)==1:nrow(y))}

обратите внимание, что это не сравнивает матрицы, но не вычитается каккак только он найдет несоответствие.

Answer 2

Ну, почему бы вам не использовать:

all(do.call(order, y)==seq(nrow(y)))

Это позволяет избежать создания упорядоченной матрицы и проверяет ваш стиль упорядочения.

Answer 3

Новее : я решил, что могу использовать практику Rcpp ...

library(Rcpp)
library(inline)
isRowSorted <- cxxfunction(signature(A="numeric"), body='
  Rcpp::NumericMatrix Am(A);
  for(int i = 1; i < Am.nrow(); i++) {
    for(int j = 0; j < Am.ncol(); j++) {
      if( Am(i-1,j) < Am(i,j) ) { break; }
      if( Am(i-1,j) > Am(i,j) ) { return(wrap(false)); }
    }
  }
  return(wrap(true));
', plugin="Rcpp")

rownames(y) <- NULL # because as.matrix is faster without rownames
isRowSorted(as.matrix(y))

Новое: Этот хак только для R одинакова для всехматриц;это определенно быстрее для отсортированных матриц;для несортированных это зависит от характера несортировки.

iss3 <- function(x) {
  x2 <- sign(do.call(cbind, lapply(x, diff)))
  x3 <- t(x2)*(2^((ncol(x)-1):0))
  all(colSums(x3)>=0)
}

Оригинал: Это быстрее для некоторых несортированных матриц.Насколько быстрее будет зависеть от того, где находятся несортированные элементы;это выглядит как матрица столбец за столбцом, поэтому несортировка слева будет замечена гораздо быстрее, чем несортировка справа, тогда как верх / низ не имеют значения почти так же.

iss2 <- function(y) {
  b <- c(0,nrow(y))
  for(i in 1:ncol(y)) {
    z <- rle(y[,i])
    b2 <- cumsum(z$lengths)
    sp <- split(z$values, cut(b2, breaks=b))
    for(spi in sp) {
      if(is.unsorted(spi)) return(FALSE)
    }
    b <- c(0, b2)
  }
  return(TRUE)
}

Answer 4

Что ж, подход грубой силы состоит в том, чтобы зацикливаться и сравнивать, прерывая работу, как только обнаруживается нарушение.

Этот подход может быть легко реализован и протестирован в R, а затем перенесен в простую функцию C ++, которую мы можем подключить к R через inline и Rcpp (или просто C, если Вы должны), поскольку цикл - это то, что действительно выигрывает от реализации на скомпилированном языке.

В противном случае, вы не можете использовать что-то вроде diff() и проверить, все ли приращения неотрицательны?

Answer 5

Вы можете использовать ваше заявление do.call с is.unsorted:

issorted.matrix <- function(A) {!is.unsorted(do.call("order",data.frame(A)))}