La forma más rápida de dividir una cadena delimitada en Java

10

Estoy construyendo un comparador que proporciona la capacidad de clasificación de varias columnas en una cadena delimitada. Actualmente estoy usando el método de división de la clase String como mi opción preferida para dividir la cadena sin procesar en tokens.

¿Es esta la mejor manera de convertir la cadena sin procesar en una matriz de cadenas? Ordenaré millones de filas, así que creo que el enfoque es importante.

Parece funcionar bien y es muy fácil, pero no estoy seguro si hay una forma más rápida en Java.

Así es como funciona el tipo en mi Comparador:

public int compare(String a, String b) {

    String[] aValues = a.split(_delimiter, _columnComparators.length);
    String[] bValues = b.split(_delimiter, _columnComparators.length);
    int result = 0;

    for( int index : _sortColumnIndices ) {
        result = _columnComparators[index].compare(aValues[index], bValues[index]);
        if(result != 0){
            break;
        }
    }
    return result;
}

Después de comparar los diversos enfoques, lo creas o no, el método de división fue el más rápido con la última versión de Java. Puede descargar mi comparador completo aquí: https://sourceforge.net/projects/multicolumnrowcomparator/

Constantin
fuente
55
Señalaré que la naturaleza de la respuesta a esta pregunta depende de la implementación de la jvm. El comportamiento de las cadenas (que comparten una matriz de respaldo común en OpenJDK, pero no en OracleJDK) difiere. Esta diferencia puede tener un impacto significativo en la división de cadenas y la creación de subcadenas, junto con la recolección de basura y las pérdidas de memoria. ¿Qué tan grandes son estas matrices? ¿Cómo lo estás haciendo ahora? ¿Consideraría una respuesta que crea un nuevo tipo Stringish en lugar de cadenas Java reales?
1
En particular, mire StringTokenizer nextToken que eventualmente llama al constructor privado String del paquete . Compare esto con los cambios documentados en la representación interna Cambios en la cadena realizada en Java 1.7.0_06
El tamaño de la matriz depende del número de columnas, por lo que es variable. Este comparador de columnas múltiples se pasa como un parámetro así: ExternalSort.mergeSortedFiles (fileList, new File ("BigFile.csv"), _comparator, Charset.defaultCharset (), false); La rutina de ordenación externa ordenará toda la cadena de la fila, en realidad es el comparador el que divide y clasifica según las columnas de ordenación
Constantin
Consideraría mirar los tokenizadores de lucene. Lucene puede usarse como una poderosa biblioteca de análisis de texto que funciona bien para tareas simples y complejas
Doug T.
Considere Apache Commons Lang's StringUtils.split[PreserveAllTokens](text, delimiter).
Restablece a Mónica el

Respuestas:

19

He escrito una prueba de referencia rápida y sucia para esto. Compara 7 métodos diferentes, algunos de los cuales requieren un conocimiento específico de los datos que se dividen.

Para la división básica de propósito general, Guava Splitter es 3.5 veces más rápido que String # split () y recomendaría usar eso. Stringtokenizer es un poco más rápido que eso y dividirse con indexOf es dos veces más rápido que otra vez.

Para ver el código y más información, visite http://demeranville.com/battle-of-the-tokenizers-delimited-text-parser-performance/

tom
fuente
Tengo curiosidad por saber qué JDK estabas usando ... y si fuera 1.6, estaría más interesado en ver un resumen de tus resultados en 1.7.
1
fue 1.6 creo. El código está allí como una prueba JUnit si desea ejecutarlo en 1.7. Nota: String.split realiza una coincidencia de expresiones regulares, que siempre será más lenta que la división en un solo carácter definido.
tom
1
Sí, sin embargo, para 1.6, el código StringTokenizer (y similar) llama a String.substring () que crea O (1) la nueva cadena usando la misma matriz de respaldo. Esto se cambió en 1.7 para hacer una copia de la parte necesaria de la matriz de respaldo en lugar de O (n). Esto podría tener un impacto singular en sus resultados, haciendo que la diferencia entre la división y StringTokenizer sea menor (ralentizando todo lo que usaba la subcadena antes).
1
Ciertamente verdad. La cuestión es que la forma en que funciona StringTokenizer ha pasado de "crear una nueva cadena, asignar 3 enteros" a "crear una nueva cadena, hacer una copia de la matriz de los datos", lo que cambiará la velocidad de esa parte. La diferencia entre los diversos enfoques puede ser menor ahora y sería interesante (si no es por otra razón que su interés) hacer un seguimiento con Java 1.7.
1
¡Gracias por ese artículo! Muy útil y se utilizará para comparar varios enfoques.
Constantin
5

Como escribe @Tom, un enfoque de tipo indexOf es más rápido que String.split(), ya que este último trata con expresiones regulares y tiene una sobrecarga adicional para ellos.

