从 Java 字符串中剥离所有不可打印字符的最快方法更新更新 2

string performance optimization java micro-optimization

2022-08-31 12:03:21

在 Java 中，从中剥离所有不可打印字符的最快方法是什么？String

到目前为止，我已经尝试并测量了138字节，131个字符的字符串：

字符串 - 最慢的方法replaceAll()
- 517009结果/秒
预编译模式，然后使用 Matcher 的replaceAll()
- 637836结果/秒
使用 StringBuffer，逐个获取代码点并附加到 StringBuffercodepointAt()
- 711946结果/秒
使用 StringBuffer，逐个获取字符并附加到 StringBuffercharAt()
- 1052964结果/秒
预分配缓冲区，使用逐个获取字符并填充此缓冲区，然后转换回字符串char[]charAt()
- 2022653结果/秒
预分配 2 个缓冲区 - 新旧，使用一次获取现有 String 的所有字符，逐个迭代旧缓冲区并填充新缓冲区，然后将新缓冲区转换为 String - 我自己的最快版本char[]getChars()
- 2502502结果/秒
具有 2 个缓冲区的相同内容 - 仅使用，并将编码指定为“utf-8”byte[]getBytes()
- 857485结果/秒
具有 2 个缓冲区的相同内容，但将编码指定为常量byte[]Charset.forName("utf-8")
- 791076结果/秒
具有2个缓冲区的相同内容，但将编码指定为1字节本地编码（几乎不是一件明智的事情）byte[]
- 370164结果/秒

我最好的尝试是以下几点：

    char[] oldChars = new char[s.length()];
    s.getChars(0, s.length(), oldChars, 0);
    char[] newChars = new char[s.length()];
    int newLen = 0;
    for (int j = 0; j < s.length(); j++) {
        char ch = oldChars[j];
        if (ch >= ' ') {
            newChars[newLen] = ch;
            newLen++;
        }
    }
    s = new String(newChars, 0, newLen);

关于如何使它更快的任何想法？

回答一个非常奇怪的问题的奖励点：为什么使用“utf-8”字符集名称直接产生比使用预分配的静态const更好的性能？Charset.forName("utf-8")

更新

棘轮怪胎的建议产生了令人印象深刻的3105590结果/秒性能，提高了+24%！
Ed Staub的建议带来了另一个改进 - 3471017结果/秒，比以前的最佳成绩高出12%。

更新 2

我尽了最大努力收集所有提出的解决方案及其交叉突变，并将其作为github的小型基准框架发布。目前它拥有17种算法。其中之一是“特殊的” - Voo1算法（由SO用户Voo提供）采用复杂的反射技巧，从而实现了出色的速度，但它搞乱了JVM字符串的状态，因此它是单独基准测试的。

欢迎您签出并运行它以确定盒子上的结果。以下是我得到的结果摘要。它的规格：

德比安希德
Linux 2.6.39-2-amd64 （x86_64）
Java从软件包安装，JVM将自己标识为sun-java6-jdk-6.24-1
- Java（TM） SE Runtime Environment （build 1.6.0_24-b07）
- Java HotSpot（TM） 64 位服务器虚拟机（内部版本 19.1-b02，混合模式）

不同的算法在给定一组不同的输入数据时最终显示不同的结果。我在3种模式下运行了基准测试：

相同的单个字符串

此模式适用于类作为常量提供的相同单个字符串。摊牌是：StringSource

 Ops / s  │ Algorithm
──────────┼──────────────────────────────
6 535 947 │ Voo1
──────────┼──────────────────────────────
5 350 454 │ RatchetFreak2EdStaub1GreyCat1
5 249 343 │ EdStaub1
5 002 501 │ EdStaub1GreyCat1
4 859 086 │ ArrayOfCharFromStringCharAt
4 295 532 │ RatchetFreak1
4 045 307 │ ArrayOfCharFromArrayOfChar
2 790 178 │ RatchetFreak2EdStaub1GreyCat2
2 583 311 │ RatchetFreak2
1 274 859 │ StringBuilderChar
1 138 174 │ StringBuilderCodePoint
  994 727 │ ArrayOfByteUTF8String
  918 611 │ ArrayOfByteUTF8Const
  756 086 │ MatcherReplace
  598 945 │ StringReplaceAll
  460 045 │ ArrayOfByteWindows1251

