Pregunta La forma más rápida de quitar todos los caracteres no imprimibles de una cadena Java


¿Cuál es la forma más rápida de quitar todos los caracteres no imprimibles de un String en Java?

Hasta ahora lo he probado y medido en String de 138 bytes y 131 caracteres:

  • Instrumentos de cuerda replaceAll() - el método más lento
    • 517009 resultados / seg
  • Precompila un Patrón, luego usa el de Matcher replaceAll()
    • 637836 resultados / seg
  • Use StringBuffer, obtenga puntos de código usando codepointAt() uno por uno y anexar a StringBuffer
    • 711946 resultados / seg
  • Use StringBuffer, obtenga caracteres usando charAt() uno por uno y anexar a StringBuffer
    • 1052964 resultados / seg
  • Preasignar un char[] buffer, obtener caracteres usando charAt() uno por uno y llene este búfer, luego vuelva a convertirlo en Cadena
    • 2022653 resultados / seg
  • Preasignar 2 char[] búferes: antiguo y nuevo, obtenga todos los caracteres de la cadena existente de una vez usando getChars(), itera sobre el buffer viejo uno por uno y llena el nuevo buffer, luego convierte el nuevo buffer a String - mi propia versión más rápida
    • 2502502 resultados / seg
  • Lo mismo con 2 búferes, solo con byte[], getBytes() y especificando la codificación como "utf-8"
    • 857485 resultados / seg
  • Lo mismo con 2 byte[] buffers, pero especificando la codificación como una constante Charset.forName("utf-8")
    • 791076 resultados / seg
  • Lo mismo con 2 byte[] búferes, pero especificando la codificación como codificación local de 1 byte (apenas una cosa sensata que hacer)
    • 370164 resultados / seg

Mi mejor intento fue el siguiente:

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

¿Alguna idea de cómo hacerlo aún más rápido?

Puntos de bonificación por responder a una pregunta muy extraña: por qué el uso del nombre de conjunto de caracteres "utf-8" proporciona un mejor rendimiento que el uso de const estást pre-asignado Charset.forName("utf-8")?

Actualizar

  • Sugerencia de monstruo de trinquete rinde un rendimiento impresionante de 3105590 resultados / seg, ¡una mejora de + 24%!
  • Sugerencia de Ed Staub produce otra mejora: 3471017 resultados / seg, a + 12% sobre el mejor anterior.

Actualización 2

Hice todo lo posible para recopilar todas las soluciones propuestas y sus mutaciones cruzadas y lo publiqué como un pequeño marco de referencia en github. Actualmente tiene 17 algoritmos. Uno de ellos es "especial" - Voo1 algoritmo (proporcionado por SO usuario Voo) emplea intrincados trucos de reflexión para lograr velocidades estelares, pero estropea el estado de las cadenas de JVM, por lo que se compara por separado.

Le invitamos a echarle un vistazo y ejecutarlo para determinar los resultados en su caja. Aquí hay un resumen de los resultados que obtuve en el mío. Son especificaciones:

  • Sid de Debian
  • Linux 2.6.39-2-amd64 (x86_64)
  • Java instalado desde un paquete sun-java6-jdk-6.24-1, JVM se identifica a sí misma como
    • Java (TM) SE Runtime Environment (compilación 1.6.0_24-b07)
    • Java HotSpot (TM) 64-Bit Server VM (compilación 19.1-b02, modo mixto)

Distintos algoritmos muestran finalmente resultados diferentes dado un conjunto diferente de datos de entrada. Corrí un punto de referencia en 3 modos:

Misma cadena individual

Este modo funciona en una misma cadena única proporcionada por StringSourceclase como una constante. El enfrentamiento es:

 Ops / s │ Algoritmo
──────────┼──────────────────────────────
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 │ MatcherRecambiar
  598 945 │ StringReplaceAll
  460 045 │ ArrayOfByteWindows1251

En forma de cuadro: Mismo gráfico de cuerda única http://www.greycat.ru/img/os-chart-single.png

Varias cadenas, 100% de cadenas contienen caracteres de control

El proveedor de cadenas fuente pre-generó muchas cadenas aleatorias usando el conjunto de caracteres (0..127), por lo tanto, casi todas las cadenas contenían al menos un carácter de control. Los algoritmos recibieron cadenas de esta matriz pregenerada en modo round-robin.

 Ops / s │ Algoritmo
──────────┼──────────────────────────────
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 │ MatcherRecambiar
  211 104 │ StringReplaceAll

En forma de cuadro: Varias cadenas, 100% de concentración http://www.greycat.ru/img/os-chart-multi100.png

Varias cadenas, 1% de cadenas contienen caracteres de control

