Поиск удаленных элементов в векторе в 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 существует гораздо более элегантное (и более дешевое!) Решение.


matlab repeat vector pruning
person Grasshoper    schedule 12.03.2019    source источник
comment
Какого размера X и сколько в нем уникальных элементов обычно?   -  person Luis Mendo    schedule 12.03.2019
comment
Не было бы проще, если бы этот процесс (я полагаю, функция) также возвращал удаленный элемент?   -  person Cris Luengo    schedule 12.03.2019
comment
Кроме того, всегда ли значения являются положительными целыми числами?   -  person Luis Mendo    schedule 12.03.2019
comment
@LuisMendo X обычно содержит сотни и не более тысячи, а значения «да» всегда положительны.   -  person Grasshoper    schedule 13.03.2019
comment
@CrisLuengo уверен, что да, проблема в том, что процесс, генерирующий значения X, требует огромного времени для вычислений, и я сейчас тщательно обрабатываю результаты.   -  person Grasshoper    schedule 13.03.2019
comment
@Grasshoper Я не понимаю ваш последний комментарий о процессе генерации значений X. Вы можете уточнить?   -  person beaker    schedule 13.03.2019
comment
И если X содержит всего несколько тысяч элементов, не будет ли find достаточно быстрым?   -  person beaker    schedule 13.03.2019
comment
@beaker Процесс, который генерирует значения X, представляет собой обрезку элементов огромной структуры в соответствии с некоторой стратегией и ограничениями. Не знаете, как использовать find() в данном контексте, вы предлагаете использовать цикл и подсчитывать частоту каждого элемента? Это построение гистограммы.   -  person Grasshoper    schedule 13.03.2019
comment
@Grasshoper Нет, я не предлагал гистограммный подход. Имея два массива X и Y, найдите первый элемент, где X ~= Y. Это первый удаленный элемент. Теперь применим к оставшимся массивам после несоответствия. Решение O(kn), где k — количество удаленных элементов, а n — длина X. Однако это, вероятно, медленнее и требует больше кода, чем решение histc(unique), предложенное здесь.   -  person beaker    schedule 13.03.2019
comment
@beaker да, понял.   -  person Grasshoper    schedule 14.03.2019
comment
@Grasshoper Маркировка как дубликат тогда   -  person Luis Mendo    schedule 14.03.2019

Ответы (2)


arrow_upward
2
arrow_downward

  1. Этот подход интенсивно использует память. Он вычисляет промежуточную матрицу размера NxM, где N — количество элементов X, а M — количество уникальных элементов X, используя неявное расширение. Это может быть возможно или нет, в зависимости от ваших типичных N и M.

    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

    Для версий Matlab до R2016b вам нужно 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));
person Luis Mendo    schedule 12.03.2019
comment
Это работает отлично и аккуратно! Благодарю вас! - person Grasshoper; 14.03.2019

arrow_upward
3
arrow_downward

Мне пришла в голову идея восстановить ввод из вывода путем вычитания обоих и повторения различных значений, которые затем являются индексами удаленных элементов.

% 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

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

Это подходящее решение, или я упускаю некоторые (очевидные) неэффективности?

person HansHirse    schedule 13.03.2019
comment
Спасибо. Решение кажется правильным, но решение, предоставленное @Luis-mendo, кажется более эффективным. - person Grasshoper; 14.03.2019