4

我有一个管理大量字符串的应用程序。字符串是类似路径的格式,有很多共同的部分,但没有明确的规则。它们不是文件系统上的路径,但可以这样考虑。我显然需要优化内存消耗,但又不会牺牲很大的性能。

我正在考虑 2 个选项:
- 实现一个compressed_string存储压缩数据的类,但我需要一个固定的字典,我现在找不到这个库。我不想要字节上的霍夫曼,我想要文字上的霍夫曼。
- 在字符串部分实现某种flyweight模式。

这个问题看起来很常见,我想知道最好的解决方案是什么,或者是否有人知道针对此问题的库。

谢谢

4

2 回答 2

1

尽管为您的问题调整特定算法可能很诱人,但这可能需要不合理的时间和精力,而标准压缩技术将立即为您解决内存消耗问题提供极大的帮助。

处理此问题的“标准”方法是将源数据分块为小块(例如 256KB),并单独压缩它们。将数据访问到块中时,需要先对其进行解码。因此,最佳块大小实际上取决于您的应用程序,即应用程序流越多,块越大;另一方面,随机访问模式越多,块大小越小。

如果您担心压缩/解压缩速度,请使用高速算法。如果解压缩速度是最重要的指标(访问时间),那么像 LZ4 这样的东西将为您提供大约 1GB/s每个内核的解码性能,因此这让您了解每秒可以解码多少块。

如果只看解压速度,可以使用高压缩变体LZ4-HC,压缩比提升30%左右,解压速度也有所提升。

于 2011-10-13T09:23:16.427 回答
0

字符串是类似路径的格式,有很多共同的部分,但没有明确的规则。

从某种意义上说,它们是形式name的层次结构中的定位器, ( separator , name )*? 如果是这样,您可以使用interning:将名称部分存储为char const *指向字符串池的元素。这样,您可以有效地将使用n次的名称压缩到刚好超过n * sizeof(char const *) + strlen(name)字节。完整路径将成为一系列实习名称,例如std::vector.

sizeof(char const *)这在 64 位硬件上似乎很大,但您也节省了一些分配开销。或者,如果您出于某种原因知道您永远不需要超过 65536 个字符串,您可以将它们存储为

class interned_name
{
    uint16_t tab_idx;

  public:
    char const *c_str() const
    {
        return NAME_TABLE[tab_idx];
    }
};

哪里NAME_TABLEstatic std::unordered_map<uint16_t, char const *>

于 2011-10-13T08:17:11.420 回答