¿Cuál es la forma más rápida de eliminar todos los caracteres no imprimibles de a Stringen Java?

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

• String's replaceAll()- método más lento
  • 517009 resultados / seg
• Precompile un patrón, luego use Matcher's replaceAll()
  • 637836 resultados / seg
• Use StringBuffer, obtenga puntos de código codepointAt()uno por uno y añádalos a StringBuffer
  • 711946 resultados / seg
• Use StringBuffer, obtenga caracteres charAt()uno por uno y agregue a StringBuffer
  • 1052964 resultados / seg
• Preasigne un char[]búfer, obtenga caracteres charAt()uno por uno y llene este búfer, luego conviértalo de nuevo a String
  • 2022653 resultados / seg
• Preasigne 2 char[]búferes: antiguo y nuevo, obtenga todos los caracteres para String existente a la vez usando getChars(), itere sobre el búfer antiguo uno por uno y llene el nuevo búfer, luego convierta el nuevo búfer en String: mi propia versión más rápida
  • 2502502 resultados / seg
• Misma materia con 2 buffers - solamente utilizando byte[], getBytes()y que especifican codificación como "UTF-8"
  • 857485 resultados / seg
• Lo mismo con 2 byte[]búferes, pero especificando la codificación como una constanteCharset.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 es una cosa sensata)
  • 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 sobre cómo hacerlo aún más rápido?

Puntos de bonificación por responder una pregunta muy extraña: ¿por qué usar el nombre del juego de caracteres "utf-8" produce directamente un mejor rendimiento que usar la constante estática preasignada Charset.forName("utf-8")?

Actualizar

• La sugerencia del fanático del trinquete produce un rendimiento impresionante de 3105590 resultados por segundo, ¡una mejora del + 24%!
• La sugerencia de Ed Staub arroja otra mejora: 3471017 resultados / segundo, un + 12% sobre el mejor anterior.

Actualización 2

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

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

• Debian sid
• Linux 2.6.39-2-amd64 (x86_64)
• Java instalado desde un paquete sun-java6-jdk-6.24-1, JVM se identifica como
  • Entorno de ejecución Java (TM) SE (compilación 1.6.0_24-b07)
  • Servidor VM Java HotSpot (TM) de 64 bits (compilación 19.1-b02, modo mixto)

Los diferentes algoritmos muestran en última instancia resultados diferentes dado un conjunto diferente de datos de entrada. Ejecuté un punto de referencia en 3 modos:

La misma cuerda única

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

 Ops / s │ Algoritmo
──────────┼──────────────────────────────
6535 947 │ Voo1
──────────┼──────────────────────────────
5350454 │ RatchetFreak2EdStaub1GreyCat1
5249343 │ EdStaub1
5002501 │ EdStaub1GreyCat1
4859086 │ ArrayOfCharFromStringCharAt
4295532 │ RatchetFreak1
4045307 │ ArrayOfCharFromArrayOfChar
2790178 │ RatchetFreak2EdStaub1GreyCat2
2583311 │ RatchetFreak2
1274 859 │ StringBuilderChar
1138174 │ StringBuilderCodePoint
  994727 │ ArrayOfByteUTF8String
  918611 │ ArrayOfByteUTF8Const
  756086 │ MatcherReplace
  598945 │ StringReplaceAll
  460 045 │ ArrayOfByteWindows1251

En forma de gráficos: _{(fuente: greycat.ru )}

Varias cadenas, el 100% de las cadenas contienen caracteres de control

El proveedor de cadenas de origen generó muchas cadenas aleatorias utilizando el juego de caracteres (0..127), por lo que casi todas las cadenas contenían al menos un carácter de control. Los algoritmos recibieron cadenas de esta matriz pregenerada en forma de turnos.

 Ops / s │ Algoritmo
