Replica String.split con StringTokenizer

https://stackoverflow.com/questions/986543

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 metodo split di String o java.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"));
   }

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow