优化插入列表中间

Question

我有适用于动态增长列表（连续内存，如 C++ 向量、Java ArrayList 或 C# 列表）的算法。直到最近，这些算法还会将新值插入列表的中间。当然，这通常是一个非常慢的操作。每次添加一个项目时，它后面的所有项目都需要转移到更高的索引。对每个算法都这样做几次，事情会变得非常慢。

我的认识是，我可以将新项目添加到列表的末尾，然后稍后将它们旋转到位。这是一种选择！

当我知道提前添加多少项目时，另一种选择是将那么多项目添加到后面，移动现有项目，然后在我为自己制作的孔中就地执行算法。缺点是我必须在列表末尾添加一些默认值，然后覆盖它们。

我对这些选项进行了快速分析，得出的结论是第二个选项更有效。我的理由是，第一个选项的轮换将导致就地交换（需要临时）。我对第二个选项唯一关心的是我正在创建一堆默认值，这些默认值只是被丢弃。大多数时候，这些默认值将为 null 或内存填充值类型。

但是，我希望熟悉算法的其他人告诉我哪种方法会更快。或者，也许有一个我没有考虑过的更有效的解决方案。

Answer 1

对于数组末尾以外的任何位置的大量插入或删除，数组效率不高。考虑使用不同的数据结构（例如其他答案之一中建议的数据结构）是否可能更有效。如果不知道您要解决的问题，几乎不可能提出一种数据结构（没有一种解决方案可以解决所有问题）。话虽如此...

第二种选择绝对是两者中更好的选择。一个更好的选择（避免默认值问题）：只需复制789到末尾并789用覆盖中间部分456。所以唯一的中间步骤是0123789789。

然而，您的默认值问题（通常）并不是一个大问题：

• 其一，在 Java 中，（据我所知）甚至不能为非 0 或空填充的数组分配内存。我相信 C++ STL 容器也强制执行这一点（但不是 C++ 本身）。

• 与任何中等大小的类相比，指针的大小是最小的（因此将其分配给默认值也花费最少的时间）（在 Java 和 C# 中，一切都是指针，在 C++ 中，您可以使用指针（类似于boost::shared_ptr指针向量或指针向量）优于直接指针）（对于基元不适用，基元一开始很小，所以通常也不是一个大问题）。

我还建议在开始插入到数组末尾（JavaArrayList::ensureCapacity或 C++ vector::reserve）之前强制重新分配到指定的大小。如果您不知道 - 变长数组实现往往有一个比size()返回值或可访问值更大的内部数组（为了防止在插入或删除值时不断重新分配内存）。

另请注意，有比使用 for 循环手动执行复制部分数组更有效的方法（例如 Java 的System.arraycopy）。