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

Question

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

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().

Answer 1

StringBuilder builder = new StringBuilder();

StringBuilder不知道输出会有多大，所以你可以在这里得到摊销增长成本：SB不是巫毒魔法，它需要猜测大小。它会猜测"嗯，我给你10个字符"。如果添加第11个字符，SB必须创建一个新的字符数组(一个更大的数组；我认为它增长了x2倍，可能是x1.5)，所以它创建了一个20个字符的数组，复制前10个字符，并丢弃旧数组。这还不错(根据定义，这种增长惩罚适用于不断呈指数递减的数量的append运算)，但。。。

看看输入问题：输出字符串和输入字符串一样大，OR更小(输入中的每个n导致输出小1)。因此，您可以事先告诉StringBuilder：嘿，从这么大的容量(输入的长度)开始。现在已经没有增长惩罚了。

这是由于使用StringBuilder 的开销

这具有误导性或过于简单化；你可能听不太对。StringBuilder只是一个带有char数组的对象。这是开销，是的，但是，

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

，它生成2个模式对象和(可能)3个字符串。字符串也是一个内部有一个大char数组的对象，因此这可能会增加的开销，因此丝毫不能解释为什么您的获取速度会慢得多。

然而，您错过了另一个优化：

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 Microbenchmark Harness)。

如果您想看到一些代码比原始.replaceAll/replaceAll/replace链差得多的示例，请制作一组大字符串，这些字符串不包含任何这些符号(没有换行符、引号、方括号)。你会看到很大的不同。

---

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

1. 几乎什么都不改变；更换相当快。然而，.replaceAll涉及一个正则表达式。如果这一行执行得很好，那么制作一个显式模式对象将更有效，读取效果更好(尽管这是旁观者的看法)。一般来说，这里的模式不使用任何regex功能，所以面试官可能只是想让你用replace替换replaceAll，仅此而已。需要明确的是，如果您有一个带有换行符和引号以及括号的大输入，我在上面的代码将更快，如果没有，则不会更慢。但是，并不是每一行代码都需要最大限度地优化。

2. 在深入研究代码之前，该练习测试了你提出问题并首先寻找全局的意愿。也许他们想让你问：这次跑步多久一次？是否有绩效框架？这个方法通常抛出什么类型的字符串？我们可以看看其他地方，"在源代码处"修复字符串，而不是每次都转换它们吗？当我进行面试时，我倾向于提出一些技术性问题，这些问题看起来很完整，但一旦你深入了解，就会有一些缺失的信息——如果面试官没有问，我会把它们分为几点。这不是一个瞬间的失败——我会告诉他们，看看他们是否愿意先提问和辩论，然后再为下一个问题编程。

Answer 2

您可以直接修改inputArray并将其作为结果使用(可能，因为替换只能缩短字符序列)

这将是我的最终版本：

public static String outputValue(final String input) {
final char[] dataArray = input.toCharArray();
int destPos = 0;
int srcPos = 0;
final int len = dataArray.length;
while (srcPos < len) {
if ('"' == dataArray[srcPos]) {
dataArray[destPos++] = ''';
srcPos++;
continue;
}
if ('n' == dataArray[srcPos]) {
srcPos++;
continue;
}
if ('[' == dataArray[srcPos] && srcPos < len - 1 && ']' == dataArray[srcPos + 1]) {
dataArray[destPos++] = '{';
dataArray[destPos++] = '}';
srcPos += 2;
continue;
}
dataArray[destPos++] = dataArray[srcPos++];
}
return String.copyValueOf(dataArray, 0, destPos);
}

关于代码的思考：

• 内存消耗是dataArray(以及创建的返回字符串)
• 速度：只有评测才能判断它是否比使用预定义大小的StringBuilder更快

速度：我对原始版本、我自己的版本和rzwitserloot(带长字符串dats-len: 268435456 charactersoutput-len 251658240

至少从eclipse内部运行，作为JUnit测试，我的速度比其他两个都快。

我的测试输出：

date-len 268435456     
out-len  251658240  
mr smith42:   1007
rzwitserloot: 1512
Orgiginal:    1950
mr smith42:   834
rzwitserloot: 1370
Orgiginal:    1870
mr smith42:   789
rzwitserloot: 1214
Orgiginal:    1945
mr smith42:   720
rzwitserloot: 1142
Orgiginal:    1572
mr smith42:   672
rzwitserloot: 1073
Orgiginal:    1739
mr smith42:   925
rzwitserloot: 1240   
Orgiginal:    1823  
mr smith42:   834  
rzwitserloot: 1284  
Orgiginal:    1676  
mr smith42:   840  
rzwitserloot: 1230  
Orgiginal:    1621 
mr smith42:   811  
rzwitserloot: 1260  
Orgiginal:    1695  
mr smith42:   840  
rzwitserloot: 1257  
Orgiginal:    1707  
mr smith42:   868  
rzwitserloot: 1309  
Orgiginal:    1716  
mr smith42:   837  
rzwitserloot: 1262  
Orgiginal:    1683  
mr smith42:   835  
rzwitserloot: 1240  
Orgiginal:    1632  
mr smith42:   824  
rzwitserloot: 1255  
Orgiginal:    1635  
mr smith42:   844  
rzwitserloot: 1243  
....

这里是我的粗略测试：(使用真正的评测工具应该会得到类似的结果)

@Test
public void test() {
String data = "jksdhfewfnkun[] [  {} "  [] }nss";
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
data += data;
String expected = "jksdhfewfnku{} [  {} '  {} }ss";
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
expected += expected;
System.err.println("date-len " + data.length());
System.err.println("out-len  " + expected.length());
// run it multible times to give the VM a chance for optimization
for (int i = 20; 0 < i; i--) {
final long t = System.currentTimeMillis();
Assert.assertEquals(expected, T.outputValue(data));
System.err.println("mr smith42:   " + (System.currentTimeMillis() - t));
final long t2 = System.currentTimeMillis();
Assert.assertEquals(expected, T.outputValue2(data));
System.err.println("rzwitserloot: " + (System.currentTimeMillis() - t2));
final long t3 = System.currentTimeMillis();
Assert.assertEquals(expected, T.outputValueOrgiginal(data));
System.err.println("Orgiginal:    " + (System.currentTimeMillis() - t3));
}
}

Answer 3

这些面试问题更多的是关于你问面试官什么问题。面试官是客户，而你是解决他们问题的承包商。

这是他们的系统，你被要求优化。你打算问他们什么问题？

另一种情况是，他们不知道如何优化这行代码，他们只是在运行一些工具——有人(比他们更有天赋)制造的工具——来找到瓶颈。

你在那里给他们免费的代码来运行他们的工具。你没有得到这份工作，因为一开始就没有工作。背阴的对在所有行业和学科中经常做？对