Como fazer pesquisa binária em um arquivo txt? – c# java arquivo

Pergunta:


Estou com um arquivo txt que armazena dados de vários livros (exemplo abaixo) gostaria de fazer uma pesquisa binária que retorne a linha que estiver com o primeiro campo (ISBN do livro) equivalente a busca, sem carregar todo o arquivo na memória (considerando que o arquivo pode ter um tamanho muito grande) é possível fazer este tipo de pesquisa? Em C# ou Java.

OBS.: As linhas tem tamanho variado.

inserir a descrição da imagem aqui

Autor da pergunta William Pereira

Comunidade

Vou descrever o que você precisa fazer, se der, mais tarde eu tento escrever algum código. Mas já adianto que não dá para fazer da forma mais precisa porque suas linhas não tem tamanho fixo. Então você tem que fazer mais ou menos o que um banco de dados faz, com a diferença que o banco de dados organizou os dados para isto.

Você já aprendeu como acessar o arquivo randomicamente na sua pergunta anterior.

Você precisará saber o tamanho do arquivo, algo como System.IO.FileInfo(path).Length. Veja a documentação.

Você também precisará no Indexof para achar a quebra de linha.

Estratégia de busca

Como não pode ler tudo para a memória terá que ler em páginas de dados. Minha sugestão é que estas páginas tenham 4096 bytes. É o tamanho da página de memória atualmente e o provável tamanho da página de de dados (cluster) em disco. Então ler e guardar um tamanho menor que isto será desperdício porque este é o tamanho mínimo que será lido fisicamente no disco. Com tamanhos menores você acabará lendo mais de uma vez os mesmos dados. É verdade que nas próximas vezes o sistema operacional provavelmente pegará do cache e não do disco. Esse tamanho nem fará cosquinha na memória, afinal depois de terminar de usar esse buffer ele poderá ser descartado pelo GC.

Dividindo o tamanho total do arquivo pelo tamanho do buffer você encontrará a quantidade páginas existentes no arquivo.

Você irá ler essas páginas que certamente conterá várias linhas (pelo padrão que você mostrou, não estou dizendo que é garantido que terá, mas parece que sim).

Já que você não tem como definir o tamanho das linhas você vai trabalhar com a páginas e aplicará a busca binária nas páginas que funcionarão como o elemento básico de procura.

Provavelmente você lerá a primeira página (conforme indicado na outra pergunta que respondi), a última, a do meio e depois sucessivamente irá ler a metade da metade atual indo para a metade anterior ou posterior conforme a comparação.

Como você chega na página. Pense nas página numeradas de zero até a última menos um. Por exemplo, se tiver 20 páginas, elas serão numeradas de 0 à 19. E o início de cada página é seu número vezes o tamanho. A primeira será 0 X 4096, ou seja posição 0 do arquivo. A página 10 será 10 X 4096 e ela deverá começar ser lida na posição 40960. Sempre vai ler 4096 bytes seguintes, conforme o tamanho do buffer. Não importa que a última provavelmente não terá todo buffer preenchido.

Em cada página lida você vai ter que procurar por todos os códigos ISBN. Pelo que entendi, ele vem sempre depois de uma quebra de linha, então vai procurar com IndexOf pelo(s) caractere(s) de quebra de linha. Aí é pegar os 14 caracteres seguintes. Este é o ISBN. Aí você compara com o que está procurando. isto será um loop para achar todas as quebras de linha e consequentemente o código que vem logo em seguida. Dentro da página provavelmente é melhor deixar a busca binária de lado e fazer a busca sequencial. Como dica saiba que existe IndexOf com offset para fazer a busca de uma posição intermediária, ou seja, achar uma string começando em uma posição específica.

Se qualquer um for igual, você achou e pode encerrar o algoritmo da busca (falta só pegar toda a linha). Se o último código achado dentro da página for menor que o que procura vai procurar na meta posterior. Se o primeiro código achado dentro da página for maior do que está procurando, vai procurar na metade anterior. Se já olhou em todas as páginas possíveis (não existem mais páginas entre a atual e a última lidas) e não achou em nenhuma página, o código não existe.

Existe a possibilidade de um código começar nesta página e terminar só na outra. Você vai ter que analisar isto e se detectar que o código não está completo ler a próxima página em disco para pegar pegar o resto do código.

Isto é o que você provavelmente terá que fazer também quando achar a linha que você quer. Existe uma probabilidade razoável de que a linha que você quer e achou está iniciando em uma página mas ela só termina (ou seja, tem outra quebra de linha) na outra página, então tem que ler a outra página para ter a linha por completo.

Tudo o que eu descrevi é o processo de busca binária, nenhum segredo. O que tem de diferente é a estratégia de busca por áginas para dar uma informação estável de quebra de partes do arquivo.

Conclusão

Percebe-se que isto não é o ideal, mas dadas as circunstâncias esta é a solução possível. Não entrei em tantos detalhes, pode ter algumas coisas que podem ser feitas de uma forma melhor, algumas verificações extras. Para fazer um exercício, é mais ou menos isso, para por em produção tem que arquitetar melhor.

