1

是否使用 NULL 终止字符串 (SZ) 或长度前缀字符串 (LPS) 似乎是一个热门话题。确实，我们甚至在这里对这个话题提出了问题。

所以我发生了一些事情。我们可以两者都用一点吗？我的意思是，很明显，你不能制作一个 LPS & SZ (LPSZ?) 字符串而不删除其中一个或另一个的一些很棒的东西。

然而，关于 SZ 的最大抱怨似乎是操作所需的时间，因为字符串长度测量需要很长时间。我对此有一个想法：

使所有字符串 SZ。但是，我们也可以将字符串 mod 256 的长度（即：）存储在字符串len % 256前面的单个字节中。虽然它不会降低操作的复杂性，但它可能会显着提高速度，代价是增加一个字节。

以下是该方案的主要优点：

  1. 不限于任何特定尺寸
  2. 比普通 SZ 更快（高达 256 倍）
  3. 兼容所有不同的内存大小
  4. 小字符串仍然非常节省空间（没有浪费的字节len）
  5. 没有字节顺序问题
  6. 可跨机器移植（见 3 和 5）

这就是strlen ()在这个方案下的样子（显然，你会用别的名字命名它，因为你会创建一个不同的库）：

size_t ppsz_strlen (const char *s) {
    // get LPS
    size_t = ((uint8_t *) s)[-1];


    // check for SZ across every 256 byte interval
    for (x = x; s[x]; x += 256)
        continue;

    return x;
}

一个合适的名称可能是 PPSZ（部分前缀空终止字符串）。

对我来说，这似乎是一个合理的权衡：一个字节用于相当大的加速度。当然，有人可能会问：为什么不是两个、四个或八个字节呢？我的回答是，程序中的大多数字符串都不会变得太大，因为向前跳过 65536、167772162 ** 32或2 ** 64变得太有价值。对于其中一些情况，实际上可能是考虑拆分字符串的好时机。特别是如果一个字符串溢出超出 64 位寻址空间的大小。

无论如何，我想知道是否有人对这个概念有一些想法。我很肯定，为什么我以前没有在实践中看到过这个概念，我可能错过了一些东西。

感谢您发现任何建议或问题！

编辑：删除背景信息以使问题的意图更加明显（我的算法中是否存在我可能遗漏的任何潜在缺陷等）

注意：此算法主要用于帮助解决 SZ 中的速度问题

4

0 回答 0