1

给定几组元素，例如：

int set1[5] {5601, 935, 4153, 2195, 422};
int set2[5] {5601, 935, 23, 44, 422};
int set3[5] {4205, 935, 4153, 2195, 15};
int set4[5] {4205, 589, 4015, 44, 422};

在顺序很重要的情况下（即 1、2、3 与 2、1、3 不同），定位特定集合的有效算法是什么？例如，您要定位：

int value[5] {5601, 935, 23, 44, 422};

注意事项：

  1. 新集合的插入成本不是问题，因此它们可以存储在任何数据结构中，以优化搜索时间。

  2. 每个集合将包含 1 到 1,000,000 个元素（大约，并且将有 1 到 1000 个集合（再次，大约）。但是，对于任何给定的集合，元素的数量将始终相同（例如，如果一个set 有 10 个元素，那么所有的集合将有 10 个元素）。

后续问题，我将在 C++ 中实现它，所以我有兴趣找出任何推荐的算法，它们是否存在于开源 C++ 库（最好是 STL、Boost 或 QT，但我会考虑其他人也是）。

4

4 回答 4

5

如果顺序很重要，那么您正在查看的是序列，而不是集合。术语很重要。

由于您只考虑大约 1,000 个序列，因此将它们存储在哈希表中应该很容易，并且性能良好。我会考虑构建一个字符串来表示每个序列，例如，通过连接每个元素的字符串表示形式，加上某种分隔符，然后对其进行散列处理。

于 2012-08-01T17:28:56.247 回答
4

使用 astd::vector<set_type>来存储集合。将所有套件插入容器中。使用 对容器进行排序std::sort。std::binary_search使用（或者std::lower_bound如果您需要元素的迭代器）查找元素。

您使用的类型set_type取决于每个集合中的元素数量。如果已知元素的数量很小，那么std::array<T, N>就足够了；否则，考虑std::vector<T>。

于 2012-08-01T17:27:40.313 回答
0

定义集合的顺序，然后将它们插入树中。或者定义一个哈希码和一个比较器并对它们进行哈希表。

于 2012-08-01T17:26:27.713 回答
0

在这种情况下，我会使用哈希表。您将有访问时间O(1)（最坏的情况是O(n)，但有一个好的哈希函数，这不是问题）

因此，如果您的 Hashtabel 足够大并且您不必担心空间问题，这绝对是最快的搜索方式。（考虑二分搜索在O(log(n))）

哈希表仅在新 C++0x 标准的 STL 中可用。见STL::TR1

于 2012-08-02T22:52:08.830 回答