优化从 MATLAB 矩阵中提取数据？

Question

给定一个 n 维值矩阵：通过任意索引（即坐标）检索值的最有效方法是什么？

例如，在随机 5x5 矩阵中，如果我想要 (1,1) (2,3) 和 (4,5) 处的值，返回这些坐标处的值的最有效方法是什么？

例如，如果我在单独的矩阵中提供这些坐标，是否有一行 MATLAB 可以做这份工作吗？比如：

    x=rand(5,5);

    y=[[1,1];[2,3];[4,5]];

    z=x(y);

除了那不起作用。

然而，需要注意的是，由于各种原因，我无法使用线性索引 - 必须使用原始索引返回结果。这些矩阵的大小可能非常大，所以我也不想使用循环。

Answer 1

如果您反对使用线性索引和循环，那么唯一的其他选择，据我所知，是逻辑索引。但是，如果 y 始终采用您建议的形式，则您需要根据 y 中指定的索引创建一个逻辑矩阵。

您能解释一下为什么不允许线性索引吗？

无论如何，如果你想要一个非常愚蠢的答案（这是我所能提供的这么多信息）：

z = diag(x(y(:,1),y(:,2)))

当然，这将不必要地创建一个巨大的矩阵并从中提取对角线元素（您需要的元素） - 但它可以在一行中完成，等等。

编辑：如果限制使用线性在原始数据上建立索引，然后您可以使用线性索引创建一个逻辑矩阵并用它索引x。例如

% Each element of L is only one byte
L = false(size(x)); 
% Create the logical mask
L(sub2ind(size(x),y(:,1),y(:,2))) = true;
% Extract the required elements
z = x(L);

，类似地，对于 3 维矩阵：

x = rand(3,3,3);
y = [1 1 1;2 2 2;3 3 3];
L = false(size(x));
L(sub2ind(size(x),y(:,1),y(:,2),y(:,3))) = true;
z = x(L);

此外，逻辑索引应该比线性索引更快，因此除了构建掩码之外，您还处于良好状态。

Answer 2

为什么 sub2ind 不适合解决这个问题？我不认为需要逻辑掩码；例如应该

z = x(sub2ind(size(x),y(:,1),y(:,2)))

也可以。

Answer 3

在音乐停止很久之后才来参加聚会，但我无法控制自己...

如果由于工具箱中的错误而需要“完整”索引，并且工具箱一次仅加载矩阵的一部分，您可能会考虑遵循工具箱的行为。通过两件事可以获得大矩阵的巨大效率增益：

1）不要复制不需要复制的东西；例如，这包括创建一个原始矩阵大小的逻辑数组（尽管它名义上“高效”，但每个元素占用一个字节。如果您的矩阵太大而无法一次放入内存，即使是一个矩阵是 1/8，大小可能很重要）

2）保持内存一致性：访问“同一区域”的内存，或者发现自己因大量磁盘交换而减慢速度；即使所有内容都适合内存，保持“缓存一致性”也可以显着提高性能。如果您可以按照矩阵元素的存储顺序访问它们，那么速度会大大加快。

为了解决第一点，您需要寻找一种不需要创建完整副本的方法（因此雅各布的答案将会消失）。为了解决第二个问题，您需要在访问矩阵之前对索引进行排序 - 这样，可以“从同一内存块”访问的任何元素都将被排序。

下面将这两种技术结合起来。我假设 numel(y) << numel(x) - 换句话说，您只对查看 x 中相对较少的元素感兴趣。如果情况并非如此，对 y 向量进行排序实际上会减慢速度：

x = rand(5,5);
y = [1 1; 2 3; 4 5];
s = sub2ind(size(x), y(:,1), y(:,2)); % from the linear index we get access order
[ySorted yOrder] = sort(s);

% find the first, second index in the right access order:
y1 = y(yOrder, 1);
y2 = y(yOrder, 2);

% access the array using conventional indexing:
z = arrayfun(@(a,b)x(a,b), y1, y2);

% now put things back in the right order:
[rev revOrder] = sort(yOrder);
z = z(revOrder);

我使用 10000x10000 矩阵 x 和 5000x2 随机元素查找向量 y 对此进行了基准测试。与 Jacob 的代码相比，我得到

my method:   51 ms
his method: 225 ms

将查找向量的大小增加到 50000x2，这些值是

my method:  523 ms
his method: 305 ms

换句话说 - 哪种方法效果更好取决于您想要访问的元素数量。另请注意，使用逻辑 L 矩阵会隐式导致对大 x 矩阵的顺序访问 - 但在创建该矩阵期间，您会随机访问内存。 ..

顺便请注意，您遇到的一个问题是“是否有单衬” - 答案是“是”。如果您定义了数组 x 和 y，那么

z = arrayfun(@(a,b)x(a,b),y(:,1),y(:,2));

确实只是一行，并且不使用线性索引...