C++ : Data structure for fast searching

Question

以下是我的场景:

我必须保留扩展 ASCII 的所有 3 字节组合，如下所示:

{ { (a,a,a),(a,a,b),..........(z,z,z) } }

所有这些组合产生一大组 256*256*256 个值

在我的算法中，碰巧在每次迭代之后，大集合都会分解成这样的东西:

 {(a,a,a), (a,a,b)}
 {(a,a,c)}
.
.
.
.
{(z,z,z)}

我正在使用数组集的 vector 来实现它。

vector<set<array<char,3> > > Partition;

使用它的原因是一个大集合会分解成子集。这些子集的数量是未知的，每次迭代后子集的数量可能会增加，因此我使用 vector 。然后子集不应包含任何元素两次，因此我正在使用 set 和 array 用于保留 3 个字符。

使用上述数据结构的问题是计算结果需要花费大量时间。

我需要有关数据结构的建议，这对我的情况来说更有效。

我的算法的更多解释:

{(a,a,a),(a,a,b)........ (z,z,z)}

所有这些三元组都是无序映射的键。所有这些三元组都对应这样一个特定的值

(a,a,a)           value=2
(a,a,b)           value=2
(a,a,c)           value=3
(a,a,d)           value=2
.
.
.
.
.

现在，我运行我的算法，想根据值(value)知道它们可以压缩多少:像这样

{(a,a,a) ,(a,a,b)  }          value=2
(a,a,c)                       value=3
{(a,a,d),......}              value=2

为什么我必须为 value=2 创建一个单独的子集，因为根据我的算法，每当我以前的值与当前值不同时，我必须创建一个新的集合。

Answer 1

嗯，你很关心3 * 8b所以有24位值。而不是 {0, 0, 0}你可以有一个整数0而不是 {'a', 'a', 'a'}你可以有 0x616161因为'a' == 0x61

所有这些整数都可以存储在 std::map 中其中由 3 个符号组成的整数是关键。或者你可以使用数组 ValueType arr[256*256*256] .我建议使用数组，但是如果您只有几个值，则可以使用 map。

从 int 转换到 3 个字符，您可以使用按位运算 <<和 >>了解它们 here和 here .但我希望您了解位移位。