按照X、Y或Z值排序点云坐标

Question

A 是一个三维坐标系中的一系列点坐标 (X,Y,Z)，例如：

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

我想要按照 "Y"（第二列） 的值对矩阵进行排序。

这里是我正在使用的代码：

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

经过 **0.001525** 秒的运行时间。

然而，对于大数据集来说，这种方法可能非常慢。如果有人知道更高效的方法，我将不胜感激。

- Iman

---

如果你有一张不错的GPU，你可以利用它获得非常好的加速效果，这只是一些信息。 - Divakar

@Divakar 我需要更改电脑的任何设置吗？ - Iman

你只需要在PCT工具箱中使用gpuArray，但是你有一张足够好的GPU来处理吗？ - Divakar

@Divakar 是的，伙计，我买了一张 "NVIDIA GeForce GTX 645" 的显卡，应该没问题吧？ - Iman

添加了一个基于GPU的解决方案，查看它在您这端的运行效果！ - Divakar

Answer 1

尝试使用sortrows，并指定第2列：

Asorted = sortrows(A,2)

经过测试，我发现这种方法虽然简单，但实际上速度较慢。显然，如果您只考虑一个列进行排序，那么sortrows并不是最好的选择。如果您考虑按照特定顺序对多个列进行排序，那么它可能是最好的选择。

- chappjc

---

谢谢，这看起来很有用。但是我想保持问题的开放，并希望能得到更快的解决方案。 - Iman

Answer 2

MATLAB有一个叫做sortrows()的功能可以实现这个，但是在我的经验中，它对于一般的非结构化矩阵来说往往与你所做的方法一样慢。

测试：

N = 1e4;
A = rand(N,N);
tic;[~, loc] = sort(A(:,2));
SortedA = A(loc,:);
toc;

tic; sortrows(A,2); toc;

提供：

Elapsed time is 0.515903 seconds.
Elapsed time is 0.525725 seconds.

- Nitish

---

我看到了一个更大的差异。显然，如果你只考虑一个列进行排序，sortrows并不是很好用。当你按照特定顺序考虑多个列时，它可能是最好的选择。 - chappjc

@chappjc，有趣。我刚刚阅读了它的源代码，结果发现如果列维度大于4，sortrows只调用C包装器。否则，它就像OP一样。 - Nitish

在R2014中，它超过3（sortrowsc），否则它调用sortrows>sort_back_to_front，它做的就像OP所做的那样，就像你说的那样。我怀疑没有比他所做的更快的方法...这是标准的方法，有其原因。 :) - chappjc

Answer 3

简介讨论

本答案主要讲解如何利用高效的计算机图形处理器（GPU）来解决所述问题。问题中给出的解决方案代码如下：

[~, loc] = sort(A(:,2));
SortedA = A(loc,:);

这个问题基本上可以分为两部分：

1. 选择第二列，对它们进行排序并获得排序后的索引。
2. 使用排序后的索引来索引输入矩阵的行。

现在，Part 1 是计算密集型的，可以移植到 GPU 上，但是Part 2 是索引工作，可以在 CPU 上完成。

建议的解决方案

所以，考虑到这些因素，一个高效的 GPU 解决方案如下：

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

基准测试

下面介绍了用于将 GPU 版本与原始解决方案进行比较的基准测试代码，但需要注意，由于我们在不同的硬件上运行 GPU 代码，与原始运行在 CPU 上的解决方案相比，基准测试结果可能因系统而异。

以下是基准测试代码 -

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

以下是基准测试结果：

------------------ With original solution on CPU
Elapsed time is 0.795616 seconds.
------------------ With proposed solution on GPU
Elapsed time is 0.465643 seconds.

如果您有足够好的 GPU，那么现在是尝试使用 GPU 来解决排序问题的最佳时机，特别是MATLAB提供了如此简单的 GPU 端口解决方案。

---

系统配置

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

- Divakar

---

就这样了。你太棒了！ - Iman