提高从字符串中移除字符的性能

Question

作为面试实践的一部分，我写了这个功能。此方法从给定字符串中移除字符。

当涉及到运行时/空间时，我想知道如何使这段代码更高效。我认为我的代码是O(n)，我不确定我是否能提高效率。然而，也许使用诸如StringBuffer或StringBuilder之类的东西会增加一些呢？我不确定，因为我对Java还有点陌生。

public static String takeOut(String str, char c) {
    int len = str.length();
    String newstr = "";
    for (int i = 0; i < len; i++) {
        if (str.charAt(i) != c) {
            newstr = newstr + str.charAt(i);
        }
    }
    return newstr;
}

Answer 1

从现有的实现学习，他们通常有解决方案的角落案例，常见的陷阱和性能瓶颈。例如，Apache StringUtils也有一个remove函数。它的实现非常简单，类似于您的：

public static String remove(final String str, final char remove) {
    if (isEmpty(str) || str.indexOf(remove) == INDEX_NOT_FOUND) {
        return str;
    }
    final char[] chars = str.toCharArray();
    int pos = 0;
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] != remove) {
            chars[pos++] = chars[i];
        }
    }
    return new String(chars, 0, pos);
}

总之，有一些不同之处：

1. 它使用char数组。Strings是不可变的，下面的连接创建了一个新的String对象: newstr = newstr + str.charAt(i)；我猜它比更改数组中的值要慢。使用字符串级联操作符重复连接n个字符串需要时间为n。源:有效的Java，第二版，第51项:注意字符串级联的性能。
2. 在第一行，它检查String是否包含已删除的字符。如果它不包含它，remove将保存char数组的创建。这可能会有帮助，但这取决于您的输入。
3. 问题中的代码在比较中调用String.charAt()，后者检查给定的索引: public char charAt(int index) { if (index < 0) that ( index >= value.length)) {抛出新的StringIndexOutOfBoundsException(索引)；}返回值索引；} StringUtils实现跳过此测试，因为它知道索引是有效的。

(另见:有效Java，第二版，第47项:了解和使用库)

Answer 2

首先，代码的复杂性为O (n ) (n个字符串的字符数)，它将精确地依赖于方法String.charAt(索引)的实现，但我们很可能认为它具有直接访问权。

O(n)是最低的。实际上，可以这样想:如果不查看字符串的所有字符，那么如何才能删除字符串的所有实例。因此，这几乎不可能做得更好。

有一个关于Java中字符串级联性能的问题。对于你的问题，我会说，那么StringBuilder可能是一个更好的选择。我还会考虑从头开始创建char数组，但我不知道来自数组的字符串构造函数在性能方面是如何运行的。

最后，如果目标只是从字符串中删除一个字符(出于面试问题)，通常调用String.replaceAll(myChar，"")；

Answer 3

我要补充如下：

• 单元测试代码--一些单元测试--它必须成为您的习惯。如果您发布了一些代码，那么还可以添加单元测试。首先，您可以检查代码的正确性，其次，它将帮助我们重构您的代码(生成更好的解决方案)。
• 好名字请用好名字。我知道，甚至Apache用的名字也不太好。没有'c‘没有'str’。一个自我描述的名字。不需要评论。我知道，并不是每个人都会同意，因为代码看起来有点“沉重”，但读起来真高兴！