Replicar String.split con StringTokenizer
https://stackoverflow.com/questions/986543
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
este y el hecho de que tengo mil millones de cadena a analizar , he intentado modificar mi código para aceptar StringTokenizer en lugar de String []
Lo único que queda entre mí y conseguir que el impulso deliciosa rendimiento x2 es el hecho de que cuando estás haciendo
"dog,,cat".split(",")
//output: ["dog","","cat"]
StringTokenizer("dog,,cat")
// nextToken() = "dog"
// nextToken() = "cat"
¿Cómo puedo lograr resultados similares con el StringTokenizer? ¿Hay maneras más rápidas de hacer esto?
Solución
¿Está en realidad sólo tokenizing de comas? Si es así, me gustaría escribir mi propia tokenizer - bien puede llegar a ser aún más eficiente que el propósito más general StringTokenizer que pueden buscar múltiples fichas, y se puede hacer que se comporte sin embargo lo desea. Para un caso simple tal uso, que puede ser una aplicación sencilla.
Si sería útil, incluso se podría implementar Iterable<String> y conseguir un mayor apoyo para la tipificación de bucle con potentes en lugar de la ayuda proporcionada por Enumeration StringTokenizer. Que me haga saber si desea que cualquier ayuda codificación de una bestia tan arriba -. En realidad no debería ser demasiado difícil
Además, me gustaría probar la ejecución de pruebas de rendimiento en los datos reales antes de saltar demasiado lejos de una solución existente. ¿Tiene alguna idea de qué parte de su tiempo de ejecución es realmente gastaron en String.split? Sé que tienes una gran cantidad de cadenas para analizar, pero si está haciendo algo significativo con ellos después, yo esperaría que para ser mucho más importante que la división.
Otros consejos
Después de juguetear con el href="http://java.sun.com/javase/6/docs/api/java/util/StringTokenizer.html" rel="noreferrer"> StringTokenizer clase ["dog", "", "cat"].
Además, la clase StringTokenizer se deja sólo por razones de compatibilidad, y el uso de String.split se encouaged. A partir de la especificación API para el StringTokenizer:
StringTokenizeres una clase de legado que se retiene para la compatibilidad razones aunque su uso es desalentado en nuevo código. Está recomienda que cualquier persona que busque este funcionalidad utilizar el métodosplitdeStringo lajava.util.regexpaquete en su lugar.
Dado que el problema es la supuestamente malos resultados de la método String.split, tenemos que encontrar una alternativa.
Nota: Digo "supuestamente mal desempeño", porque es difícil de determinar que cada caso de uso se va a dar lugar a la StringTokenizer siendo superior al método String.split. Además, en muchos casos, a menos que la tokenización de las cuerdas son de hecho el cuello de botella de la aplicación determinada por el perfil adecuado, siento que va a terminar siendo una optimización prematura, en todo caso. Me inclinaría a decir que escribir código que sea significativa y fácil de entender antes de aventurarse en la optimización.
Ahora, a partir de los requerimientos actuales, probablemente rodar nuestra propia tokenizer no sería demasiado difícil.
Rollo de nuestro propio tokenzier
El siguiente es un simple tokenizer escribí. Debo señalar que no hay optimizaciones de velocidad, ni hay error controles para evitar ir más allá del final de la cadena - esto es una implementación rápida y sucia-:
class MyTokenizer implements Iterable<String>, Iterator<String> {
String delim = ",";
String s;
int curIndex = 0;
int nextIndex = 0;
boolean nextIsLastToken = false;
public MyTokenizer(String s, String delim) {
this.s = s;
this.delim = delim;
}
public Iterator<String> iterator() {
return this;
}
public boolean hasNext() {
nextIndex = s.indexOf(delim, curIndex);
if (nextIsLastToken)
return false;
if (nextIndex == -1)
nextIsLastToken = true;
return true;
}
public String next() {
if (nextIndex == -1)
nextIndex = s.length();
String token = s.substring(curIndex, nextIndex);
curIndex = nextIndex + 1;
return token;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
El MyTokenizer tomará un String a tokenize y una String como delimitador, y utilizar el método String.indexOf para llevar a cabo la búsqueda de delimitadores. Tokens son producidos por el método String.substring.
Me Sospecho que puede haber algunas mejoras en el rendimiento de trabajo en la cadena a nivel char[] en lugar de a nivel String. Pero lo dejo como ejercicio para el lector.
La clase también implementa Iterable Iterator con el fin de aprovechar el for-each construcción de lazo que se introdujo en Java 5. StringTokenizer es un Enumerator, y no soporta el constructo for-each.
¿Es más rápido?
Con el fin de averiguar si esto es más rápido, me escribió un programa para comparar las velocidades en los cuatro métodos siguientes:
- El uso de
StringTokenizer. - El uso de la nueva
MyTokenizer. - El uso de
String.split. - Uso de expresión regular precompilado por
Pattern.compile.
En los cuatro métodos, el "dog,,cat" cadena se separó en tokens. Aunque el StringTokenizer se incluye en la comparación, cabe señalar que no devolverá el resultado deseado de ["dog", "", "cat].
El tokenizing se repitió durante un total de 1 millón de veces para dar tomar el tiempo suficiente para notar la diferencia en los métodos.
El código utilizado por el simple punto de referencia fue la siguiente:
long st = System.currentTimeMillis();
for (int i = 0; i < 1e6; i++) {
StringTokenizer t = new StringTokenizer("dog,,cat", ",");
while (t.hasMoreTokens()) {
t.nextToken();
}
}
System.out.println(System.currentTimeMillis() - st);
st = System.currentTimeMillis();
for (int i = 0; i < 1e6; i++) {
MyTokenizer mt = new MyTokenizer("dog,,cat", ",");
for (String t : mt) {
}
}
System.out.println(System.currentTimeMillis() - st);
st = System.currentTimeMillis();
for (int i = 0; i < 1e6; i++) {
String[] tokens = "dog,,cat".split(",");
for (String t : tokens) {
}
}
System.out.println(System.currentTimeMillis() - st);
st = System.currentTimeMillis();
Pattern p = Pattern.compile(",");
for (int i = 0; i < 1e6; i++) {
String[] tokens = p.split("dog,,cat");
for (String t : tokens) {
}
}
System.out.println(System.currentTimeMillis() - st);
Los resultados
Las pruebas fueron run usando Java SE 6 (build 1.6.0_12-b04), y los resultados fueron los siguientes:
Run 1 Run 2 Run 3 Run 4 Run 5
----- ----- ----- ----- -----
StringTokenizer 172 188 187 172 172
MyTokenizer 234 234 235 234 235
String.split 1172 1156 1171 1172 1156
Pattern.compile 906 891 891 907 906
Así que, como puede verse en la prueba limitada y sólo cinco carreras, el StringTokenizer de hecho salir el más rápido, pero el MyTokenizer entró como un segundo cierre. Entonces, String.split fue el más lento, y la expresión regular precompilado fue ligeramente más rápido que el método split.
Al igual que con cualquier pequeño punto de referencia, probablemente no es muy representativa de las condiciones de la vida real, por lo que los resultados deben tomarse con un grano (o un montículo) de sal.
Nota: Después de haber hecho algunos puntos de referencia rápidas, escáner resulta ser aproximadamente cuatro veces más lento que String.split. Por lo tanto, no utilice el escáner.
(estoy dejando el cargo para registrar el hecho de que Scanner es una mala idea en este caso (que se lee:. No me downvote por sugerir escáner, por favor ...))
Si se asume que está utilizando Java 1.5 o superior, intente escáner , que implementa Iterator<String>, como sucede:
Scanner sc = new Scanner("dog,,cat");
sc.useDelimiter(",");
while (sc.hasNext()) {
System.out.println(sc.next());
}
da:
dog
cat
Dependiendo de qué tipo de cadenas que necesita para tokenize, puede escribir su propio divisor basado en String.indexOf () por ejemplo. También puede crear una solución multi-núcleo para mejorar aún más el rendimiento, ya que la tokenización de cadenas es independiente el uno del otro. El trabajo en lotes de 100 cuerdas -Permite decir- por núcleo. Haga lo String.split () o watever más.
En lugar de StringTokenizer, podría intentar la clase StrTokenizer de Apache Commons Lang, que cito:
Esta clase se puede dividir una cadena en muchas cadenas más pequeñas. Su objetivo es hacer un trabajo similar al StringTokenizer, sin embargo, ofrece mucho más control y flexibilidad incluyendo la implementación de la interfaz ListIterator.
tokens vacíos pueden ser eliminados o devueltos como nulo.
Esto suena como lo que necesita, que pienso?
Se podría hacer algo así. No es perfecto, pero podría estar trabajando para usted.
public static List<String> find(String test, char c) {
List<String> list = new Vector<String>();
start;
int i=0;
while (i<=test.length()) {
int start = i;
while (i<test.length() && test.charAt(i)!=c) {
i++;
}
list.add(test.substring(start, i));
i++;
}
return list;
}
Si es posible se puede ommit la cosa lista y directamente hacer algo para la subcadena:
public static void split(String test, char c) {
int i=0;
while (i<=test.length()) {
int start = i;
while (i<test.length() && test.charAt(i)!=c) {
i++;
}
String s = test.substring(start,i);
// do something with the string here
i++;
}
}
En mi sistema El último método es más rápido que el StringTokenizer-solución, pero es posible que desee probar cómo funciona para usted. (Por supuesto que podría hacer este método un poco más corto por ommiting el {} de la segunda, mientras que mirada y, por supuesto, se puede utilizar un bucle for en lugar del bucle while-exterior e incluyendo el último i ++ en eso, pero yo no' t hacer eso aquí porque considero que mal estilo.
Bueno, la cosa más rápida que podría hacer sería para atravesar manualmente la cadena, por ejemplo,
List<String> split(String s) {
List<String> out= new ArrayList<String>();
int idx = 0;
int next = 0;
while ( (next = s.indexOf( ',', idx )) > -1 ) {
out.add( s.substring( idx, next ) );
idx = next + 1;
}
if ( idx < s.length() ) {
out.add( s.substring( idx ) );
}
return out;
}
Este (prueba informal) parece ser algo así como el doble de rápido de división. Sin embargo, es un poco peligroso para recorrer esta manera, por ejemplo, se romperá en comas escapado, y si al final necesidad de hacer frente a que en algún momento (debido a que su lista de mil millones de cuerdas tiene 3 escapado comas) en el momento de 'he permitido que probablemente va a terminar perdiendo algunos de los beneficios de velocidad.
En última instancia es probable que no vale la pena la molestia.
Yo recomendaría Splitter guayaba de Google.
He comparado con la prueba de coobird y obtuve los siguientes resultados:
StringTokenizer 104
Google guayaba divisor 142
String.split 446
expreg 299
Si la entrada está estructurado, se puede echar un vistazo al compilador JavaCC. Genera una clase java lectura de su entrada. Se vería así:
TOKEN { <CAT: "cat"> , <DOG:"gog"> }
input: (cat() | dog())*
cat: <CAT>
{
animals.add(new Animal("Cat"));
}
dog: <DOG>
{
animals.add(new Animal("Dog"));
}
