0

In ArrayList the add operation is amortized operation. So while reading StringBuffer it came to my mind why the StringBuffer is not amortized. Suppose I use append operation on a string buffer object then it should be able to add those many no of characters in it's underlying array implementation. But instead I found in source code that we have 

System.arraycopy(chars, 0, value, count, chars.length);

in append operation of string buffer. So my question is can't the StringBuffer be amortized so it can give us less that O(N) complexity?

4

4 回答 4

1

归根结底，您仍在将 N 个引用从某个内存位置 A 移动到某个其他内存位置 B。但是，我相信System.arraycopy它的速度足够快，以至于来自StringBuffer. 但是，这取决于您是否这样做append或insert.

回想一下，有两种方法ArrayList可以执行add：使用单个对象，或者将元素从特定索引点向下移动。两者都有不同的表现。

为了解决这个问题，（最终）StringBuffer将调用System.arraycopy(). 这个实现实际上是依赖于 JVM 的（它是一个本地调用），但可能是它非常快。StringBuffer.append()除此之外，除了要复制的非常大的非连续内存区域之外，没有什么可以真正减慢 的性能。

ArrayList.add(E element)将花费一个 amoritized O(1) 时间，但可能会更改为 O(N)，因为它必须增​​长支持数组以适应其中的更多元素；但是，如果它不必这样做，那么插入时间大约为 O(1) （它将元素添加到数组的末尾）。

ArrayList.add(int index, E element)在最好的情况下可能是 O(1)，但在平均和最坏的情况下可能是 O(N - index)，因为它必须向下移动才能放入E。

总结一下：

  • 的代码StringBuffer.append()可以看作是摊销 O(N)，因为它确实复制了数组。但是，此操作仍然很快，并且仅取决于您移动的数据有多大。

  • 的代码StringBuffer.insert()是不同的，并且在最好的情况下很容易成为一个摊销的 O(1)，在最坏的情况下是 O(N)（因为它对 进行了两次调用System.arraycopy()）。在给定点插入元素意味着您必须将其他所有内容向下移动，这不是一个便宜的操作，无论您的代码有多快。

我相信，根据您使用的方法，您确实有摊销业绩。您只需要确定您正在执行的操作即可知道性能将如何。

于 2013-07-04T08:14:41.310 回答
1

实际上StringBuffer和ArrayList工作方式相同，正如你所指出的，add操作ArrayList是O(1) 摊销的。

在添加元素时，您ArrayList还有一种ensureCapacity方法，如果容量不足，则会分配一个新数组并将数据复制到其中。然而，这种重新分配的操作很少发生，因此您可以认为即使加法需要O(1)超过 K 的 1 倍，它也需要O(n).

于 2013-07-04T08:01:21.497 回答
0

您正在混合取决于数据结构的大小（ArrayList / StringBuilder 长度）的复杂性和取决于输入大小的复杂性。

ArrayList 是O(1)指将单个元素添加到列表的内容中，并且是 amortized O(1)。显然，将 n 个元素添加到列表中n * O(1)。StringBuilder 也是如此。在大多数情况下，添加单个字符是O(1)（除非必须扩展内部数组。但是添加 char 数组需要复制数组的值（实际上，数组的批量复制应该非常快，肯定比附加单个字符要快）。

O(1)对于列表连接可以实现 - 附加时 - 使用链表。但是结果很容易受到每个连接子列表的变化的影响，……。StringBuilder 总是想避免。此外，作为字符串实现的字符链接列表将非常低效。

于 2013-07-04T08:12:24.727 回答
0

如果您进一步查看源代码：

public AbstractStringBuilder append(char[] str) {
    int len = str.length;
    ensureCapacityInternal(count + len);  // expand array if needed
    System.arraycopy(str, 0, value, count, len); 
    count += len;
    return this;
}

这正是arraylist 的工作原理。

    System.arraycopy(str, 0, value, count, len);

告诉我们从 str 复制到从 count 开始的值（stringBuffer 中的当前结束位置）。仅len复制附加 str 的长度。

于 2013-07-04T07:50:56.703 回答