F # - Сортировать матрицу, содержащую кортежи

Question

Я не нахожу способ сортировки значений, включенных в столбцы следующей матрицы кортежей:

Matrix<float * float> =
  matrix [[(1.0, 145.0); (1.0, 45.0); (1.0, 130.0); (1.0, 30.0); (1.0, 130.0)]
          [(2.0, 45.0); (2.0, 45.0); (2.0, 30.0); (2.0, 30.0); (2.0, 30.0)]
          [(3.0, 130.0); (3.0, 30.0); (3.0, 145.0); (3.0, 45.0); (3.0, 130.0)]
          [(4.0, 30.0); (4.0, 30.0); (4.0, 45.0); (4.0, 45.0); (4.0, 30.0)]
          [(5.0, 130.0); (5.0, 30.0); (5.0, 130.0); (5.0, 30.0); (5.0, 145.0)]]

Я бы хотел отсортировать каждый столбец в зависимости от второго элемента кортежа. Например, здесь ответ будет:

   matrix [[(1.0, 145.0); (1.0, 45.0); (3.0, 145.0); (3.0, 45.0); (5.0, 145.0)]
          [(3.0, 130.0); (2.0, 45.0); (1.0, 130.0); (4.0, 45.0); (1.0, 130.0)]
          [(5.0, 130.0); (3.0, 30.0); (5.0, 130.0); (1.0, 30.0); (3.0, 130.0)]
          [(2.0, 45.0); (4.0, 30.0); (4.0, 45.0); (2.0, 30.0); (2.0, 30.0)]
          [(4.0, 30.0); (5.0, 30.0); (2.0, 30.0); (5.0, 30.0); (4.0, 30.0)]]

Заранее спасибо!

Answer 1

Ниже приведена такая функция:

let sortByCol f (m:Matrix<'T>) = 
    let n = m.Transpose
    [for i = 0 to n.NumRows-1 do 
        yield [for j in n.Row(i) -> j] 
              |> List.sortBy f ]
    |> Matrix.Generic.ofList
    |> Matrix.Generic.transpose

Использование как специфическое для этого вопроса:

matrix |> sortByCol (fun (_,b) -> -b)

ОБНОВЛЕНО: Чтобы сделать функцию сортировки по col универсальной.

Answer 2

По своему опыту, при работе с массивами (2D и / или матрицами) я обнаружил, что внутренняя работа с массивами часто является самым быстрым способом.

Например, объединение подходов Даниэля и Анкура в изменяемойway:

let mutableSortByCol f (m:Matrix<'T>) =
    let columns = [| for c in 0 .. m.NumCols - 1 -> 
                         m.Column c |> Vector.Generic.toArray |]

    for c in 0 .. m.NumCols - 1 do 
        columns.[c] |> Array.sortInPlaceBy f

    Matrix.Generic.init (m.NumRows) (m.NumCols) (fun r c -> columns.[c].[r])

Я преобразовал матрицу в массив столбцов ('a [] [], а не' a [,]) и выполнил сортировку на месте для каждого столбца.После этого я заполнил новую матрицу отсортированным результатом.Обратите внимание, что исходная матрица остается неизменной: массив столбцов заполняется копиями векторов столбцов (Vector.toArray создает новый массив).

Этот подход быстрее, поскольку он не требует транспонирования, сортирует столбцы по месту,и не требует преобразования в и из промежуточных структур списков, сохраняя все ориентированное на массив.Я подозреваю, что это могло бы быть сделано еще быстрее, если бы модуль Matrix поддерживал преобразование в / из 'a [] [], хотя, возможно, он не очень подходит для матриц.

Кроме того, на случай, если вы не знали: вы можете использовать структурное сравнение F # кортежей для сортировки по убыванию второго элемента, возрастанию первого элемента:

Пример:

> mutableSortByCol (fun (a,b) -> (-b,a)) M;;
val it : Matrix<float * float> =
  matrix [[(1.0, 145.0); (1.0, 45.0); (3.0, 145.0); (3.0, 45.0); (5.0, 145.0)]
          [(3.0, 130.0); (2.0, 45.0); (1.0, 130.0); (4.0, 45.0); (1.0, 130.0)]
          [(5.0, 130.0); (3.0, 30.0); (5.0, 130.0); (1.0, 30.0); (3.0, 130.0)]
          [(2.0, 45.0); (4.0, 30.0); (4.0, 45.0); (2.0, 30.0); (2.0, 30.0)]
          [(4.0, 30.0); (5.0, 30.0); (2.0, 30.0); (5.0, 30.0); (4.0, 30.0)]]

Answer 3

Я никогда раньше не использовал Matrix, так что может быть лучший способ, но, похоже, это работает:

let sortMatrix (m:Matrix<_>) =
  seq {
    for c in 0 .. (m.NumCols - 1) do
      let arr = [| for r in 0 .. (m.NumRows - 1) -> m.[r, c] |]
      arr |> Array.sortInPlaceBy (fun (_, b) -> -b : float) //(snd >> (~-))
      yield arr
  }
  |> Matrix.Generic.ofSeq 
  |> Matrix.Generic.transpose