1. java
  2. android
  3. c#
  4. .net
  5. javascript
  6. php
  7. jquery
  8. html
  9. sql

Busca de palavras em arquivo

Olá pessoal,

estou com o seguinte desafio: tenho que otimizar a busca de uma palavra num texto (dado num arquivo txt). A busca inicialmente dada é a sequencial. Minha tarefa é torná-la mais eficiente. Eu tentei a estratégia de fazer uma busca binária com base no tamanho das Strings (que foram ordenadas com mergeSort - não posso utilizar coleções). Ou seja, caso a string buscada for menor(ou maior) que a do meio, chamo um método que faz a varredura apenas na "metade" em questão.

O ponto é que, ao executar, chequei qual das duas versões gastariam mais tempo: a minha. Gostaria de ajuda para otimizar esse código. Se houver alguma sugestão para uma solução mais eficiente que esta também aceito :D

  • O vetor palavras contém todas as strings do arquivo, ordenadas em tamanho.
public String [] busca(String buscada){

        int w2 = buscada.length();

        if(palavras != null){

            int ini = 0;
            int fim = palavras.length - 1;

            while (ini <= fim){
                int meio = (ini + fim)/2;

                if (palavras[meio].equals(buscada)){

                    String [] resultado = new String[1];
                    resultado[0] = palavras[meio];
                    return resultado;
                }

                int w1 = palavras[meio].length();

                if (w1 < w2) {
                    ini = meio + 1;
                    String [] resultado = new String[1];
                    resultado[0] = varredura(palavras,ini,fim,buscada);
                    return resultado;
                } 
                else{ 
                    fim = meio - 1;
                    String [] resultado = new String[1];
                    resultado[0] = varredura(palavras,ini,fim,buscada);
                    return resultado;
                }
            }

        }
        else{
            System.out.println("Arquivo não foi carregado!");    
        }

        // Se chegamos até aqui, ou o arquivo não foi carregado, ou 
        // a palavra buscada não existe. Então devolvemos "null".
        return null;
    }


    public static String varredura (String [] v, int ini, int fim, String buscada){

        for (int i = ini; i < fim; i++){
            if (v[i].equalsIgnoreCase(buscada)){
                return v[i];
            }
        }

        return null;
    }

O código inicial concedido:

public String [] busca(String buscada){

        if(palavras != null){

            // para cada palavra presente no vetor "palavras"...
            for(String p : palavras){

                // ... se a palavra for igual à palavra buscada...
                if(p.equals(buscada)){

                    // ... então a busca foi bem sucedida. Criamos
                    // um vetor de uma posição e adicionamos ao mesmo
                    // a palavra encontrada.
                    String [] resultado = new String[1];
                    resultado[0] = p;
                    return resultado;
                }
            }
        }
        else{
            System.out.println("Arquivo não foi carregado!");    
        }

        // Se chegamos até aqui, ou o arquivo não foi carregado, ou 
        // a palavra buscada não existe. Então devolvemos "null".
        return null;
    }
  1. Você vai ver essas setas em qualquer página de pergunta. Com elas, você pode dizer se uma pergunta ou uma resposta foram relevantes ou não.
  2. Edite sua pergunta ou resposta caso queira alterar ou adicionar detalhes.
  3. Caso haja alguma dúvida sobre a pergunta, adicione um comentário. O espaço de respostas deve ser utilizado apenas para responder a pergunta.
  4. Se o autor da pergunta marcar uma resposta como solucionada, esta marca aparecerá.
  5. Clique aqui para mais detalhes sobre o funcionamento do GUJ!

0 resposta

Não é a resposta que estava procurando? Procure outras perguntas com as tags busca string ou faça a sua própria pergunta.