什么是计算子字符串的最快方法？

Question

我有一个巨大的“二进制”字符串，如：1110 0010 1000 1111 0000 1100 1010 0111.... 它的长度是4的倍数，可以达到500,000。我还有一个相应的数组：{14, 2, 8, 15, 0, 12, 10, 7, ...} （数组中的每个数字对应于字符串中的4位）。给定这个字符串、这个数组和一个数字N，我需要计算以下子字符串string.substr(4*N, 4)，即：当N=0时结果应为1110，当N=1时结果应为0010。我需要多次执行此任务，我的问题是计算此子字符串的最快方法是什么？一种方法是直接计算子字符串：string.substr(4*N, 4)。恐怕这种方法对于如此庞大的字符串来说效率不高。另一种方法是使用array[N].toString(2)，然后根据需要用零包装结果。我不确定这样做有多快。也许你有其他想法？

- Misha Moroshko

---

我不知道你从哪里得到 substr 不快的概念。我不确定你的要求，但在我进行的一个简单测试中，我创建了一个包含 500,000 个字符的字符串，然后从中随机选择了 100,000 次子字符串，用时约为 169ms。 - nickf

Answer 1

字符串从哪里来？为什么不将字符串表示为十六进制，然后将每个四位二进制数字节作为单个字符存储呢？（如果您想要，您显然可以将其压缩两倍，或者实际上，现在我想到了，四倍，因为Javascript字符串是16位Unicode）。然后找到一个单独的组将是一个“charAt()”调用，并且您只需要通过查找表将其扩展为二进制形式。

编辑-哦，好吧，你已经有一个数组。在这种情况下根本不需要做子字符串处理；这太疯狂了。只需获取数组元素并通过查找数组将其转换为4位二进制数字字符串即可。

- Pointy

Answer 2

你可以考虑将你的大字符串表示为Rope数据结构。Rope基本上是一棵二叉树，其叶子节点是字符数组。树中的一个节点有左孩子和右孩子，左孩子是字符串的前半部分，而右孩子是后半部分。

通过使用Rope，子字符串操作的复杂度变为对数级别，而不是普通字符串的线性级别。

- luvieere

---

如果他要这样拆分字符串，为什么不将其拆分成一个平坦的数组呢？那么他的查找时间就是常数时间，甚至不是对数时间。 - Pointy

@Pointy 如果他有一个数组而不是字符串，那就可以工作。但是将字符串拆分成数组仍然需要调用substring来获取各个部分。 - luvieere

Answer 3

如果你想要填充它，你可以这样做：

var elem = array[N]
var str = "" + ((elem>>3)&1) + ((elem>>2)&1) + ((elem>>1)&1) + (elem&1);

- Eric

---

他说他有一个 字符串，而不是数组。你的代码假设一个数字数组。此外，你得到了二进制字符串的反向结果。 - Pointy

我也有一个相应的数组...不过关于位的方向是个好点。 - Eric

@Josh 不，JavaScript 中它们并不是真正的数组。它们没有数组所拥有的方法。 - Pointy

然而，OP说他有一个数组和一个字符串。 - Eric

@Pointy 当然，但我不明白这与OP的问题有什么关系。 - Josh Stodola

这并不是，但有一天可能会有其他人阅读此页面！ - Pointy

Answer 4

数组已经完全拥有你需要的东西了，只不过你需要以二进制格式打印它。幸运的是，JavaScript 中有 sprintf 函数可供使用。

- mpez0