2

这是我的问题定义：我有一个包含七百万个索引的数组，每个索引都包含一个标签。因此，为简单起见，这是我正在处理的示例数组：[1 2 3 3 3 5 2 1 7]。

我需要遍历这个数组，每次遇到一个标签时，将标签的位置输入到一个“集合”中，并与所有其他标签相同。由于数组如此之大，我只想在任何给定点访问特定标签的位置，所以假设我只想访问 3 的位置并处理这些位置并将它们更改为 5，但我想做更多不仅是一项操作，而且不仅如此，我还想在所有标签上分别进行。在像我的示例中这样的小数组中，坚持使用数组似乎微不足道。但是，对于 700 万个点的数组，完成对所述标签的搜索然后对它们进行操作要花费更多的时间。

为了消除混淆，使用我的示例，我希望示例数组为我提供以下内容：

  • 1 映射到包含 0 和 7 的集合
  • 2 映射到包含 1 和 6 的集合
  • 3 映射到包含 2、3 和 4 的集合
  • 5 映射到包含 5 的集合

本来我是对原数组做我的处理，简单的对数组进行操作。这大约需要 30 秒来确定每个标签的相应索引的数量（所以我能够确定 1 的大小是 2，6 的大小是 2，3 的大小是 3，等等。但是，它没有使用此方法生成所述标签的位置。因此，在我的其余处理过程中也增加了时间来查找每个标签的位置，尽管它通过添加终端来加速，一旦它找到了引用标签的所有索引, 停止搜索。

下一步，我使用了 a map<int,set<int>>，但这最终导致时间增加至约 100 秒，但随后的处理时间减少了，但不足以证明时间的大幅增加是合理的。

我还没有实现它，但作为一个额外的步骤，我计划尝试初始化一个集合数组，其索引对应于标签并尝试使用这种方法。

我也尝试过 hash_maps 也无济于事。Unordered_sets 和 unordered_maps 不包含在 Visual Studio 2005 的 STL 中，因此我没有使用这两个结构实现上述内容。

要点：我已经对数组进行了预处理，使得我知道最大标签，并且所有标签都是连续的（最小标签和最大值之间没有间隙）。但是，它们随机分散在原始阵列中。这可能证明在初始化一组大小的数据结构时很有用。与标签对应的索引的顺序并不重要。标签在给定数据结构中的顺序也不重要。

编辑：对于背景，数组对应于二进制图像，我实现了二进制顺序标记以输出与 UINT16 的二进制图像大小相同的数组，所有二进制 blob 都被标记。我现在要做的是尽可能有效地获取构成每个 blob 的点的地图。

4

2 回答 2

1

你为什么要使用如此复杂的数据结构来完成这项任务？只需创建一个向量向量来存储每个标签的所有位置即可。您还可以通过预处理每个标签所需的空间来避免烦人的向量内存分配。像这样的东西：

vector <int> count(N);
for(size_t i = 0; i < N; ++i)
    ++count[dataArray[i]];
vector < vector <int> > labels(N);
vector <int> last(N);
for(size_t i = 0; i < N; ++i)
    labels[i].resize(count[i]);
for(size_t i = 0; i < N; ++i) {
    labels[dataArray[i]][last[dataArray[i]]] = i;
    ++last[dataArray[i]];
}

它会在 O(N) 时间内工作，对于你的 700 万个整数来说，这看起来像 1 秒。

于 2013-06-03T17:14:04.243 回答
0

我不一定会为此使用通用映射（或哈希表）。

我最初的直觉是，我将创建一个包含 700 万个（或任何 N 个）位置的第二个数组“位置”，以及对应于范围 [min-label, max-label] 的第三个数组“last_position_for_index”。请注意，这几乎肯定会比任何类型的地图占用更少的存储空间。

将 last_position_for_index 的所有条目初始化为某个保留值，然后您可以使用类似（未经测试）的方式遍历您的数组：

for (std::size_t k = 0; k<N; ++k) {
  IndexType index = indices[k];
  positions[k] = last_position_for_index[index-min_label];
  last_position_for_index[index-min_label] = k;
}
于 2013-06-03T17:01:01.277 回答