Sin embargo, un cambio de algoritmo que podría darte una súper velocidad. Suponiendo que este comparador se vaya a utilizar para ordenar sus ~ 100,000 cadenas, no escriba el Comparator<String>. Porque, en el curso de su clasificación, la misma cadena probablemente se comparará varias veces, por lo que la dividirá varias veces, etc.

Divida todas las Cadenas una vez en Cadenas [] s, y Comparator<String[]>ordene la Cadena []. Luego, al final, puedes combinarlos todos juntos.

Alternativamente, también podría usar un Mapa para almacenar en caché la Cadena -> Cadena [] o viceversa. por ejemplo (incompleto) También tenga en cuenta que está intercambiando memoria por velocidad, espero que tenga mucha RAM

HashMap<String, String[]> cache = new HashMap();

int compare(String s1, String s2) {
   String[] cached1 = cache.get(s1);
   if (cached1  == null) {
      cached1 = mySuperSplitter(s1):
      cache.put(s1, cached1);
   }
   String[] cached2 = cache.get(s2);
   if (cached2  == null) {
      cached2 = mySuperSplitter(s2):
      cache.put(s2, cached2);
   }

   return compareAsArrays(cached1, cached2);  // real comparison done here
}
user949300
fuente
Este es un buen punto.
tom
Sería necesario modificar el código de clasificación externa que se puede encontrar aquí: code.google.com/p/externalsortinginjava
Constantin
1
Probablemente sea más fácil usar un Mapa entonces. Ver editar.
user949300
Dado que esto es parte de un motor de clasificación externo (para manejar muchos más datos de los que posiblemente caben en la memoria disponible), realmente estaba buscando un "divisor" eficiente (sí, es un desperdicio dividir la misma cadena repetidamente, de ahí mi necesidad original de hacer esto lo más rápido posible)
Constantin
Al examinar brevemente el código de ExternalSort, parece que si borró su caché al final (o al inicio) de cada sortAndSave()llamada, entonces no debería quedarse sin memoria debido a una gran caché. En mi opinión, el código debe tener algunos ganchos adicionales, como disparar eventos o llamar a métodos protegidos de no hacer nada que los usuarios como usted podrían anular. (Además, no deberían ser todos los métodos estáticos para que puedan hacer esto) Es posible que desee ponerse en contacto con los autores y presentar una solicitud.
user949300
2

De acuerdo con estos puntos de referencia , StringTokenizer es más rápido para dividir cadenas, pero no devuelve una matriz que lo hace menos conveniente.

Si necesita ordenar millones de filas, le recomiendo usar un RDBMS.

Tulains Córdova
fuente
3
Eso estaba bajo JDK 1.6 - las cosas en las cadenas son fundamentalmente diferentes en 1.7 - vea java-performance.info/changes-to-string-java-1-7-0_06 (en particular, crear una subcadena ya no es O (1) pero más bien O (n)). El enlace señala que en 1.6 Pattern.split usó una creación de String diferente que String.substring ()). Vea el código vinculado en el comentario anterior para seguir el StringTokenizer.nextToken () y el constructor privado del paquete al que tuvo acceso.
1

Este es el método que uso para analizar archivos delimitados por tabulaciones grandes (1GB +). Tiene mucho menos gastos generales que String.split(), pero se limita a chardelimitador. Si alguien tiene un método más rápido, me gustaría verlo. Esto también se puede hacer de nuevo CharSequencey CharSequence.subSequence, pero eso requiere implementación CharSequence.indexOf(char)(consulte el método del paquete String.indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex)si está interesado).

public static String[] split(final String line, final char delimiter)
{
    CharSequence[] temp = new CharSequence[(line.length() / 2) + 1];
    int wordCount = 0;
    int i = 0;
    int j = line.indexOf(delimiter, 0); // first substring

    while (j >= 0)
    {
        temp[wordCount++] = line.substring(i, j);
        i = j + 1;
        j = line.indexOf(delimiter, i); // rest of substrings
    }

    temp[wordCount++] = line.substring(i); // last substring

    String[] result = new String[wordCount];
    System.arraycopy(temp, 0, result, 0, wordCount);

    return result;
}
vallismortis
fuente
¿Has comparado esto con String.split ()? Si es así, ¿cómo se compara?
Jay Elston
@JayElston En un archivo de 900 MB, redujo el tiempo de división de 7,7 segundos a 6,2 segundos, por lo que es un 20% más rápido. Sigue siendo la parte más lenta de mi análisis de matriz de punto flotante. Supongo que gran parte del tiempo restante es la asignación de matriz. Podría ser posible reducir la asignación de la matriz mediante el uso de un enfoque basado en tokenizer con un desplazamiento en el método, que comenzaría a parecerse más al método que cité anteriormente en el código.
vallismortis