Replicando String.split com StringTokenizer

https://stackoverflow.com/questions/986543

13-09-2019
|

Pergunta

este , eo fato de que eu tenho bilhões de corda para analisar , eu tentei modificar meu código para aceitar StringTokenizer em vez de string []

A única coisa que resta entre mim e recebendo esse impulso delicioso desempenho x2 é o fato de que quando você está fazendo

"dog,,cat".split(",")
//output: ["dog","","cat"]

StringTokenizer("dog,,cat")
// nextToken() = "dog"
// nextToken() = "cat"

Como posso obter resultados semelhantes com o StringTokenizer? Existem mais rápido maneiras de fazer isso?

Solução

Você realmente só tokenizing em vírgulas? Se assim for, eu escrever meu próprio tokenizer - ele pode muito bem acabar por ser ainda mais eficiente do que o objectivo mais geral StringTokenizer que pode olhar para várias fichas, e você pode torná-lo comportar-se, contudo, você gostaria. Para tal um caso de uso simples, pode ser uma implementação simples.

Se seria útil, você pode até mesmo implementar Iterable<String> e obter suporte melhorado-for-loop com tipagem forte em vez do apoio Enumeration fornecido pelo StringTokenizer. Deixe-me saber se você quiser alguma ajuda na codificação tal uma besta up -. Ele realmente não deve ser muito difícil

Além disso, eu tente executar testes de desempenho em seus dados reais antes de pular muito longe de uma solução existente. Você tem alguma idéia de como muito do seu tempo de execução é realmente gasto em String.split? Eu sei que você tem um monte de cordas para analisar, mas se você está fazendo algo significativo com eles depois, eu esperaria que ser muito mais significativa do que a divisão.

Outras dicas

Depois de mexer com a StringTokenizer classe , eu não poderia encontrar uma maneira de satisfazer os requisitos para ["dog", "", "cat"] retorno.

Além disso, a classe StringTokenizer é deixado só por razões de compatibilidade, eo uso de String.split é encouaged. A partir da especificação API para o StringTokenizer:

StringTokenizer é uma classe legado que é mantido para compatibilidade razões embora seu uso seja desencorajado no novo código. Isto é recomendou que qualquer um que procura este funcionalidade usar o método split de String ou o java.util.regex pacote em vez.

Uma vez que a questão é supostamente fraco desempenho do String.split método, precisamos encontrar uma alternativa.

Nota: Eu estou dizendo "supostamente mau desempenho", porque é difícil de determinar que cada caso de uso vai resultar na StringTokenizer ser superior ao método String.split. Além disso, em muitos casos, a menos que o tokenization das cordas são realmente o gargalo do pedido determinada pelo perfil adequado, sinto que ele vai acabar sendo uma otimização prematura, se alguma coisa. Eu estaria inclinado a dizer escrever código que é significativo e fácil de entender antes de se aventurar na otimização.

Agora, a partir das exigências atuais, provavelmente rolar nossa própria tokenizer não seria muito difícil.

Role nossa própria tokenzier!

O seguinte é um simples tokenizer que eu escrevi. Devo observar que não há otimizações de velocidade, nem há erro-verificações para evitar indo além do fim da string - esta é uma implementação rápida e suja:

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();
  }
}

O MyTokenizer vai demorar um String tokenizar e uma String como um delimitador, e usar o método String.indexOf para executar a busca por delimitadores. Tokens são produzidos pelo método String.substring.

Eu suspeito que poderia haver algumas melhorias de desempenho por trabalhar na corda ao nível char[] em vez de no nível String. Mas vou deixar isso como um exercício para o leitor.

A classe também implementa Iterable Iterator , a fim de tirar proveito da for-each loop de construção que foi introduzido em Java 5. StringTokenizer é um Enumerator, e não suporta a construção for-each.

É mais rápido?

A fim de descobrir se este é mais rápido, eu escrevi um programa para comparar velocidades nos quatro métodos seguintes:

Use of StringTokenizer.
O uso do novo MyTokenizer.
Use of String.split.
O uso de expressões regulares pré-compilados por Pattern.compile .

