3

我需要存储一个整数列表列表。例如，X[1]应该能够包含[1 3 5]，而X[2]可以包含[1 2]. 最好的解决方案是什么？单元阵列？

背后故事：

对于一个项目，我预先计算了 N 条线和 M 个立方体之间的交点。这些是通过两种方式检索的：给定一个行索引，我想要一个它通过的立方体列表，给定一个立方体索引，我想要一个通过它的行列表。

典型值为 N=2^24 和 M=2^18，这意味着交集矩阵 (NxM) 是不可能的。幸运的是，平均线仅通过 M^(1/3)=2^6 个立方体。目前，我将结构存储为 NxM^(1/3) 矩阵，因此这X(n,:)是第 n 行穿过的立方体向量（用零填充）。

这适用于检索给定列表索引的多维数据集，但事实证明我的代码的瓶颈是检索给定多维数据集索引的行。（我用find(X==m)m 是立方体索引来做。）我无法创建相反的矩阵，因为穿过单个立方体的线数可能非常高，即使它平均很低。

4

1 回答 1

11

通常，单元阵列是此问题的正确答案。这是最简单的情况。一些示例用途：

%Writes
X = {[1], [1 2 3], [1 2]};
X{4} = [1 2 3 4];

%Reads
a = X{1}
b = cat(2,X{:});
c = X([2 4]);

然而，这并不是唯一的答案。

您可以使用一个结构数组，每个结构都有一个名为.indexes（或根据您的问题的适当名称）的字段。如果您希望将其他信息附加到列表列表中，这将提供更多的灵活性，例如可以将立方体位置添加为.position字段。示例用途：

%Writes
X(1).indexes = 1;
X(2).indexes = [1 2 3];
X(3).indexes = [1 2];

%Reads
a = X(1).indexes
b = cat(2,X.indexes)
c = X([2 4]);

您还可以使用containers.Map对象。这与结构数组具有相同的优点，但在引用对象的方式上具有更大的灵活性。而当使用结构数组时，结构是通过索引引用的，使用容器。映射对象可以使用任意数字（不是接近 1 的整数）或名称（对于 2^24 情况不实用）来引用每个结构。这可能不是您的最佳答案，但参考示例如下：

%Writes
X = containers.Map('keyType','uint32','valueType','Any');
X(1) = [1];
X(2) = [1 2 3];
X(3) = [1 2];
X(4) = [1 2 3 4];

%Reads
a = X(1);
b = cat(2,X.values);

最后，可能值得为此定义一对自定义类。这需要更多的工作来设置，但可能是让恒定时间查找到预先计算的值的最简单方法。下面是一些让您开始走这条路的代码。

%A start at cube.m.  Most of the code handles smartly reallocating the list of lines.
classdef cube < handle
    properties (SetAccess = private, GetAccess = public)
        numLines = 0
        intersectingLines = [];
    end
    methods (Access = public)
        function addLine(self, lineToAdd)
            if self.numLines == 0
                self.intersectingLines = lineToAdd;
                self.numLines = 1;
            elseif self.numLines>=length(self.intersectingLines)
                self.intersectingLines(length(self.intersectingLines)*2) = line();
                self.intersectingLines(self.numLines+1) = lineToAdd;
                self.numLines = self.numLines+1;
            else
                self.intersectingLines(self.numLines+1) = lineToAdd;
                self.numLines = self.numLines+1;
            end
        end
    end
end

%A start at line.m.  A near copy/paste of cube.m
    classdef line < handle
    properties (SetAccess = private, GetAccess = public)
        numCubes = 0
        intersectingCubes = [];
    end
    methods (Access = public)
        function addCube(self, cubeToAdd)
            if self.numCubes == 0
                self.intersectingCubes = cubeToAdd;
                self.numCubes = 1;
            elseif self.numCubes>=length(self.intersectingCubes)
                self.intersectingCubes(length(self.intersectingCubes)*2) = cube();
                self.intersectingCubes(self.numCubes+1) = cubeToAdd;
                self.numCubes = self.numCubes+1;
            else
                self.intersectingCubes(self.numCubes+1) = cubeToAdd;
                self.numCubes = self.numCubes+1;
            end
        end
    end 
end

要按照编写的方式使用这些类，您需要add成对调用方法（以后的明显升级是正确交叉添加。同时（因为我很懒），我们将定义一个辅助函数。 

function crossAdd(cube, line)
cube.addLine(line);
line.addCube(cube);

现在示例使用是：

%Create two class arrays of cubes and lines
allCubes(1) = cube;
allCubes(2) = cube;
allCubes(3) = cube;
allCubes(4) = cube;

allLines(1) = line;
allLines(2) = line;
allLines(3) = line;
allLines(4) = line;

%Define links (matching above "writes" examples)
crossAdd(allCubes(1), allLines(1));
crossAdd(allCubes(2), allLines(1));
crossAdd(allCubes(2), allLines(2));
crossAdd(allCubes(2), allLines(3));
crossAdd(allCubes(3), allLines(1));
crossAdd(allCubes(3), allLines(2));
crossAdd(allCubes(4), allLines(1));
crossAdd(allCubes(4), allLines(2));
crossAdd(allCubes(4), allLines(3));
crossAdd(allCubes(4), allLines(4));

%Use linked values
aLines = allCubes(1).getLines   %Only one intersecting line
bLines = allCubes(2).getLines   %Three intersecting lines
cubesFromSecondLine = bLines(2).getCubes %Three cubes here (2, 3, 4)

顺便说一句，我们实际上只是利用了< handle类作为传递引用的事实，因此我们可以使用复杂的、交叉链接的数据结构。

于 2012-12-07T16:15:40.123 回答