Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Julia: Sort the columns of a matrix by the values in another vector (in place...)?

I am interested in sorting the columns of a matrix in terms of the values in 2 other vectors. As an example, suppose the matrix and vectors look like this:

M  = [ 1   2   3   4   5   6  ; 
       7   8   9   10  11  12 ; 
       13  14  15  16  17  18 ]

v1 = [ 2 , 6 , 6 , 1 , 3 , 2  ]
v2 = [ 3 , 1 , 2 , 7 , 9 , 1  ]

I want to sort the columns of A in terms of their corresponding values in v1 and v2, with v1 taking precedence over v2. Additionally, I am interested in trying to sort the matrix in place as the matrices I am working with are very large. Currently, my crude solution looks like this:

MM = [ v1' ; v2' ; M ] ; ## concatenate the vectors with the matrix
MM[:,:] = sortcols(MM , by=x->(x[1],x[2])) 
M[:,:] = MM[3:end,:]

which gives the desired result:

3x6 Array{Int64,2}:
  4   6   1   5   2   3
 10  12   7  11   8   9
 16  18  13  17  14  15

Clearly my approach is not ideal is it requires computing and storing intermediate matrices. Is there a more efficient/elegant approach for sorting the columns of a matrix in terms of 2 other vectors? And can it be done in place to save memory?

Previously I have used sortperm for sorting an array in terms of the values stored in another vector. Is it possible to use sortperm with 2 vectors (and in-place)?

like image 951
Landon Avatar asked Aug 31 '16 07:08

Landon


1 Answers

I would probably do it this way:

julia> cols = sort!([1:size(M,2);], by=i->(v1[i],v2[i]));

julia> M[:,cols]
3×6 Array{Int64,2}:
  4   6   1   5   2   3
 10  12   7  11   8   9
 16  18  13  17  14  15

This should be pretty fast and uses only one temporary vector and one copy of the matrix. It's not fully in-place, but doing this operation completely in-place is not easy. You would need a sorting function that moves columns as it works, or alternatively a version of permute! that works on columns. You could start with the code for permute!! in combinatorics.jl and modify it to permute columns, reusing a single column-size temporary buffer.

like image 139
Jeff Bezanson Avatar answered Nov 16 '22 01:11

Jeff Bezanson