Nos quatro métodos, o "dog,,cat" cadeia foi separado em fichas. Embora o StringTokenizer está incluído na comparação, deve-se notar que não irá devolver o resultado desejado de ["dog", "", "cat].

O tokenizing foi repetido para um total de 1 milhão de vezes para dar ter tempo suficiente para notar a diferença nos métodos.

O código usado para o benchmark simples foi o seguinte:

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);

Os resultados

Os testes foram run usando Java SE 6 (compilação 1.6.0_12-b04), e os resultados foram os seguintes:

                   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

Então, como pode ser visto a partir do teste limitado e apenas cinco corridas, o StringTokenizer se de fato sair o mais rápido, mas o MyTokenizer veio como um próximo 2nd. Então, String.split foi o mais lento, e a expressão regular pré-compilados foi ligeiramente mais rápido do que o método split.

Tal como acontece com qualquer pequena referência, ele provavelmente não é muito representativo das condições da vida real, de modo que os resultados devem ser tomadas com um grão (ou um montículo) de sal.

Nota: Depois de ter feito alguns benchmarks rápidas, Scanner acaba por ser cerca de quatro vezes mais lento do que String.split. Por isso, não use Scanner.

(Eu estou deixando o cargo para gravar o fato de que Scanner é uma má idéia, neste caso (leia-se:. Não downvote me para sugerir Scanner, por favor ...))

Assumindo que você está usando Java 1.5 ou superior, tente Scanner , que implementa Iterator<String>, como acontece:

Scanner sc = new Scanner("dog,,cat");
sc.useDelimiter(",");
while (sc.hasNext()) {
    System.out.println(sc.next());
}

dá:

dog

cat

Dependendo do tipo de cordas que você precisa para tokenizar, você pode escrever seu próprio divisor baseado em String.indexOf (), por exemplo. Você também pode criar uma solução multi-core para melhorar o desempenho ainda mais, como o uso de token de cordas é independente um do outro. Trabalho em lotes de -Permite dizer- 100 cordas por núcleo. Faça o String.split () ou watever mais.

Ao invés de StringTokenizer, você pode tentar a classe StrTokenizer de Apache Commons Lang, que cito:

Esta classe pode dividir uma string em muitas cordas menores. Destina-se a fazer um trabalho semelhante ao StringTokenizer, no entanto, ele oferece muito mais controle e flexibilidade, incluindo a implementação da interface ListIterator.

símbolos vazios podem ser removidos ou devolvido como nulo.

Isso soa como o que você precisa, eu acho?

Você poderia fazer algo parecido. Não é perfeito, mas pode estar trabalhando para você.

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 possível, você pode omitir a coisa lista e directamente fazer algo para a substring:

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++;
    }
}

No meu sistema o último método é mais rápido do que o StringTokenizer-solução, mas você pode querer testar como funciona para você. (Claro que você poderia fazer este método um pouco mais curto por ommiting o {} do segundo enquanto olhar e, claro, você poderia usar um loop for em vez do while-loop externo e incluindo o último i ++ para isso, mas eu não' t fazer isso aqui porque considero que o estilo ruim.

Bem, a coisa mais rápida que você poderia fazer seria a de percorrer manualmente a corda, por exemplo,

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 (teste informal) parece ser algo como duas vezes mais rápido dividida. No entanto, é um pouco perigoso para iterate Desta forma, por exemplo, ele vai quebrar em vírgulas escaparam, e se você acabar precisando que lidar com isso em algum momento (porque a sua lista de um bilhão de cordas tem 3 escaparam vírgulas) pelo tempo que você 've permitiu que você provavelmente vai acabar perdendo alguns dos benefícios de velocidade.

Em última análise, é provavelmente não vale a pena.

Eu recomendaria Splitter Goiaba do Google.
Comparei-o com coobird de teste e tem os seguintes resultados:

StringTokenizer 104
Google Guava Splitter 142
String.split 446
regexp 299

Se a sua entrada é estruturada, você pode ter um olhar para o compilador JavaCC. Ele gera uma classe java lendo sua entrada. Ele ficaria assim:

TOKEN { <CAT: "cat"> , <DOG:"gog"> }

input: (cat() | dog())*


cat: <CAT>
   {
   animals.add(new Animal("Cat"));
   }

dog: <DOG>
   {
   animals.add(new Animal("Dog"));
   }

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow