3

我在 Matlab 中有一个数组。我用自然数对数组中的每个条目进行编号。所以我在数组中形成了等价关系。

例如，

array   = [1 2 3 5 6 7]
classes = [1 2 1 1 3 3].

我想获取单元格数组：i-th 单元格数组的位置与i-th 初始数组条目相关联，并显示哪些元素与该条目在一个类中。对于上面的示例，我会得到：

{[1 3 5], [2], [1 3 5], [1 3 5], [6 7], [6 7]}

使用for循环可以轻松完成，但还有其他解决方案吗？如果它的工作速度比 快，那就太好了，初始数组的大小O(n^2)在哪里。n

Edit. 如果我知道将已排序数组拆分为具有相等元素索引的单元格的方法，问题将得到解决O(n)。

array  = [1 1 1 2 3 3]
groups = {[1 2 3], [4], [5 6]}
4

3 回答 3

3

不确定复杂性，但accumarray单元格输出对于根据类的唯一值拆分数组很有用：

data = sortrows([classes; array].',1) %' stable w.r.t. array
arrayPieces = accumarray(data(:,1),data(:,2)',[],@(x){x.'})
classElements = arrayPieces(classes).'

关于将排序数组拆分为 indeces 的单元格：

>> array  = [1 1 1 2 3 3]
>> arrayinds = accumarray(array',1:numel(array),[],@(x){x'})' %' transpose for rows
arrayinds = 
    [1x3 double]    [4]    [1x2 double]
>> arrayinds{:}
ans =
     1     2     3
ans =
     4
ans =
     5     6
于 2014-03-15T20:38:52.617 回答
1

我不知道如何在完全没有 for 循环的情况下做到这一点，但您可以使用 、 和 的组合sort来diff组织find和划分等价类标识符。O(n)这将为您提供一个主要矢量化的解决方案，其中M 代码级 for 循环是n类的数量，而不是整个输入数组的长度。这在实践中应该很快。

这是一个使用一些索引修改的粗略示例。当心; 由于我刚刚解决了这个问题，因此某处可能存在一个错误的边缘案例错误。

function [eqVals,eqIx] = equivsets(a,x)
%EQUIVSETS Find indexes of equivalent values

[b,ix] = sort(x);
ixEdges = find(diff(b)); % identifies partitions between equiv classes
ix2 = [0 ixEdges numel(ix)];
eqVals = cell([1 numel(ix2)-1]);
eqIx = cell([1 numel(ix2)-1]);
% Map back to original input indexes and values
for i = 1:numel(ix2)-1
    eqIx{i} = ix((ix2(i)+1):ix2(i+1));
    eqVals{i} = a(eqIx{i}); 
end

我在输出中包含了索引，因为它们通常比值本身更有用。你会这样称呼它。

% Get indexes of occurrences of each class
equivs = equivsets(array, classes)
% You can expand that to get equivalences for each input element
equivsByValue = equivs(classes)

首先为每个类构建列表然后扩展它们以匹配输入索引会更有效。您不仅只需执行一次工作，而且当您使用 将b = a(ix)小单元阵列扩展到更大的单元阵列时，Matlab 的写时复制优化最终将重用底层数字 mxArrays 的内存，因此您得到一个内存中更紧凑的表示。

unique()在使用或数据库时，这种转换会经常出现。对于我使用过的决策支持系统和数据仓库风格的东西，它无处不在。我希望它内置在 Matlab 中。（最近几年它可能已被添加到数据库或时间序列工具箱之一中；我落后了几个版本。）

实际上，如果此性能对您的代码至关重要，您还可以考虑使用 Java 或 C MEX 函数并在那里实现它。但是，如果您的数据集是低基数——也就是说，有少量的类/不同的值，比如numel(unique(classes)) / numel(array)往往小于 0.1 左右——M 代码实现可能会很好。

于 2014-03-15T20:42:32.107 回答
1

对于第二个问题：

array  = [1 1 1 2 3 3]; %// example data

  1. 用于diff查找每次运行相等值的结束，并从中构建组：

    ind = [0 find(diff([array NaN])~=0)];
groups = arrayfun(@(n) ind(n)+1:ind(n+1), 1:numel(ind)-1, 'uni', 0);

  2. 使用相同的方法unique：

    [~, ind] = unique(array);
ind = [0 ind];
groups = arrayfun(@(n) ind(n)+1:ind(n+1), 1:numel(ind)-1, 'uni', 0);

不过，我还没有测试过复杂度是否为 O(n)。

于 2014-03-16T02:05:26.070 回答