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

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

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

  • String replaceAll()самый медленный метод
    • 517009 результатов / сек
  • Предварительно replaceAll() шаблон, затем используйте Matcher replaceAll()
    • 637836 результатов / сек
  • Используйте StringBuffer, получайте кодовые страницы с помощью codepointAt() один за другим и добавьте в StringBuffer
    • 711946 результатов / сек
  • Используйте StringBuffer, получайте символы, используя charAt() один за другим и добавляйте к StringBuffer
    • 1052964 результатов / сек
  • Предварительно charAt() буфер char[] , получите символы, используя charAt() один за другим, и заполните этот буфер, затем преобразуйте обратно в String
    • 2022653 результатов / сек
  • Preallocate 2 char[] buffers – старый и новый, получить все символы для существующей строки сразу с помощью getChars() , поочередно перебирать старый буфер и заполнять новый буфер, а затем конвертировать новый буфер в String – моя самая быстрая версия
    • 2502502 результатов / сек
  • Тот же материал с двумя буферами – только с использованием 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 = ' ') { newChars[newLen] = ch; newLen++; } } s = new String(newChars, 0, newLen); 

Любые мысли о том, как сделать это еще быстрее?

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

Обновить

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

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

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

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

  Ops / s │ Алгоритм
 ──────────┼──────────────────────────────
 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://sofru.miximages.com/optimization/os-chart-single.png

Несколько строк, 100% строк содержат контрольные символы

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

  Ops / s │ Алгоритм
 ──────────┼──────────────────────────────
 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://sofru.miximages.com/optimization/os-chart-multi100.png

Несколько строк, 1% строк содержат контрольные символы

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

  Ops / s │ Алгоритм
 ──────────┼──────────────────────────────
 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://sofru.miximages.com/optimization/os-chart-multi1.png

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

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

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

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

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

Ну, я побил свои лучшие методы (решение freak с предустановленным массивом) примерно на 30%. Как? Продавая мою душу.

Как я уверен, все, кто следил за обсуждением, до сих пор знают, что это почти полностью нарушает принцип базового программирования, но хорошо. В любом случае, следующее работает только в том случае, если используемый массив символов строки не используется совместно с другими строками – если он делает, тот, кто должен отлаживать это, будет иметь все права, чтобы убить вас (без вызовов подстроки () и использования этого в литеральных строках это должно работать, поскольку я не понимаю, почему 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).

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

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

Кроме того, у этого есть интересные идеи для оптимизации.

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

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

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

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

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

  • Лучший способ заменить многие строки - обфускация в C #
  • Сортировка одной строки в Java
  • Закрытие сканера вызывает java.util.NoSuchElementException
  • Разделить строку с точкой в ​​качестве разделителя
  • В чем преимущество непрерывности String?
  • Создайте переменную java.lang.String
  • Конкатенация строк: оператор concat () vs "+"
  • Получить строку после символа
  • Байт Java-массива с массивом строк в байт
  • Получить переменную по имени из строки
  • Получить индекс n-го вхождения строки?
  • Давайте будем гением компьютера.