Igual que en el caso anterior, pero solo el 1% de las cadenas se generó con caracteres de control: otro 99% se generó al usar el juego de caracteres [32..127], por lo que no pudieron contener ningún tipo de control. Esta carga sintética es lo más parecido a la aplicación en el mundo real de este algoritmo en mi lugar.

 Ops / s │ Algoritmo
──────────┼──────────────────────────────
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

En forma de cuadro: Varias cadenas, concentración del 1% http://www.greycat.ru/img/os-chart-multi1.png

Es muy difícil para mí decidir quién proporcionó la mejor respuesta, pero dado que la mejor solución de la aplicación del mundo real fue dada / inspirada por Ed Staub, creo que sería justo marcar su respuesta. Gracias a todos los que participaron en esto, su aporte fue muy útil e invaluable. Siéntase libre de ejecutar el conjunto de pruebas en su caja y proponer soluciones aún mejores (¿solución JNI de trabajo, alguien?).

Referencias


76
2017-08-23 13:10


origen


Respuestas:


Si es razonable insertar este método en una clase que no se comparte entre subprocesos, puede reutilizar el búfer:

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 ...

Esto es una gran ganancia: 20% más o menos, ya que entiendo el mejor caso actual.

Si esto se va a utilizar en cadenas potencialmente grandes y la "fuga" de memoria es una preocupación, se puede usar una referencia débil.


9
2017-08-23 19:32



usar 1 matriz de caracteres podría funcionar un poco mejor

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

y evité repetidas llamadas a s.length();

otra micro-optimización que podría funcionar es

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

24
2017-08-23 13:20



Bueno, he superado el mejor método actual (la solución de Freak con la matriz preasignada) en aproximadamente un 30% de acuerdo con mis medidas. ¿Cómo? Al vender mi alma

Como estoy seguro, todos los que han seguido la discusión hasta ahora saben que esto viola prácticamente cualquier principio básico de programación, pero bueno. De todos modos, lo siguiente solo funciona si la matriz de caracteres utilizada de la cadena no se comparte entre otras cadenas; si lo hace, quien tenga que depurar tendrá todo el derecho de decidir matarte (sin llamadas a subcadena () y usar esto en cadenas literales esto debería funcionar ya que no veo por qué la JVM internaría cadenas únicas leídas de una fuente externa). Aunque no se olvide de asegurarse de que el código de referencia no lo haga, es muy probable que esto ayude a la solución de reflexión.

De todos modos aquí vamos:

    // 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;
    }

Para mi cadena de pruebas que se pone 3477148.18ops/s vs. 2616120.89ops/s para la vieja variante. Estoy bastante seguro de que la única forma de vencer eso podría ser escribirlo en C (probablemente no así) o en un enfoque completamente diferente que nadie haya pensado hasta ahora. Aunque no estoy seguro si el tiempo es estable en diferentes plataformas, al menos produce resultados confiables en mi caja (Java7, Win7 x64).


9
2017-08-24 12:55



Puede dividir la tarea en varias subtareas paralelas, dependiendo de la cantidad del procesador.


2
2017-08-23 13:37



IANA adicta al rendimiento de java de bajo nivel, pero ¿has probado desenrollando su ciclo principal? Parece que podría permitir que algunas CPU realicen comprobaciones en paralelo.

También, esta tiene algunas ideas divertidas para optimizaciones.


1
2017-08-23 13:24



Era tan libre y escribí un pequeño punto de referencia para diferentes algoritmos. No es perfecto, pero tomo el mínimo de 1000 ejecuciones de un algoritmo dado 10000 veces sobre una cadena aleatoria (con aproximadamente 32/200% no imprimibles por defecto). Eso debería encargarse de cosas como GC, inicialización, etcétera. No hay tanta sobrecarga que ningún algoritmo debería tener al menos una ejecución sin muchos obstáculos.

No está especialmente bien documentado, pero bueno. Aquí vamos - Incluí los algoritmos de trinquete y la versión básica. En este momento, inicializo aleatoriamente una cadena de 200 caracteres de largo con caracteres uniformemente distribuidos en el rango [0, 200).


1
2017-08-23 14:52



¿Por qué el uso del nombre de conjunto de caracteres "utf-8" proporciona un mejor rendimiento que el uso de const estáticas preestablecidas Charset.forName ("utf-8")?

Si te refieres a String#getBytes("utf-8") etc .: Esto no debería ser más rápido, a excepción de un mejor almacenamiento en caché, ya que Charset.forName("utf-8")se usa internamente, si el juego de caracteres no está en la memoria caché.

Una cosa podría ser que estés usando diferentes conjuntos de caracteres (o tal vez parte de tu código lo haga de forma transparente), pero el conjunto de caracteres almacenado en caché StringCoding no cambia


0
2017-08-23 13:22