list - Big O 列表复杂度 8 字节 vs 16 字节

Question

在以下链接中：

如果您向下滚动到他正在比较排序的部分，他首先会显示具有 8 字节数据类型的结果，比较列表、向量和双端队列。对于 8 字节（和 128 字节）数据类型，列表比向量和双端队列慢得多。然而，在排序比较的底部，他使用了 16 字节数据类型，列表突然变得更快了。

8 和 128 字节的列表如何变慢，但介于两者之间的值（即 16 字节）更快？

编辑：我在 random_insert 部分注意到相同的模式。对于 8 字节和 32 字节数据类型，列表比向量和双端队列慢，但对于 16 字节数据类型要快得多？

score 2 · Accepted Answer

请注意，16 字节数据类型不是“普通的 16 字节数据类型”，它指出：

非平凡的数据类型由两个 long 组成，并且具有非常愚蠢的赋值运算符和复制构造函数，它们只是做一些数学运算（完全没有意义但代价高昂）。有人可能会争辩说，这既不是通用的复制构造函数，也不是通用的赋值运算符，而且一个是正确的，但是，重要的一点是，对于这个基准测试来说，成本高昂的运算符就足够了。

因此，这与 16 字节是一个使列表变慢的幻数无关，而是与运算符重载在非平凡类型上使其变慢有关。

1 回答 1