java - 如何在不使用正则表达式的情况下优化代码？

问题描述

我招聘时的测试任务是优化这段代码：

someString.replaceAll("\"", "'").replaceAll("\n", "").replace("[]", "{}");

为了解决这个问题，我写了这个方法：

public String outputValue(String input) {
   char[] inputArray = input.toCharArray();
   StringBuilder builder = new StringBuilder();
   for (int i = 0; i < inputArray.length; i++) {
      if (i != inputArray.length - 1 && inputArray[i] == '[' && inputArray[i + 1] == ']' ) {
         builder.append("{}");
         i++;
      }
      else if (inputArray[i] == '"')
         builder.append("'");
      else if (inputArray[i] == '\n' )
         continue;
      else builder.append(inputArray[i]);
   }
   return  builder.toString();
}

我有很多解决这个问题的选择，但这似乎是最优化的。我使用Instant类测试了速度，并且在任何行大小上都显示了很高的结果。该公司告诉我，在他们的测量中，大型线路出现退化，这是由于使用StringBuilder的开销和最后无条件分配新线路造成的。

所以我没有找到工作。

什么解决方案可以更优化？即使使用 char 数组，我也不能没有字符串分配String.valueOf()。

标签： javaregexalgorithmoptimization

StringBuilder builder = new StringBuilder();

StringBuilder 不知道输出会有多大，所以你会在这里得到摊销的增长成本：SB 不是巫术魔法，它需要猜测大小。它会猜测“嗯，我会给你 10 个字符”。如果然后添加第 11 个字符，SB 必须创建一个新的 char 数组（更大的一个；我认为它增长了 x2 倍，可能是 x1.5），所以它创建了一个 20 个字符的数组，复制第一个10 个字符，然后扔掉旧数组。这还不错（根据定义，这种增长惩罚适用于呈指数级减少的append操作），但是......

查看输入问题：输出字符串与输入字符串一样大，或者更小（\n输入中的每个结果都会导致输出小 1）。因此，您可以事先告诉 StringBuilder：嘿，从这么多容量（输入的长度）开始。现在不再有增长惩罚。

这是由于使用 StringBuilder 的开销

这具有误导性或过于简单化；您可能没有完全正确地听到。StringBuilder 只是一个对象，带有一个 char 数组。那是开销，是的，但是，

someString.replaceAll("\"", "'").replaceAll("\n", "").replace("[]", "{}");

这会产生 2 个模式对象和（可能）3 个字符串。字符串也只是一个内部带有大字符数组的对象，因此这可能会产生更多开销，因此丝毫不能解释为什么您的拍摄速度会慢很多。

但是，您错过了另一个优化：

如果不需要， replace/replaceAll方法不会生成任何字符串AT ALL。试试看："Hello!".replace("Foo", "Bar")返回相同的引用（a == b相等）。

此外，.toCharArray确实需要另一个完整的克隆，也很昂贵。只需使用charAt.

所以，让我们做一个真正的快速：

public String outputValue(String input) {
   StringBuilder builder = null;
   int len = input.length();
   for (int i = 0; i < len; i++) {
      char c = input.charAt(i);
      if (c != '[' && c != '\n' && c != '"') {
        if (builder != null) builder.append(c);
        continue;
      }

      if (builder == null) {
        // Don't even make the builder until we determine we need it!
        builder = new StringBuilder(len);
        builder.append(input, 0, i);
      }
      if (i != leg - 1 && c == '[' && input.charAt(i + 1) == ']' ) {
         builder.append("{}");
         i++;
      } else if (c == '"') {
         builder.append('\'');
      } else if (c != '\n') {
         builder.append(c);
      }
   }
   return  builder == null ? input : builder.toString();
}

我使用 Instant 类测试了速度，并且在任何行大小上都显示了很高的结果。

不是你如何测试性能。Instant 代表系统时钟；它最多只有微秒的粒度（通常甚至没有），并且如果网络时间守护进程改变你的时间，它可以并且将会改变。它也可能被拖尾（当时钟需要调整时，因为那里的很多软件都假设时间永远不会倒退，而不是仅仅将时间向后移动，拖尾的 NTP 只会运行时间“更慢” - 每增加 750 毫秒例如，第二个，直到时间“固定”）。

不过，即使 nanoTime 也不是很好——基准测试比这复杂得多。使用 JMH（Java 微基准线束）。

如果您想查看一些代码比原始.replaceAll/replaceAll/replace链更糟糕的示例，请制作一堆大的字符串并且不包含任何这些符号（没有换行符，没有引号，没有括号）。你会看到很大的不同。

但是，面试问题不一定是关于代码优化的。例如，我发现这些同样合理：

几乎没有改变；替换相当快。但是，.replaceAll涉及正则表达式。如果这条线被大量执行，那么制作一个显式的模式对象会更有效并且读起来更好（尽管这是旁观者的看法）。更一般地说，这里的模式不使用任何正则表达式功能，所以也许面试官只是想让你替换replaceAll，仅replace此而已。需要明确的是，如果你有一个带有换行符、引号和括号的大输入，我上面的代码会更快，如果没有的话也不会变慢。但是，并不是每一行代码都需要尽可能地优化。
在深入研究代码之前，该练习测试了您提出问题并首先寻找大局的意愿。也许他们想让你问：这次跑步多久一次？是否有适当的绩效框架？这种方法通常会抛出什么样的字符串？我们是否可以在别处寻找并“从源头”修复字符串，而不是每次都转换它们？当我进行面试时，我倾向于提出看似完整的技术问题，但一旦你深入挖掘，就会有一些缺失的信息——如果被面试者不问，我会扣分。这不是一蹴而就的失败——我会告诉他们，看看他们是否愿意先提问和辩论，然后再深入研究下一个问题的编程。

java - 如何在不使用正则表达式的情况下优化代码？

问题描述

解决方案

推荐阅读