从 Java 字符串中删除所有不可打印字符的最快方法

Question

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

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

• String 的 replaceAll() - 最慢​​方法
  • 517009 个结果/秒
• 预编译一个 Pattern，然后使用 Matcher 的 replaceAll()
  • 637836 个结果/秒
• 使用 StringBuffer，使用 codepointAt() 逐一获取代码点并附加到 StringBuffer
  • 711946 个结果/秒
• 使用 StringBuffer，使用 charAt() 逐一获取字符并附加到 StringBuffer
  • 1052964 个结果/秒
• 预分配一个 char[] 缓冲区，使用 charAt() 逐一获取字符并填充此缓冲区，然后转换回 String
  • 2022653 个结果/秒
• 预分配 2 个 char[] 缓冲区 - 新旧缓冲区，使用 getChars() 一次获取现有字符串的所有字符，迭代旧缓冲区一对一填充新缓冲区，然后将新缓冲区转换为字符串 - 我自己最快的版本
  • 2502502 个结果/秒
• 具有 2 个缓冲区的相同内容 - 仅使用 byte[]、getBytes() 并将编码指定为“utf-8”
  • 857485 个结果/秒
• 具有 2 个 byte[] 缓冲区的相同内容，但将编码指定为常量 Charset.forName("utf-8")
  • 791076 个结果/秒
• 与 2 个 byte[] 缓冲区相同的内容，但将编码指定为 1 字节本地编码（几乎不是明智之举）
  • 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 字符串的状态，因此它是单独进行基准测试的。

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

• Debian sid
• Linux 2.6.39-2-amd64 (x86_64)
• Java 从包 sun-java6-jdk-6.24-1 安装，JVM 将自身标识为
  • Java(TM) SE 运行时环境（版本 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 存储库 以及基准测试套件

Answer 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);

Answer 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% 左右，据我了解当前的最佳情况。

如果要在可能很大的字符串上使用它并且需要考虑内存“泄漏”，则可以使用弱引用。

Answer 3

嗯，根据我的测量，我已经击败了当前最好的方法（使用预分配数组的怪物解决方案）大约 30%。如何？通过出卖我的灵魂。

我确信到目前为止关注过讨论的每个人都知道这几乎违反了任何基本的编程原则，但是哦，好吧。无论如何，只有当字符串的使用字符数组不在其他字符串之间共享时，以下内容才有效 - 如果确实如此，那么任何必须调试它的人都将有权决定杀死你（无需调用 substring() 并在文字字符串上使用它这应该可以工作，因为我不明白为什么 JVM 会保留从外部源读取的唯一字符串）。不过，不要忘记确保基准测试代码不会这样做——这是极有可能的，并且显然会对反射解决方案有所帮助。

无论如何，我们开始吧：

    // Has to be done only once - so cache those! Prohibitively expensive otherwise
    private Field value;
    private Field offset;
    private Field count;
    private Field hash;
    {
        try {
            value = String.class.getDeclaredField("value");
            value.setAccessible(true);
            offset = String.class.getDeclaredField("offset");
            offset.setAccessible(true);
            count = String.class.getDeclaredField("count");
            count.setAccessible(true);
            hash = String.class.getDeclaredField("hash");
            hash.setAccessible(true);               
        }
        catch (NoSuchFieldException e) {
            throw new RuntimeException();
        }

    }

    @Override
    public String strip(final String old) {
        final int length = old.length();
        char[] chars = null;
        int off = 0;
        try {
            chars = (char[]) value.get(old);
            off = offset.getInt(old);
        }
        catch(IllegalArgumentException e) {
            throw new RuntimeException(e);
        }
        catch(IllegalAccessException e) {
            throw new RuntimeException(e);
        }
        int newLen = off;
        for(int j = off; j < off + length; j++) {
            final char ch = chars[j];
            if (ch >= ' ') {
                chars[newLen] = ch;
                newLen++;
            }
        }
        if (newLen - off != length) {
            // We changed the internal state of the string, so at least
            // be friendly enough to correct it.
            try {
                count.setInt(old, newLen - off);
                // Have to recompute hash later on
                hash.setInt(old, 0);
            }
            catch(IllegalArgumentException e) {
                e.printStackTrace();
            }
            catch(IllegalAccessException e) {
                e.printStackTrace();
            }
        }
        // Well we have to return something
        return old;
    }