──────────┼──────────────────────────────
2123142 │ Voo1
──────────┼──────────────────────────────
1782 214 │ EdStaub1
1776199 │ EdStaub1GreyCat1
1694628 │ ArrayOfCharFromStringCharAt
1484481 │ ArrayOfCharFromArrayOfChar
1460 067 │ RatchetFreak2EdStaub1GreyCat1
1438435 │ RatchetFreak2EdStaub1GreyCat2
1366494 │ RatchetFreak2
1349710 │ RatchetFreak1
  893176 │ ArrayOfByteUTF8String
  817127 │ ArrayOfByteUTF8Const
  778089 │ StringBuilderChar
  734754 │ StringBuilderCodePoint
  377829 │ ArrayOfByteWindows1251
  224140 │ MatcherReplace
  21114 │ StringReplaceAll

En forma de gráficos: _{(fuente: greycat.ru )}

Varias cadenas, el 1% de las cadenas contienen caracteres de control

Igual que antes, pero solo el 1% de las cadenas se generó con caracteres de control; el otro 99% se generó usando el conjunto de caracteres [32..127], por lo que no podían contener caracteres de control en absoluto. Esta carga sintética es la más cercana a la aplicación de este algoritmo en el mundo real en mi casa.

 Ops / s │ Algoritmo
──────────┼──────────────────────────────
3711952 │ Voo1
──────────┼──────────────────────────────
2851440 │ EdStaub1GreyCat1
2455 796 │ EdStaub1
2426007 │ ArrayOfCharFromStringCharAt
2347969 │ RatchetFreak2EdStaub1GreyCat2
2242152 │ RatchetFreak1
2 171 553 │ ArrayOfCharFromArrayOfChar
1922707 │ RatchetFreak2EdStaub1GreyCat1
1857 010 │ RatchetFreak2
1023751 │ ArrayOfByteUTF8String
  939055 │ StringBuilderChar
  907194 │ ArrayOfByteUTF8Const
  841963 │ StringBuilderCodePoint
  606465 │ MatcherReplace
  501555 │ StringReplaceAll
  381185 │ ArrayOfByteWindows1251

En forma de gráficos: _{(fuente: greycat.ru )}

Es muy difícil para mí decidir quién proporcionó la mejor respuesta, pero dada la aplicación del mundo real que mejor solución 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 funcional, ¿alguien?).

Referencias

• Repositorio de GitHub con una suite de evaluación comparativa

Si es razonable incrustar 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 ...

Esta es una gran victoria: aproximadamente un 20%, según entiendo el mejor caso actual.

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

el uso de una 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 microoptimizació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);

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

Como estoy seguro de que 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 esto tendrá todo el derecho de decidir matarte (sin llamadas a substring () y usar esto en cadenas literales esto debería funcionar ya que no veo por qué la JVM internará cadenas únicas leídas desde una fuente externa). Aunque no olvide asegurarse de que el código de referencia no lo haga, eso es extremadamente probable y obviamente ayudaría 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 prueba que obtiene 3477148.18ops/sfrente 2616120.89ops/sa la variante anterior. Estoy bastante seguro de que la única forma de superar eso podría ser escribirlo en C (aunque probablemente no) o algún enfoque completamente diferente en el que nadie haya pensado hasta ahora. Aunque no estoy absolutamente seguro de si el tiempo es estable en diferentes plataformas, produce resultados confiables en mi caja (Java7, Win7 x64) al menos.

Puede dividir la tarea en varias subtareas paralelas, según la cantidad del procesador.

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 en una cadena aleatoria (con aproximadamente 32/200% no imprimibles de forma predeterminada). Eso debería ocuparse de cosas como GC, inicialización, etc., 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í tanto los algoritmos de Ratchet Freak como la versión básica. En este momento, inicializo aleatoriamente una cadena de 200 caracteres de longitud con caracteres distribuidos uniformemente en el rango [0, 200).

Adicto al rendimiento de Java de bajo nivel de IANA, pero ¿ha intentado desenrollar su bucle principal ? Parece que podría permitir que algunas CPU realicen comprobaciones en paralelo.

Además, esto tiene algunas ideas divertidas para optimizaciones.

¿Por qué usar el nombre del juego de caracteres "utf-8" directamente produce un mejor rendimiento que usar el juego de caracteres constante estático preasignado Charset.forName ("utf-8")?

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

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