Java CharAt()和deleteCharAt()性能

Question

我一直想知道java中String/StringBuilder/StringBuffer的charAt函数的实现是什么的复杂性？那么StringBuffer/StringBuilder中的deleteCharAt()呢？

Answer 1

对于String,StringBuffer和StringBuilder,charAt()是一个恒定时间操作.

对于StringBuffer和StringBuilder,deleteCharAt()是线性时间操作.

StringBuffer并StringBuilder具有非常相似的性能特征.主要区别在于前者是synchronized(线程安全的),而后者则不是.

Answer 2

让我们依次查看每个方法的相应实际java实现(仅相关代码).这本身就会回答他们的效率.

String.charAt:

public char charAt(int index) {
    if ((index < 0) || (index >= value.length)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    return value[index];
}

我们可以看到,它只是一个单一的数组访问,它是一个恒定的时间操作.

StringBuffer.charAt:

public synchronized char charAt(int index) {
  if ((index < 0) || (index >= count))
    throw new StringIndexOutOfBoundsException(index);
  return value[index];
}

再次,单阵列访问,所以一个恒定的时间操作.

StringBuilder.charAt:

public char charAt(int index) {
    if ((index < 0) || (index >= count))
        throw new StringIndexOutOfBoundsException(index);
    return value[index];
}

再次,单阵列访问,所以一个恒定的时间操作.即使所有这三种方法看起来都相同,但也存在一些细微差别.例如,只有StringBuffer.charAt方法是同步的,而不是其他方法.同样,如果 String.charAt的检查略有不同(猜猜为什么？).仔细看看这些方法实现本身就会给我们带来其他的细微差别.

现在,让我们看看deleteCharAt实现.

String没有deleteCharAt方法.原因可能是它是一个不可变的对象.因此,暴露一个明确指示此方法修改对象的API可能不是一个好主意.

StringBuffer和StringBuilder都是AbstractStringBuilder的子类.这两个类的deleteCharAt方法将实现委托给其父类本身.

StringBuffer.deleteCharAt:

  public synchronized StringBuffer deleteCharAt(int index) {
        super.deleteCharAt(index);
        return this;
    }

StringBuilder.deleteCharAt:

 public StringBuilder deleteCharAt(int index) {
        super.deleteCharAt(index);
        return this;
    }

AbstractStringBuilder.deleteCharAt:

  public AbstractStringBuilder deleteCharAt(int index) {
        if ((index < 0) || (index >= count))
            throw new StringIndexOutOfBoundsException(index);
        System.arraycopy(value, index+1, value, index, count-index-1);
        count--;
        return this;
    }

仔细看看AbstractStringBuilder.deleteCharAt方法会发现它实际上正在调用System.arraycopy.在最坏的情况下,这可以是O(N).所以deleteChatAt方法是O(N)时间复杂度.

Answer 3

该charAt方法O(1).

假设您正在从字符/ 中删除随机字符,则该deleteCharAt方法在平均值上.(平均而言,它必须移动剩余字符的一半以填充已删除字符留下的"漏洞".多个操作没有摊销 ;请参阅下文.)但是,如果删除最后一个字符,则成本会的.StringBuilderStringBufferO(N)NStringBufferStringBuilderO(1)

没有deleteCharAt办法String.

从理论上讲,StringBuilder并StringBuffer能为你在哪里插入或在一个"通",通过缓冲删除多个字符的情况进行优化.他们可以通过在缓冲区中保持可选的"间隙"并在其上移动字符来实现此目的.(IIRC,emacs以这种方式实现其文本缓冲.)这种方法的问题是:

• 它需要更多的空间,用于说明差距所在的属性,以及间隙本身.
• 它使代码更复杂,并减慢其他操作.例如,charAt必须offset将间隙的起点和终点进行比较,并在获取字符数组元素之前对实际索引值进行相应的调整.
• 如果应用程序在同一个缓冲区上执行多次插入/删除操作,它只会有所帮助.

毫不奇怪,这种"优化"还没有在标准StringBuilder/ StringBuffer类中实现.但是,自定义CharSequence类可以使用此方法.

Answer 4

charAt超快(并且可以使用String的内在函数),它是一个简单的数组索引.deleteCharAt需要一个arraycopy,因此删除一个char将不会很快.