图表形式：
_{（来源：greycat.ru）}

多个字符串，100% 的字符串包含控制字符

源字符串提供程序使用（0..127）字符集预先生成了许多随机字符串 - 因此几乎所有字符串都包含至少一个控制字符。算法以轮循机制方式从此预生成的数组接收字符串。

 Ops / s  │ Algorithm
──────────┼──────────────────────────────
2 123 142 │ Voo1
──────────┼──────────────────────────────
1 782 214 │ EdStaub1
1 776 199 │ EdStaub1GreyCat1
1 694 628 │ ArrayOfCharFromStringCharAt
1 481 481 │ ArrayOfCharFromArrayOfChar
1 460 067 │ RatchetFreak2EdStaub1GreyCat1
1 438 435 │ RatchetFreak2EdStaub1GreyCat2
1 366 494 │ RatchetFreak2
1 349 710 │ RatchetFreak1
  893 176 │ ArrayOfByteUTF8String
  817 127 │ ArrayOfByteUTF8Const
  778 089 │ StringBuilderChar
  734 754 │ StringBuilderCodePoint
  377 829 │ ArrayOfByteWindows1251
  224 140 │ MatcherReplace
  211 104 │ StringReplaceAll

图表形式：
_{（来源：greycat.ru）}

多个字符串，1% 的字符串包含控制字符

与之前相同，但只有1%的字符串是使用控制字符生成的 - 另外99%是使用[32..127]字符集生成的，因此它们根本不能包含控制字符。在我的位置，这种合成负载最接近该算法的实际应用。

 Ops / s  │ Algorithm
──────────┼──────────────────────────────
3 711 952 │ Voo1
──────────┼──────────────────────────────
2 851 440 │ EdStaub1GreyCat1
2 455 796 │ EdStaub1
2 426 007 │ ArrayOfCharFromStringCharAt
2 347 969 │ RatchetFreak2EdStaub1GreyCat2
2 242 152 │ RatchetFreak1
2 171 553 │ ArrayOfCharFromArrayOfChar
1 922 707 │ RatchetFreak2EdStaub1GreyCat1
1 857 010 │ RatchetFreak2
1 023 751 │ ArrayOfByteUTF8String
  939 055 │ StringBuilderChar
  907 194 │ ArrayOfByteUTF8Const
  841 963 │ StringBuilderCodePoint
  606 465 │ MatcherReplace
  501 555 │ StringReplaceAll
  381 185 │ ArrayOfByteWindows1251

图表形式：
_{（来源：greycat.ru）}

我很难决定谁提供了最好的答案，但考虑到现实世界中最好的解决方案是由Ed Staub给出/启发的，我想标记他的答案是公平的。感谢所有参与其中的人，您的意见非常有帮助和宝贵。随意在您的盒子上运行测试套件，并提出更好的解决方案（工作JNI解决方案，有人吗？

引用

具有基准测试套件的 GitHub 存储库

答案 1

使用1个字符数组可以更好地工作

int length = s.length();
char[] oldChars = new char[length];
s.getChars(0, length, oldChars, 0);
int newLen = 0;
for (int j = 0; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

我避免了重复打电话s.length();

另一个可能有效的微优化是

int length = s.length();
char[] oldChars = new char[length+1];
s.getChars(0, length, oldChars, 0);
oldChars[length]='\0';//avoiding explicit bound check in while
int newLen=-1;
while(oldChars[++newLen]>=' ');//find first non-printable,
                       // if there are none it ends on the null char I appended
for (int  j = newLen; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;//the while avoids repeated overwriting here when newLen==j
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

答案 2

如果将此方法嵌入到不在线程之间共享的类中是合理的，则可以重用缓冲区：

char [] oldChars = new char[5];

String stripControlChars(String s)
{
    final int inputLen = s.length();
    if ( oldChars.length < inputLen )
    {
        oldChars = new char[inputLen];
    }
    s.getChars(0, inputLen, oldChars, 0);

等。。。

这是一个巨大的胜利 - 20%左右，因为我理解目前最好的情况。

如果要将其用于潜在的大字符串，并且内存“泄漏”是一个问题，则可以使用弱引用。