Каков самый быстрый способ удалить все непечатаемые символы из a Stringв Java?

До сих пор я пробовал и измерял 138-байтовую 131-символьную строку:

• String replaceAll()- самый медленный метод
  • 517009 результатов / сек
• Предварительно скомпилируйте шаблон, затем используйте Matcher's replaceAll()
  • 637836 результатов / сек
• Используйте StringBuffer, получайте кодовые точки, используя codepointAt()одну за другой, и добавляйте в StringBuffer
  • 711946 результатов / сек
• Используйте StringBuffer, получайте символы charAt()по одному и добавляйте в StringBuffer
  • 1052964 результатов / сек
• Предварительно выделить char[]буфер, получить символы, используя charAt()один за другим, и заполнить этот буфер, затем преобразовать обратно в String
  • 2022653 результатов / сек
• Предварительно выделите 2 char[]буфера - старый и новый, получите все символы для существующей String сразу, используя getChars(), перебирайте старый буфер один за другим и заполняйте новый буфер, затем конвертируйте новый буфер в String - моя собственная самая быстрая версия
  • 2502502 результатов / сек
• То же материал с 2 буферов - только с использованием byte[], getBytes()и с указанием кодировки , как «UTF-8»
  • 857485 результатов / сек
• То же самое с двумя 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» напрямую дает лучшую производительность, чем использование предварительно выделенной static const Charset.forName("utf-8")?

Обновить

• Предложение от храповика дает впечатляющие результаты 3105590 результатов / сек, улучшение + 24%!
• Предложение Эда Стауба дает еще одно улучшение - 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)
  • 64-разрядная серверная виртуальная машина Java HotSpot (TM) (сборка 19.1-b02, смешанный режим)

Различные алгоритмы показывают в конечном итоге разные результаты при разном наборе входных данных. Я провел тест в 3 режимах:

Та же единственная строка

Этот режим работает с той же единственной строкой, предоставленной StringSourceклассом в качестве константы. Разборки таковы:

 Операции / с │ Алгоритм
──────────────────────────────────────────
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
  994727 │ ArrayOfByteUTF8String
  918 611 │ ArrayOfByteUTF8Const
  756086 │ Матчер Заменить
  598945 │ StringReplaceAll
  460 045 │ ArrayOfByteWindows1251

В виде диаграммы: _{(источник: greycat.ru )}

Несколько строк, 100% строк содержат управляющие символы

Поставщик исходной строки предварительно сгенерировал множество случайных строк с использованием набора символов (0..127) - таким образом, почти все строки содержат хотя бы один управляющий символ. Алгоритмы получали строки из этого предварительно сгенерированного массива циклически.

 Операции / с │ Алгоритм
──────────────────────────────────────────
2 123 142 │ Voo1
──────────────────────────────────────────
1 782 214 │ EdStaub1
1 776199 │ EdStaub1GreyCat1
1694628 │ ArrayOfCharFromStringCharAt
1 481 481 │ ArrayOfCharFromArrayOfChar
1 460 067 │ RatchetFreak2EdStaub1GreyCat1
1 438 435 │ RatchetFreak2EdStaub1GreyCat2
1 366 494 │ RatchetFreak2
1 349 710 │ RatchetFreak1
  893 176 │ ArrayOfByteUTF8String
  817127 │ ArrayOfByteUTF8Const
  778 089 │ StringBuilderChar
  734 754 │ StringBuilderCodePoint
  377 829 │ ArrayOfByteWindows1251
  224 140 │ Матчер Заменить
  211 104 │ StringReplaceAll

В виде диаграммы: _{(источник: greycat.ru )}

Несколько строк, 1% строк содержат управляющие символы

То же, что и предыдущее, но только 1% строк был сгенерирован с управляющими символами - остальные 99% были сгенерированы с использованием набора символов [32..127], поэтому они вообще не могли содержать управляющие символы. Эта синтетическая нагрузка является наиболее близкой к реальному применению этого алгоритма у меня.

 Операции / с │ Алгоритм