对于我的测试字符串，它得到 3477148.18ops/s 与旧版本的 2616120.89ops/s 。我很确定解决这个问题的唯一方法可能是用 C 语言编写它（但可能不是），或者到目前为止还没有人考虑过的一些完全不同的方法。虽然我绝对不确定不同平台上的计时是否稳定 - 至少在我的机器（Java7、Win7 x64）上产生可靠的结果。

Answer 4

您可以根据处理器的数量将任务拆分为多个并行子任务。

Answer 5

我很自由，为不同的算法写了一个小基准。它并不完美，但我在随机字符串上运行给定算法 10000 次（默认情况下大约有 32/200% 不可打印），最少运行 1000 次。这应该处理诸如 GC、初始化等问题 - 没有太多的开销以至于任何算法都不应该在没有太多阻碍的情况下至少运行一次。

没有特别详细的记录，但是哦，很好。 我们开始 - 我包括了棘轮怪胎的算法和基本版本。目前，我随机初始化一个 200 个字符长的字符串，其中字符在 [0, 200) 范围内均匀分布。

Answer 6

IANA 低级 java 性能迷，但是您尝试过 展开主循环吗？看起来它可以允许某些 CPU 并行执行检查。

此外，这有一些有趣的优化想法。

Answer 7

它可以走得更快。更快^*。如何？通过利用 System.arraycopy 这是本机 方法。回顾一下：

• 如果“干净”，则返回相同的字符串。

• 避免在每次迭代时分配新的 char[]

• 使用 System.arraycopy 将元素 x 位置移回

   公共类 SteliosAdamantidis 实现 StripAlgorithm {
  
        私有 char[] 复制 = 新 char[128];
  
        @覆盖
        public String strip(String s) 抛出异常 {
            int 长度 = s.length();
            if (长度>copy.length) {
                int newLength = copy.length * 2;
                while (长度> newLength) newLength *= 2;
                复制=新字符[新长度];
            }
  
            s.getChars(0, 长度, 副本, 0);
  
            int 开始 = 0; //从哪里开始复制
            整数偏移量=0； //不可打印字符的数量或距离
                            //后面的字符应该被复制到
  
            整数索引 = 0；
            //快进到第一个不可打印字符
            for (; 索引 < 长度; ++index) {
                if (复制[索引] < ' ') {
                    开始=索引；
                    休息;
                }
            }
  
            //字符串已经干净了
            if (索引==长度) 返回 s;
  
            for (; 索引 < 长度; ++index) {
                if (复制[索引] < ' ') {
                    if (开始!=索引) {
                        System.arraycopy(复制, 开始, 复制, 开始 - 偏移量, 索引 - 开始);
                    }
                    ++偏移量；
                    开始=索引+1； //处理后续的不可打印字符
                }
            }
  
            如果（长度！=开始）{
                //复制剩余部分 - 如果有的话
                System.arraycopy(复制，开始，复制，开始-偏移量，长度-开始);
            }
            返回新字符串（副本，0，长度-偏移量）；
        }
    }
  

该类不是线程安全的，但我想如果有人想在单独的线程上处理大量字符串，那么他们可以在 ThreadLocal 琐事中提供 4-8 个 StripAlgorithm 实现

实例

1. 我用作参考RatchetFreak2EdStaub1GreyCat2 解决方案。我很惊讶这在我的机器上表现不佳。。然后我错误地认为“救助”机制不起作用，最后我把它移走了。它的性能飙升。然后我想“等一下”，然后我意识到这种情况总是有效，只是最后会更好。我不知道为什么。

   <前><代码> ...
   6.RatchetFreak2EdStaub1GreyCat早期保释 3508771.93 3.54x +3.9%
   ...
   2.RatchetFreak2EdStaub1GreyCatLateBail 6060606.06 6.12x +13.9%

2. 该测试并非 100% 准确。起初我是一个利己主义者，我把测试放在了一系列算法上。它在第一次运行时出现了一些糟糕的结果，然后我在最后移动了它（让其他人为我预热 JVM:)），然后它首先出现。

结果

