合并排序对

Question

我有两个（或更多，但如果求解两个，则可以求解任何数字）2×N 矩阵，它们表示具有 x（第一行）和 y（第二行）坐标的点。这些点总是按递增的 x 坐标排序。我想做的是我想将这两个矩阵合并成一个 3×N 矩阵，这样如果两个点（每个矩阵中的一个点）具有相同的 x 坐标，它们将在新矩阵中形成一列，第一个行是 x 坐标，第二行和第三行是两个 y 坐标。但是，如果一个矩阵中有一个点的 x 坐标不同于第二个矩阵中的所有其他点，我仍然希望放置完整的 3 元素列，以便 x 坐标仍然排序并且缺失值来自另一个矩阵替换为 x 坐标较低的最近值（如果存在 none，则为 NaN）。

最好举例说明。

第一个矩阵：

1  3  5  7  % x coordinate
1  2  3  4  % y coordinate

第二个矩阵：

2  3  4  7  8  % x coordinate
5  6  7  8  9  % y coordinate

想要的结果：

1    2  3  4  5  7  8  % x coordinate
1    1  2  2  3  4  4  % y coordinate from first matrix
NaN  5  6  7  7  8  9  % y coordinate from second matrix

我的问题是，如何在 matlab/octave 和 numpy 中有效？（实际上是因为我总是可以 "manually" 使用循环，但这似乎不对。）

Answer 1

你的例子：

a = [1 3 5 7; 1 2 3 4];
b = [2 3 4 7 8; 5 6 7 8 9];

% Get the combined (unique, sorted) `x` coordinates 
output(1,:) = unique([a(1,:), b(1,:)]);
% Initialise y values to NaN
output(2:3, :) = NaN;   
% Add x coords from `a` and `b`
output(2, ismember(output(1,:),a(1,:))) = a(2,:);
output(3, ismember(output(1,:),b(1,:))) = b(2,:);
% Replace NaNs in columns `2:end` with the previous value. 
% A simple loop has the advantage of capturing multiple consecutive NaNs.
for ii = 2:size(output,2)
    colNaN = isnan(output(:, ii));
    output(colNaN, ii) = output(colNaN, ii-1);
end

如果你有超过 2 个矩阵（如你的问题中所建议的）那么我建议

将它们存储在一个元胞数组中，并循环遍历它们以调用 ismember，而不是对每个矩阵硬编码一个代码行。
NaN 替换循环已经针对任意数量的行进行了矢量化。

这是任意数量矩阵的通用解决方案，用 a 和 b 进行了演示：

mats = {a, b};
cmats = horzcat(mats);
output(1, :) = unique(cmats(1,:));
output(2:numel(mats)+1, :) = NaN;
for ii = 1:size(mats)
    output(ii+1, ismember(output(1,:), mats{ii}(1,:))) = mats{ii}(2,:);
end
for ii = 2:size(output,2)
    colNaN = isnan(output(:,ii));
    output(colNaN, ii) = output(colNaN, ii-1);
end

Answer 2

此版本使用集合操作：

a=[...
1  3  5  7;... 
1  2  3  4];

b=[...
2  3  4  7  8;...
5  6  7  8  9];

% compute union of x coordinates
c = union(a(1,:),b(1,:));

% find indices of x of a and b coordinates in c
[~,~,ia] = intersect(a(1,:),c); 
[~,~,ib] = intersect(b(1,:),c);

% create output matrix
d = NaN(3,numel(c));
d(1,:) = c;
d(2,ia) = a(2,:);
d(3,ib) = b(2,:);

% fill NaNs
m = isnan(d);
m(:,1) = false;
i = find(m(:,[2:end,1])); %if you have multiple consecutive nans you have to repeat these two steps
d(m) = d(i);

disp(d);

Try it online!

Answer 3

策略可以用interp1和关键字'previous'来实现（不介意大还是小也可以选择'nearest'）和'extrap' 允许外推。

定义矩阵

a=[...
1  3  5  7;... 
1  2  3  4];

b=[...
2  3  4  7  8;...
5  6  7  8  9];

然后求插值点

x = unique([a(1,:),b(1,:)]);

并插值

[x ; interp1(a(1,:),a(2,:),x,'previous','extrap') ; interp1(b(1,:),b(2,:),x,'previous','extrap') ]

时间结果：

我在

上测试了算法

n = 1e6;
a = cumsum(randi(3,2,n),2);
b = cumsum(randi(2,2,n),2);

并得到：

沃尔菲：1.7473 秒
缺陷：0.4927秒
我的：0.2757 秒

合并排序对

Merging sorted pairs

matlab

numpy

octave