处理Javascript中的元组:容器数据结构

Question

无论出于什么原因，我正在编写的算法都处理数字元组(想想固定长度的字符串，但每个字符都是一个数字(。例如，如果今天我的元组的长度是4，我想要一个类似的抽象数据

// Think of Vector<Tuple<4>>
const vector_of_tuples = [
[0, 0, 0, 0],
[0, 1, 4, 6],
[9, 8, 7, 2],
[5, 6, 7, 8],
];

现在，(固定长度的(元组是我的基本数据类型，我想用它们制作向量，在地图中用作键，等等。(在地图中使用它们作为键是另一天的问题(。

如果我的代码多次创建元组的新向量，就会产生大量垃圾，因为每个元组都分配自己的存储空间。创建一个具有n个元组的向量会导致O(n(分配。在这方面，一个明显的胜利是将元组"打包"到一个单独的向量中(删除上面例子中的方括号(：

const packed_vector_of_tuples = [
0, 0, 0, 0,
0, 1, 4, 6,
9, 8, 7, 2,
5, 6, 7, 8
];

这在分配方面是一个巨大的胜利(对于持有n个元组的向量来说，O(1(而不是O(n((，但在可用性方面却是一个巨大损失。显然，现在我需要以某种方式记住元组的长度(这不是一个问题，很容易解决(，但抽象变得更加困难。假设我现在想迭代元组的压缩向量，类似于vector_of_tuples.forEach(...)最初的工作方式。一个想法是这样做：

function forEach_packed_vector(packed_vector, tuple_length, func) {
for (let i = 0; i < packed_vector.length; i += tuple_length)
func(packed_vector.slice(i, i + tuple_length));
}

然而，这意味着每次迭代时，我都会进行O(n(分配，这正是我试图避免的事情。(V8和SpiderMonkey似乎都无法在堆栈上传递短向量，或者至少无法传递足够的转义分析来处理我的代码(。

相反，我可以保留自己的"堆栈分配"工作空间：

function forEach_packed_vector_2(packed_vector, tuple_length, func) {
const temporary = [];
for (let i = 0; i < packed_vector.length; i += tuple_length) {
// Copy packed_vector[i : i + tuple_length] into temporary.
for (let j = 0; j < tuple_length; j++)
temporary[j] = packed_vector[i + j];
// Now call the iteration function.
func(temporary);
}
}

事实上，这运行得很好，不会分配不止一次，而且速度非常快。然而，我不断遇到错误，func保留了对传入向量的引用(而不是像应该的那样使用防御副本(，这导致了一些非常奇怪的错误在我的代码中的其他地方出现。因此，这个解决方案在性能方面很好，但在能够射中自己的脚方面却相当糟糕。

问题：我如何在不为自己设置陷阱的情况下编写这样的高性能垃圾灯代码？

这个问题基本上是在乞求一种切片类型，比如C#中的Span<T>，或者Go中的切片，等等。但我愿意接受任何关于如何创建这样高效的数据结构的建议，这种方法可以很好地进行抽象，而不会留下足迹。

Answer 1

您可能很清楚，JavaScript中没有"切片类型"。

你可以建立自己的：

class Slice {
constructor(array, start, length) {
this.array = array;
this.start = start;
this.length = length;
}
get(index) {
return this.array[this.start + index];
}
/* any other methods you want */
}
function func(slice) {
for (let i = 0; i < slice.length; i++) {
console.log(slice.get(i));
}
}
func(new Slice(packed_vector_of_tuples, 4, 4));

当然，您可以在创建这样一个切片的任何时候进行分配，但特别是如果元组比4个元素大得多，这可能是抽象和效率之间的合理折衷——特别是，每次分配是O(1(，而Array.prototype.slice必须分配，然后复制n元素。

(编辑：对此进行扩展：您可以通过在外部容器上缓存切片来进一步减少分配数量，大致如下：

class PackedVector {
constructor(tuple_length, tuple_count, tuple_data) {
console.assert(tuple_data.length === tuple_length * tuple_count);
this.array = tuple_data;
this.slices = [];
for (let i = 0; i < tuple_count; i++) {
this.slices[i] = new Slice(this.array, i * tuple_length, tuple_length);
}
this.length = tuple_count;
}
}
function forEach_packed_vector_3(packed_vector, func) {
for (let i = 0; i < packed_vector.length; i++)
func(packed_vector.slices(i));
}

编辑结束(

为了获得最大性能，packed_vector_of_tuples是一个好主意，任何辅助函数都可以使用上面Slice类的"开箱"版本。所以你应该有func(base_array, start, length)而不是func(temporary)。这将防止"意外引用"类错误，但会使函数签名相对难以处理。

根据您的描述，拥有单个元组的对象标识对于您的大型应用程序来说似乎很重要。如果确实是这样的话，我建议使用您的第一个解决方案：数组。当然，会有一些开销；但除非你注意到这真的很重要，否则这并不重要(我的预测是不会；分配很便宜，元组越长，相对开销就越小(。