哦，当然还有结果。 Windows 7，jdk1.8.0_111 在相对较旧的计算机上，因此预计在较新的硬件和/或操作系统上会出现不同的结果。

    Rankings: (1.000.000 strings)
    17. StringReplaceAll                        990099.01   1.00x   +0.0%
    16. ArrayOfByteWindows1251                  1642036.12  1.66x   +65.8%
    15. StringBuilderCodePoint                  1724137.93  1.74x   +5.0%
    14. ArrayOfByteUTF8Const                    2487562.19  2.51x   +44.3%
    13. StringBuilderChar                       2531645.57  2.56x   +1.8%
    12. ArrayOfByteUTF8String                   2551020.41  2.58x   +0.8%
    11. ArrayOfCharFromArrayOfChar              2824858.76  2.85x   +10.7%
    10. RatchetFreak2                           2923976.61  2.95x   +3.5%
     9. RatchetFreak1                           3076923.08  3.11x   +5.2%
     8. ArrayOfCharFromStringCharAt             3322259.14  3.36x   +8.0%
     7. EdStaub1                                3378378.38  3.41x   +1.7%
     6. RatchetFreak2EdStaub1GreyCatEarlyBail   3508771.93  3.54x   +3.9%
     5. EdStaub1GreyCat1                        3787878.79  3.83x   +8.0%
     4. MatcherReplace                          4716981.13  4.76x   +24.5%
     3. RatchetFreak2EdStaub1GreyCat1           5319148.94  5.37x   +12.8%
     2. RatchetFreak2EdStaub1GreyCatLateBail    6060606.06  6.12x   +13.9%
     1. SteliosAdamantidis                      9615384.62  9.71x   +58.7%

    Rankings: (10.000.000 strings)
    17. ArrayOfByteWindows1251                  1647175.09  1.00x   +0.0%
    16. StringBuilderCodePoint                  1728907.33  1.05x   +5.0%
    15. StringBuilderChar                       2480158.73  1.51x   +43.5%
    14. ArrayOfByteUTF8Const                    2498126.41  1.52x   +0.7%
    13. ArrayOfByteUTF8String                   2591344.91  1.57x   +3.7%
    12. StringReplaceAll                        2626740.22  1.59x   +1.4%
    11. ArrayOfCharFromArrayOfChar              2810567.73  1.71x   +7.0%
    10. RatchetFreak2                           2948113.21  1.79x   +4.9%
     9. RatchetFreak1                           3120124.80  1.89x   +5.8%
     8. ArrayOfCharFromStringCharAt             3306878.31  2.01x   +6.0%
     7. EdStaub1                                3399048.27  2.06x   +2.8%
     6. RatchetFreak2EdStaub1GreyCatEarlyBail   3494060.10  2.12x   +2.8%
     5. EdStaub1GreyCat1                        3818251.24  2.32x   +9.3%
     4. MatcherReplace                          4899559.04  2.97x   +28.3%
     3. RatchetFreak2EdStaub1GreyCat1           5302226.94  3.22x   +8.2%
     2. RatchetFreak2EdStaub1GreyCatLateBail    5924170.62  3.60x   +11.7%
     1. SteliosAdamantidis                      9680542.11  5.88x   +63.4%

* Reflection -Voo 的回答

我在 更快 语句上加了一个星号。我认为在这种情况下，没有什么比反思更快的了。它改变字符串的内部状态并避免新的字符串分配。我不认为有人能打败它。

我尝试取消注释并运行 Voo 的算法，但出现 offset 字段不退出的错误。 IntelliJ 抱怨它也无法解析 count 。另外（如果我没有记错的话）安全管理器可能会切断对私有字段的反射访问，因此该解决方案将不起作用。这就是为什么这个算法没有出现在我的测试运行中。否则我很想看看自己，尽管我相信非反射解决方案不可能更快。

Answer 8

为什么直接使用“utf-8”字符集名称比使用预分配的 static const Charset.forName(“utf-8”) 产生更好的性能？

如果您的意思是 String#getBytes("utf-8") 等：这不应该更快 - 除了一些更好的缓存 - 因为 Charset.forName("utf-8")如果未缓存字符集，则在内部使用。

一件事可能是您使用不同的字符集（或者您的某些代码可能是透明的），但 StringCoding 中缓存的字符集不会改变。