Replica String.split con StringTokenizer
-
13-09-2019 - |
Domanda
questo , e il fatto che ho miliardi di stringa da analizzare , ho cercato di modificare il mio codice di accettare StringTokenizer al posto di String []
L'unica cosa che resta tra me e ottenere quella spinta deliziosa prestazioni x2 è il fatto che quando si sta facendo
"dog,,cat".split(",")
//output: ["dog","","cat"]
StringTokenizer("dog,,cat")
// nextToken() = "dog"
// nextToken() = "cat"
Come posso ottenere risultati simili con lo StringTokenizer? Ci sono modi più veloci per fare questo?
Soluzione
Si tratta unicamente in realtà creazione di token su virgole? Se è così, mi piacerebbe scrivere il mio tokenizer - potrebbe anche finire per essere ancora più efficiente rispetto alla finalità più generale StringTokenizer che può guardare per più gettoni, e si può farlo comportare tuttavia si desidera. Per tale caso semplice utilizzo, può essere una semplice implementazione.
Se sarebbe utile, si potrebbe anche implementare Iterable<String>
e ottenere il supporto migliorato per la ciclo con la tipizzazione forte invece del supporto fornito da Enumeration
StringTokenizer
. Fatemi sapere se si vuole alcun aiuto codifica una bestia up -. In realtà non dovrebbe essere troppo difficile
Inoltre, mi piacerebbe provare l'esecuzione di test di prestazioni su dati effettivi prima di saltare troppo lontano da una soluzione esistente. Avete qualche idea di come gran parte del vostro tempo di esecuzione è effettivamente spesi in String.split
? So che hai un sacco di stringhe di analizzare, ma se si sta facendo qualcosa di significativo con loro in seguito, mi aspetto che per essere molto più significativo rispetto alla divisione.
Altri suggerimenti
Dopo armeggiare con la href="http://java.sun.com/javase/6/docs/api/java/util/StringTokenizer.html" rel="noreferrer"> StringTokenizer
classe ["dog", "", "cat"].
Inoltre, la classe StringTokenizer
viene lasciato solo per motivi di compatibilità, e l'uso di String.split
è encouaged. Dalla specifica API per StringTokenizer
:
StringTokenizer
è una classe legacy che viene mantenuto per la compatibilità ragioni sebbene il suo uso è scoraggiato nel nuovo codice. È raccomandato che chi cerca questo funzionalità utilizzare il metodosplit
diString
ojava.util.regex
pacchetto, invece.
Dato che il problema è il presunto scarso rendimento della metodo String.split
, abbiamo bisogno di trovare un'alternativa.
Nota: Sto dicendo "performance presumibilmente poveri" perché è difficile determinare che ogni caso d'uso sta per portare alla StringTokenizer
essere superiore al metodo String.split
. Inoltre, in molti casi, a meno che la tokenizzazione delle corde sono davvero il collo di bottiglia della domanda, determinata da una corretta profilazione, sento che finirà per essere un'ottimizzazione prematura, se non altro. Sarei propenso a dire scrivere il codice che è significativo e facile da capire prima di avventurarsi sull'ottimizzazione.
Ora, dalle esigenze attuali, probabilmente a rotazione nostra tokenizer non sarebbe troppo difficile.
Stendere la nostra tokenzier!
La seguente è una semplice tokenizzatore che ho scritto. Vorrei sottolineare che non ci sono ottimizzazioni di velocità, né v'è errore controlli per evitare di andare oltre la fine della stringa - questa è un'implementazione rapida e-sporca:
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();
}
}
Il MyTokenizer
vorrà un String
per tokenize e String
come delimitatore, e utilizzare il metodo String.indexOf
per eseguire la ricerca di delimitatori. Gettoni sono prodotte con il metodo String.substring
.
Vorrei sospetto che ci potrebbero essere alcuni miglioramenti delle prestazioni, lavorando sulla corda a livello char[]
piuttosto che a livello String
. Ma lascio che fino come un esercizio per il lettore.
La classe implementa anche Iterable
Iterator
al fine di sfruttare la for-each
ciclo costrutto che è stato introdotto in Java 5. StringTokenizer
è un Enumerator
, e non supporta il costrutto for-each
.
E 'più veloce?
Al fine di scoprire se questo è più veloce, ho scritto un programma per confrontare le velocità nei seguenti quattro metodi:
- L'utilizzo di
StringTokenizer
. - L'utilizzo del nuovo
MyTokenizer
. - L'utilizzo di
String.split
. - L'utilizzo di espressioni regolari precompilato da
Pattern.compile
.
Nei quattro metodi, il "dog,,cat"
stringa è stato separato in token. Anche se il StringTokenizer
è incluso nel confronto, si deve rilevare che non restituirà il risultato desiderato di ["dog", "", "cat]
.
La creazione di token è stato ripetuto per un totale di 1 milione di volte per dare prendere abbastanza tempo per notare la differenza nei metodi.
Il codice utilizzato per il semplice punto di riferimento è stato il seguente:
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);
I risultati
I test sono stati run usando Java SE 6 (build 1.6.0_12-B04), ed i risultati sono stati i seguenti:
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
Quindi, come si può vedere dal test limitati e solo cinque piste, il StringTokenizer
ha infatti uscito il più veloce, ma il MyTokenizer
è entrato come una stretta secondo. Poi, String.split
era il più lento, e l'espressione regolare precompilato è stato leggermente più veloce rispetto al metodo split
.
Come per ogni piccolo punto di riferimento, probabilmente non è molto rappresentativo delle condizioni di vita reale, quindi i risultati devono essere presi con un grano (o un tumulo) di sale.
Nota: Avendo fatto alcuni benchmark rapidi, scanner risulta essere circa quattro volte più lento di String.split. Quindi, non usare scanner.
(Sto lasciando il posto per registrare il fatto che Scanner è una cattiva idea in questo caso (Leggi come:. Non mi downvote per suggerire scanner, per favore ...))
Supponendo che si sta utilizzando Java 1.5 o superiore, provare Scanner , che implementa Iterator<String>
, come accade:
Scanner sc = new Scanner("dog,,cat");
sc.useDelimiter(",");
while (sc.hasNext()) {
System.out.println(sc.next());
}
dà:
dog
cat
A seconda del tipo di stringhe che dovete tokenize, è possibile scrivere il proprio splitter sulla base di String.indexOf (), per esempio. Si potrebbe anche creare una soluzione multi-core per migliorare le prestazioni ancora di più, come la tokenizzazione di stringhe è indipendente l'uno dall'altro. I lavori per lotti di -Consente dire- 100 stringhe per core. Fare la String.split () o watever altro.
Invece di StringTokenizer, si potrebbe provare la classe StrTokenizer da Apache Commons Lang, che cito:
Questa classe può dividere una stringa in molte corde più piccoli. Ha lo scopo di fare un lavoro simile a StringTokenizer, tuttavia offre molto più controllo e flessibilità compreso che implementa l'interfaccia ListIterator.
gettoni vuoti possono essere rimossi o restituiti come nullo.
Questo suona come quello che vi serve, penso?
Si potrebbe fare qualcosa di simile. Non è perfetto, ma potrebbe funzionare per voi.
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;
}
Se possibile si può ommit la cosa List e fare direttamente qualcosa al sottostringa:
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++;
}
}
Sul mio sistema l'ultimo metodo è più veloce rispetto alla StringTokenizer-soluzione, ma si potrebbe desiderare di provare come funziona per voi. (Naturalmente si potrebbe rendere questo metodo un po 'più corto dal ommiting il {} del secondo, mentre aspetto e, naturalmente, si potrebbe usare un ciclo for, invece del ciclo while-esterno e compreso l'ultimo i ++ in questo, ma io didn' t farlo qui perché ritengo che un cattivo stile.
Bene, la cosa più veloce che si potrebbe fare sarebbe quella di attraversare manualmente la stringa, per esempio
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;
}
Questa (test informale) sembra essere qualcosa di simile a due volte più veloce di divisione. Tuttavia, è un po 'pericoloso per scorrere in questo modo, ad esempio, si romperà il virgole sfuggiti, e se si finisce per dover affrontare che a un certo punto (perché la vostra lista di un miliardo di stringhe ha 3 sfuggito virgole) per il momento si 'Ho permesso che probabilmente finisce per perdere un po' del vantaggio di velocità.
In definitiva è probabilmente non vale la pena preoccuparsi.
Suggerirei Guava Splitter
di Google.
Ho confrontato con coobird di prova ed ha ottenuto i seguenti risultati:
StringTokenizer 104
Google Guava Splitter 142
String.split 446
regexp 299
Se l'input è strutturato, si può avere uno sguardo al compilatore JavaCC. Esso genera una classe Java leggere il vostro input. Si sarebbe simile a questa:
TOKEN { <CAT: "cat"> , <DOG:"gog"> }
input: (cat() | dog())*
cat: <CAT>
{
animals.add(new Animal("Cat"));
}
dog: <DOG>
{
animals.add(new Animal("Dog"));
}