Sort point cloud coordinates according to X, Y, or Z values
A
is a series of point coordinates in 3D (X, Y, Z), for example:
>> A = [1 2 0;3 4 7;5 6 9;9 0 5;7 8 4]
A =
1 2 0
3 4 7
5 6 9
9 0 5
7 8 4
I would like to sort the matrix by values "Y" (second column)
.
Here is the code I'm using:
>> tic;[~, loc] = sort(A(:,2));
SortedA = A(loc,:)
toc;
SortedA =
9 0 5
1 2 0
3 4 7
5 6 9
7 8 4
Elapsed time is **0.001525** seconds.
However, for a large dataset, it can be very slow. I would appreciate it if anyone knew a more efficient approach.
source to share
Introductory discussion
This answer will mainly talk about how efficient computing can be used GPU
to solve the above problem. The solution code for the specified problem, provided in the question, was:
[~, loc] = sort(A(:,2)); SortedA = A(loc,:);
There are essentially two parts -
- Select the second column, sort them and get sorted indices.
- An index into the rows of the input matrix with sorted indices.
It Part 1
is now computationally intensive, which can be ported to GPU
, but Part 2
which is the work of indexing, can be done on its own CPU
.
Proposed solution
So, with all this in mind, an effective solution GPU
would be -
gA = gpuArray(A(:,2)); %// Port only the second column of input matrix to GPU
[~, gloc] = sort(gA); %// compute sorted indices on GPU
SortedA = A(gather(gloc),:); %// get the sorted indices back to CPU with `gather`
%// and then use them to get sorted A
Benchmarking
The following is comparative code to compare the version GPU
with the original solution, however, keep in mind that since we are running the codes GPU
on different hardware compared to the originally announced solution that runs on CPU
, test results may differ from system to system.
Here's the test code -
N = 3000000; %// datasize (number of rows in input) A = rand(N,3); %// generate random large input disp('------------------ With original solution on CPU') tic [~, loc] = sort(A(:,2)); SortedA = A(loc,:); toc, clear SortedA loc disp('------------------ With proposed solution on GPU') tic gA = gpuArray(A(:,2)); [~, gloc] = sort(gA); SortedA = A(gather(gloc),:); toc
Here are the test results -
------------------ With original solution on CPU
Elapsed time is 0.795616 seconds.
------------------ With proposed solution on GPU
Elapsed time is 0.465643 seconds.
So, if yours is decent enough GPU
, it's time to give it a try GPU
for sorting the related problem, much less with MATLAB providing such lightweight portability solutions GPU
.
system configuration
MATLAB Version: 8.3.0.532 (R2014a)
Operating System: Windows 7
RAM: 3GB
CPU Model: Intel® Pentium® Processor E5400 (2M Cache, 2.70 GHz)
GPU Model: GTX 750Ti 2GB
source to share
MATLAB has a function called for this sortrows()
, but in my experience it tends to be as slow as what you do for a general unstructured matrix.
Test:
N = 1e4; A = rand(N,N); tic;[~, loc] = sort(A(:,2)); SortedA = A(loc,:); toc; tic; sortrows(A,2); toc;
gives:
Elapsed time is 0.515903 seconds.
Elapsed time is 0.525725 seconds.
source to share
Try sortrows
it by specifying column 2:
Asorted = sortrows(A,2)
Simplified, but actually slower now that I'm testing it ... Apparently sortrows
not that great if you only consider one column to sort. This is probably best when you are looking at multiple columns in a specific order.
source to share