在matlab中查找向量中删除的元素

Finding removed elements in a vector in matlab

我有一个迭代和随机修剪一个巨大的整数向量的过程,我想找出在每次迭代之间删除了哪些元素。这个向量有很多重复,使用 ismember() 和 setdiff() 对我帮助不大。

作为示例,如果 X = [1,10,8,5,10,3,5,2]:

step 0: X = 1,10,8,5,10,3,5,2
step 1: X = 1,10,8,10,3,5,2 (5 is removed)
step 2: X = 1,10,8,3,2 (10 and 5 are removed)
step 3: X = 10,8,3,2 (1 is removed)
step 4: X = 2 (10, 8 and 3 are removed)
step 5: X = [] (2 is finally removed)

我的目标是找到在每个步骤中删除的元素(即 5 然后,10 和 5 等等)。我可能会在步骤之间使用 hist(X, unique(X)) 找到过于复杂的解决方案,但我认为在 matlab 中存在更优雅(也更便宜!)的解决方案。

  1. 这种方法占用大量内存。它计算大小为 NxM 的中间矩阵,其中 NX 的元素数,M 是 [= 的唯一元素数17=],使用 implicit expansion。这可能可行或不可行,具体取决于您的典型 NM.

    X = [1,10,8,5,10,3,5,2];
    Y = [8,10,2,1]; % removed 10, 5, 5, 3. Order in Y is arbitrary
    u = unique(X(:).');
    removed = repelem(u, sum(X(:)==u,1)-sum(Y(:)==u,1));
    

    给予

    removed =
         3     5     5    10
    

    对于 R2016b 之前的 Matlab 版本,您需要 bsxfun 而不是隐式扩展:

    removed = repelem(u, sum(bsxfun(@eq,X(:),u),1)-sum(bsxfun(@eq,Y(:),u),1));
    
  2. 如果X中的值总是正整数更有效的方法可以是使用,使用 sparse 来计算每个元素出现的次数:

    X = [1,10,8,5,10,3,5,2];
    Y = [8,10,2,1]; % removed 10, 5, 5, 3. Order in Y is arbitrary
    removed = repelem(1:max(X), sparse(1,X,1) - sparse(1,Y,1));
    

我想到了通过将两者相减并迭代不同的值来从输出中恢复输入的想法,这些值就是要找到的已删除元素的索引。

% Input.
X = [1, 10, 8, 5, 10, 3, 5, 2];

% Remove indices for the given example.
y = { [4], [4 6], [1], [1 2 3], [1] };

% Simulate removing.
for k = 1:numel(y)

  % Remove elements.
  temp = X;
  temp(y{k}) = [];

  % Determine number of removed elements.
  nRemoved = numel(X) - numel(temp);

  % Find removed elements by recovering input from output.
  recover = temp;
  removed = zeros(1, nRemoved);
  for l = 1:nRemoved
    tempdiff = X - [recover zeros(1, nRemoved - l + 1)];
    idx = find(tempdiff, 1);
    removed(l) = X(idx);
    recover = [recover(1:idx-1) X(idx) recover(idx:end)];
  end

  % Simple, stupid output.
  disp('Input:');
  disp(X);
  disp('');
  disp('Output:');
  disp(temp);
  disp('');
  disp('Removed elements:');
  disp(removed);
  disp('');
  disp('------------------------------');

  % Reset input.
  X = temp;

end

给定示例的输出:

Input:
    1   10    8    5   10    3    5    2

Output:
    1   10    8   10    3    5    2

Removed elements:
 5

------------------------------
Input:
    1   10    8   10    3    5    2

Output:
    1   10    8    3    2

Removed elements:
   10    5

------------------------------
Input:
    1   10    8    3    2

Output:
   10    8    3    2

Removed elements:
 1

------------------------------
Input:
   10    8    3    2

Output:
 2

Removed elements:
   10    8    3

------------------------------
Input:
 2

Output:
[](1x0)

Removed elements:
 2

------------------------------

这是一个合适的解决方案,还是我遗漏了一些(明显的)效率低下的地方?