──────────────────────────────────────────
3 711 952 │ Voo1
──────────────────────────────────────────
2 851 440 │ EdStaub1GreyCat1
2 455 796 │ EdStaub1
2 426007 │ ArrayOfCharFromStringCharAt
2 347 969 │ RatchetFreak2EdStaub1GreyCat2
2 242 152 │ RatchetFreak1
2 171 553 │ ArrayOfCharFromArrayOfChar
1922707 │ RatchetFreak2EdStaub1GreyCat1
1 857 010 │ RatchetFreak2
1 023 751 │ ArrayOfByteUTF8String
  939 055 │ StringBuilderChar
  907 194 │ ArrayOfByteUTF8Const
  841 963 │ StringBuilderCodePoint
  606 465 │ Матчер Заменить
  501 555 │ StringReplaceAll
  381 185 │ ArrayOfByteWindows1251

В виде диаграммы: _{(источник: greycat.ru )}

Мне очень сложно решить, кто дал лучший ответ, но, учитывая, что лучшее решение для реального приложения было предложено / вдохновлено Эдом Стаубом, я думаю, было бы справедливо отметить его ответ. Спасибо всем, кто принял в этом участие, ваш вклад был очень полезным и бесценным. Не стесняйтесь запускать набор тестов на своем компьютере и предлагать еще лучшие решения (рабочее решение JNI, кто-нибудь?).

Рекомендации

• Репозиторий GitHub с набором тестов

Если разумно встроить этот метод в класс, который не используется совместно потоками, вы можете повторно использовать буфер:

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% или около того, как я понимаю в лучшем случае.

Если это должно использоваться с потенциально большими строками и "утечка" памяти вызывает беспокойство, можно использовать слабую ссылку.

использование 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);

Что ж, я победил текущий лучший метод (решение урода с предварительно выделенным массивом) примерно на 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/svs. 2616120.89ops/sдля старого варианта. Я совершенно уверен, что единственный способ победить это - написать это на C (возможно, нет) или какой-то совершенно другой подход, о котором пока никто не думал. Хотя я абсолютно не уверен, стабильно ли время на разных платформах - по крайней мере, дает надежные результаты на моем компьютере (Java7, Win7 x64).

Вы можете разделить задачу на несколько параллельных подзадач, в зависимости от количества процессоров.

Я был настолько свободен и написал небольшой тест для разных алгоритмов. Это не идеально, но я беру минимум 1000 запусков данного алгоритма 10000 раз по случайной строке (по умолчанию около 32/200% непечатаемых). Это должно позаботиться о таких вещах, как сборщик мусора, инициализация и т. Д. - накладных расходов не так много, чтобы у любого алгоритма не было хотя бы одного запуска без особых препятствий.

Не особо хорошо задокументировано, ну да ладно. Вот и все - я включил оба алгоритма храповика и базовую версию. На данный момент я произвольно инициализирую строку длиной 200 символов с равномерно распределенными символами в диапазоне [0, 200).

Наркоман IANA на низкоуровневой производительности Java, но пробовали ли вы развернуть основной цикл ? Похоже, что это может позволить некоторым процессорам выполнять проверки параллельно.

Кроме того, здесь есть несколько забавных идей для оптимизации.

почему использование имени кодировки «utf-8» напрямую дает лучшую производительность, чем использование предварительно выделенной статической const Charset.forName («utf-8»)?

Если вы имеете в виду и String#getBytes("utf-8")т.д .: Это не должно быть быстрее - за исключением некоторого лучшего кеширования - поскольку Charset.forName("utf-8")используется внутри, если кодировка не кешируется.

Одна вещь может заключаться в том, что вы используете разные кодировки (или, возможно, часть вашего кода прозрачна), но кодировка, кешированная в StringCoding, не меняется.