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

根据我的经验，在使用数组（2D 和/或矩阵）时，我发现在内部使用数组通常是最快的方法。

例如，以可变方式组合 Daniel 和 Ankur 的方法：

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 2

下面是这样一个函数：

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 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