Блог

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

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

ПРИМЕЧАНИЕ: для сортировки a la 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 for testSorted(x) и TRUE for testSorted(y) .

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

Я пробовал их с довольно большими матрицами, такими как 1 М 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 раз быстрее, предполагает, что тест, который не сортирует, может быть еще быстрее. В случае матрицы из 1 строки первые три строки 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 сравнение выше: ожидается, что in-memory превзойдет on-disk). Что касается соотношения относительно других методов, трудно сказать: знаменатель слишком мал, чтобы дать точное измерение, и я не изучал microbenchmark его подробно. Ускорения могут быть очень большими (на 4-5 порядков) для некоторых матриц (например, для матрицы, созданной с rnorm помощью ), но это вводит в заблуждение — проверка может завершиться только через пару строк. У меня были ускорения с примерами матриц примерно на 25-60 для несортированных и примерно в 1,1 раза для отсортированных, поскольку конкурирующие методы были уже очень быстрыми, если данные отсортированы.

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

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

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

обратите внимание, что при этом матрицы не сравниваются, но они не исчезают, как только обнаруживается несоответствие.

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

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

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

Новее: я решил, что могу использовать практику 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)
}
  

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

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

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

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

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