A melhor abordagem para uma busca em arquivo texto vai depender da frequência com que o arquivo é modificado, do tempo necessário para percorrer o arquivo e do uso da funcionalidade de busca.

Dependendo do tamanho do tempo de leitura do arquivo, uma busca binária pode ser ineficiente no sentido de que não fará bom uso da CPU e do sistema de buffer e leitura do meio em questão. Nem toda leitura randômica ou aleatória é realmente sem custo. Ver artigo.

Indexação

Se o arquivo não for atualizado com frequência, você pode criar um índice em memória que mantém as posições de cada linha vinculadas ao ISBN.

Veja um exemplo simples em Java:

//lê e mantém um índice do ISBN
static class IndiceArquivo {

    //posição da linha
    static class PosicaoLinha {
        long inicio;
        int tamanho;
        PosicaoLinha(long inicio, int tamanho) {
            this.inicio = inicio;
            this.tamanho = tamanho;
        }
    }

    //índice
    Map<String, PosicaoLinha> indicePorIsbn = new HashMap<>();

    //arquivo
    Path arquivo;

    //construtor
    IndiceArquivo(Path arquivo) {
        this.arquivo = arquivo;
        montarIndice();
    }

    //lê todos os ISBNs
    void montarIndice() {
        try (BufferedReader reader = Files.newBufferedReader(arquivo, Charset.forName("UTF-8"))) {
            String linha;
            long posicao = 0;
            while ((linha = reader.readLine()) != null) {
                indicePorIsbn.put(linha.substring(0, linha.indexOf('-')), new PosicaoLinha(posicao, linha.getBytes().length));
                posicao += linha.getBytes().length + System.getProperty("line.separator").length();
            }
        } catch (IOException e) {
            throw new RuntimeException("Erro ao ler o arquivo!");
        }
    }

    //encontra a posição indexada da linha do livro e então recupera a linha completa do arquivo
    Optional<String> getLinhaIsbn(String isbn) {
        return Optional.ofNullable(isbn)
                .map(k -> indicePorIsbn.get(k))
                .map(p -> {
                    try {
                        ByteBuffer buffer = ByteBuffer.allocate(p.tamanho);
                        Files.newByteChannel(arquivo).position(p.inicio).read(buffer);
                        System.out.println(new String(buffer.array(), "UTF-8"));
                        return new String(buffer.array(), "UTF-8");
                    } catch (IOException e) {
                        throw new RuntimeException("Erro ao ler o arquivo!");
                    }
                });
    }
}

E para testar:

public static void main(String[] args) throws Exception {
    //cria arquivo de exemplo
    Path arquivo = Files.createTempFile("meu", "teste");
    Files.write(arquivo, (
                    "123456789-titulo 1-autor 1-2012" + System.getProperty("line.separator") +
                    "234567890-titulo 2-autor 3-2013" + System.getProperty("line.separator") +
                    "345678901-titulo 3-autor 3-2014"
            ).getBytes("UTF-8"));

    //monta o índice
    IndiceArquivo indice = new IndiceArquivo(arquivo);

    //faz busca e verifica resultado
    Optional<String> resultadoBusca = indice.getLinhaIsbn("234567890");
    if (resultadoBusca.isPresent()) {
        System.out.println("Encontrou: " + resultadoBusca.get());
    } else {
        System.out.println("Nao Encontrou");
    }
}

Lendo tudo

Se o arquivo não for realmente tão grande e a leitura do arquivo não for necessária com muita frequência, simplesmente leia o arquivo todo usando um stream:

static Optional<String> buscarIsbn(String isbn) throws Exception {
    Path arquivo = Paths.get("/meu/arquivo/grande.txt");
    String inicioLinha = isbn + "-";
    try (Stream<String> lines = Files.lines(arquivo)) {
        return lines.filter(linha -> linha.startsWith(inicioLinha)).findFirst();
    } catch (IOException e) {
        throw new Exception("Erro ao ler o arquivo!");
    }
}

Exemplo de uso:

public static void main(String[] args) throws Exception {
    Optional<String> resultadoBusca = buscarIsbn("1234567890");
    if (resultadoBusca.isPresent()) {
        //encontrou
    } else {
        //não encontrou
    }
}

Cópia do arquivo alinhado

Outra alternativa é fazer uma cópia do arquivo com os caracteres alinhados, assim a busca binária pode ser feita com facilidade:

static void alinharArquivo(int tamanhoMaximoLinha) throws Exception {
    Path arquivoOriginal = Paths.get("/meu/arquivo/grande.txt");
    Path arquivoAlinhado = Paths.get("/meu/arquivo/grande-alinhado.txt");
    try (
            Stream<String> linhas = Files.lines(arquivoOriginal);
            PrintWriter saida = new PrintWriter(Files.newBufferedWriter(arquivoAlinhado))) {
        linhas.forEachOrdered(l -> saida.format("%s-" + tamanhoMaximoLinha + "s", l));
    } catch (IOException e) {
        throw new Exception("Erro ao ler o arquivo!");
    }
}

