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

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



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




  • строки replaceAll() -самый медленный метод


    • результаты 517009 / сек



  • предварительная компиляция шаблона, а затем использовать совпадений по replaceAll()


    • 637836 результаты / сек



  • использовать StringBuffer, получить кодовые точки с помощью codepointAt() один за другим и добавить в StringBuffer


    • 711946 результаты / сек



  • используйте StringBuffer, получить символы с помощью charAt() один за другим и добавить в StringBuffer


    • 1052964 результаты / сек



  • назначить char[] буфер, получить символы с помощью charAt() один за другим и заполнить этот буфер, а затем преобразовать обратно в строку


    • 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% улучшение!

  • предложение Эд Стауб дает еще одно улучшение-3471017 результаты / сек, а +12% к предыдущему лучшему.


обновление 2



я старался изо всех сил, чтобы собрать все предлагаемые решения и его кросс-мутации и опубликовал его как небольшие рамки бенчмаркинга на github. В настоящее время он имеет 17 алгоритмов. Один из них - "особенный" -Voo1 алгоритм (предоставленный SO user Voo) использует сложные трюки отражения, таким образом достигая звездных скоростей, но он портит состояние строк JVM, таким образом, он сравнивается отдельно.



вы можете проверить его и запустить его, чтобы определить результаты на вашем поле. Вот краткое изложение результатов, которые у меня есть. Это спецификации:




  • Debian sid

  • Linux 2.6.39-2-amd64 (x86_64)

  • Java устанавливается из пакета sun-java6-jdk-6.24-1, JVM идентифицирует себя как


    • 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


в виде диаграммы:
тот же однострочный график http://www.greycat.ru/img/os-chart-single.png



несколько строк, 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


в виде диаграммы:
несколько строк, 100% концентрация http://www.greycat.ru/img/os-chart-multi100.png



несколько строк, 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


в намеченный форма:
несколько строк, концентрация 1% http://www.greycat.ru/img/os-chart-multi1.png



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



ссылки



726   7  

7 ответов:

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

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

etc...

Это большой выигрыш-20% или около того, как я понимаю текущий лучший случай.

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

9  
2011-08-23 23:47:28

используя 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]='';//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);
24  
2011-08-23 16:58:04

Ну, я избил текущий лучший метод (решение freak с предварительно распределенным массивом) примерно на 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).

9  
2011-08-24 17:27:25

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

2  
2011-08-23 16:37:09

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

и этой есть некоторые интересные идеи для оптимизации.

1  
2017-05-23 15:26:28

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

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

1  
2011-08-23 17:52:06

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

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

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

0  
2011-08-23 16:22:21

Comments

    Ничего не найдено.
Click here to cancel reply.