使用MATLAB查找坐标列表中每个坐标的第一个和最后一个索引。

Question

我有一组坐标列表 (x,y)，需要找到列表中每个坐标第一次和最后一次出现的索引。 例如（在我的用例中，我有大约 30M 个坐标）：

x = [1 3 7 1 3];
y = [5 1 6 5 1];
first = [1 2 3 1 2];
last  = [4 5 3 4 5];

我使用矩阵和循环实现了它，代码如下，但是速度较慢：

x1 = min(x);
y1 = min(y);
x2 = max(x);
y2 = max(y);
tic
Mlast = zeros(y2-y1+1, x2-x1+1);
Mfirst = Mlast;

ind = sub2ind(size(Mlast),y-y1+1, x-x1+1);

for i1=1:length(ind)
    first = Mfirst(ind(i1));

    if first == 0
        first = i1;
    end

    Mlast(ind(i1)) = i1;
    Mfirst(ind(i1)) = first;
end

我尝试将整个过程向量化，但只有在Mlast上成功了：

ind = sub2ind(size(Mlast),y-y1+1, x-x1+1);
t = (1:length(x))';
Mlast(ind) = t;
Mfirst = ???

有没有一种方法也可以获取第一次出现的内容呢？

- MiB_Coder

---

find(x==y, 1, 'first') finds the first entry upholding the criterion. Other useful functions might be unique() - Adriaan

Answer 1

unique函数可以实现这一功能：

[~, b, c] = unique([x(:) y(:)], 'rows', 'first');
first = b(c).';
[~, b, c] = unique([x(:) y(:)], 'rows', 'last');
last = b(c).';

- Luis Mendo

---

确实可以工作，但它的速度大约比带有循环的版本慢20倍。 - MiB_Coder

奇怪，我本来以为“unique”会非常快。 - Luis Mendo

@LuisMendo：是的，我的错。 - Cris Luengo

Answer 2

假设坐标是正整数，特别是当坐标范围较小时，您可以使用accumarray函数：假定坐标为正整数且范围较小，可使用accumarray函数：最初的回答。

x1 = min(x);
y1 = min(y);
x2 = max(x);
y2 = max(y);
sz = [y2-y1+1, x2-x1+1];
ind = sub2ind(sz,y-y1+1, x-x1+1);

ifirst = accumarray(ind(:), 1:numel(ind), [], @min);
ilast  = accumarray(ind(:), 1:numel(ind), [], @max);
Mfirst = ifirst(ind);
Mlast  = ilast(ind);

如果需要更高的范围，您可以使用sparse选项：

ifirst = accumarray(ind(:), 1:numel(ind), [], @min,[],1);
ilast  = accumarray(ind(:), 1:numel(ind), [], @max,[],1);

- rahnema1

---

它能工作！但是它的速度大约比循环实现慢30倍。不过了解accumarray还是很有趣的... - MiB_Coder

Answer 3

如果你有3000万个点，那么可能没有足够的内存来使用这种方法...但对于较小的数组来说，它非常快。

x = [1 3 7 1 3];
y = [5 1 6 5 1];

xy = cat( 3, x, y );

chk = all( xy == permute( xy, [2 1 3] ), 3 );

[~,first] = max( chk );
[~,last] = max( flipud( chk ) );
last = size(chk,1) - last + 1;

---

编辑 您也可以使用findgroups，并循环遍历唯一坐标而不是每个坐标，从而拥有可能更短的循环...

x = [1 3 7 1 3];
y = [5 1 6 5 1];

g = findgroups( x, y );   
first = zeros( size( x ) );
last = first;
for ii = 1:max(g)
    idx = (ii==g);
    first( idx ) = find( idx, 1, 'first' );
    last( idx ) = find( idx, 1, 'last' );
end 

---

编辑2 我认为相对于其他答案，这两个答案都比较慢...

- Wolfie