Considerações

Se uma funcionalidade depende de uma grande quantidade de dados, sendo crítica para o usuário e frequentemente usada, a melhor saída é considerar a migração para um banco de dados ou tecnologia adequada.

Caso a dependência de arquivos texto seja necessária, outra possibilidade seria dividir o arquivo logicamente em grupos, assim você consegue limitar a quantidade de informações pesquisadas em uma busca. Por exemplo, se dividir o arquivo grande em dez arquivos menores de acordo com alguns dos primeiros dígitos do ISBN, em cada busca seria possível determinar qual o arquivo a ser pesquisado e assim ignorar os outros 9.

Entretanto, considere também que qualquer solução como essa tem possibilidade de criar severas limitações no futuro. Por exemplo, se for necessário buscar por autor você ainda terá que percorrer os dez arquivos.

Portanto, eu diria que em linhas gerais a melhor abordagem é usar um banco de dados e a segunda melhor é utilizar um índice. Caso o índice seja muito grande para a memória, você poderia usar outro arquivo para armazená-lo com formato posicional de forma que fosse viável fazer uma busca binária.

Fonte

Related Posts:

Qual a diferença entre AppCompatActivity e Activity? – android android-activity
Pergunta: Qual a diferença da AppCompatActivity para Activity ? A partir de qual versão a AppCompatActivity foi adicionada ao Android? Autor da pergunta Luhhh A diferença reside ...
Como abreviar palavras em PHP? – php string
Pergunta: Possuo informações comuns como nome de pessoas e endereços, e preciso que elas contenham no máximo 30 caracteres sem cortar palavras. Exemplo: 'Avenida Natalino João Brescansin' ...
Qual é a finalidade de um parêntese vazio numa declaração Lambda? – c# expressões-lambda característica-linguagem
Pergunta: Criei um exemplo de uma declaração Lambda sem argumentos, entretanto, estou com duvidas referente a omissão do parêntese vazio () na declaração. Veja o exemplo: class ...
Boas práticas para URI em API RESTful – api rest restful
Pergunta: Estou com dúvida em relação às URIs de alguns recursos da api que estou desenvolvendo. Tenho os recursos projetos e atividades com relação 1-N, ...
Dúvidas sobre a integração do MySQL com Java – java mysql netbeans
Pergunta: Estou criando um sistema no NetBeans, utilizando a linguagem Java e o banco de dados MySQL. Escrevi o seguinte código para realizar a conexão ...
Qual é a finalidade da pasta Model do framework Inphinit? – php inphinit
Pergunta: No Inphinit micro-framework existe a pasta Model que fica dentro da pasta application, e nela é onde ficam as classes, mas eu estou muito ...
Uso do ‘@’ em variáveis – javascript typescript coffeescript
Pergunta: Vejo em algumas linguagens que compilam para javascript, como TypeScript e CoffeeScript, o uso do @ em variáveis, como também, casos em que o ...
Qual tamanho máximo um arquivo JSON pode ter? – json arquivo
Pergunta: Vou dar um exemplo para conseguir explicar minha duvida: Preciso recuperar informação de imagens vindas de uma API, esse banco de imagens me retorna JSON's ...
O que é Teste de Regressão? – terminologia engenharia-de-software testes
Pergunta: Na matéria de Teste de Software o professor abordou um termo chamado Teste de Regressão, isto dentro da disciplina de teste de software. Sendo ...
O que é um construtor da linguagem? – php característica-linguagem
Pergunta: Em PHP, já li e ouvi várias vezes a respeito dos Construtores da Linguagem. Os casos que sempre ouvi falar deles foi em casos ...
Função intrínseca para converter numérico para string – cobol
Pergunta: Estou a tentar saber se existe alguma função intrínseca do COBOL para converter um data numérico para string sem precisar usar a cláusula REDEFINES: ( ...
Porque usar implements? – java android
Pergunta: Qual a diferença entre usar btn.setOnClickListener(new OnClickListener() { e public class MainActivity extends Activity implements OnClickListener{ Estive fazendo um curso de Android e meu professor falou que ...
O que é XHTML e quando deve ser usado? – html xml xhtml
Pergunta: O que eu sei é que o XHTML precisa ser XML válido. Isso implica, por exemplo, que todas as tags precisam ser fechadas. Por ...
Uma placa aceleradora de vídeo pode melhorar o desempenho não-gráfico? [fechada] – desempenho
Pergunta: Para desenvolver em Ruby on Rails, eu utilizo aqui uma máquina virtual do VirtualBox com Ubuntu Server 14.04 sem interface gráfica instalada. Recentemente descobri uma ...
Concat() VS Union() – c# .net
Pergunta: Qual a diferença entre Concat() e Union() ? Quando usar Concat() e quando usar Union() ? Somente pode ser usado em list ? ...

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *