Trabalho byte a byte com arquivos

Especial para

Vamos começar

No nível 18, começaram as primeiras tarefas de leitura de arquivo byte por byte: ler o arquivo, encontrar os bytes mínimo/máximo ou exibi-lo de forma ordenada, etc.

As pessoas aqui são muito inteligentes. Eles conhecem as coleções e sabem que podem classificá-las e inseri-las. As coleções são um mecanismo poderoso. E muitos nem os usavam antes do JavaRush. É claro que é recomendável estudá-los e tentar acertá-los nos lugares errados. Então. Tomemos um problema que não está nas tarefas (para que não haja spoilers na hora de resolvê-lo), mas existem outros muito semelhantes:

Digite o nome do arquivo no console
Leia todos os bytes de um arquivo.
Ignorando as repetições, classifique-as por bytecode em ordem decrescente.
Mostrar
Fechar fluxo de E/S

Exemplo de bytes de um arquivo de entrada 44 83 44 Exemplo de saída 83 44 Introduzimos adicionalmente variáveis startTimee finishTimepara registrar o tempo de execução do programa. Para o cálculo usei i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64 (exemplos de programas nas opções 1-2 foram retirados do fórum info.javarush, eles são ligeiramente modificado apenas para classificação em ordem crescente, ok - ou seja, eles são REAIS!!)

Vamos resolver isso de frente:

// Вариант 1. Загоняем в коллекцию и сортируем используя ее метод Collections.sort
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());
        long startTime = System.currentTimeMillis();

        ArrayList<Integer> listData = new ArrayList<Integer>();
        while (inputStream.available() > 0) listData.add(inputStream.read());
        inputStream.close();
        ArrayList<Integer> result = new ArrayList<Integer>(new HashSet<Integer>(listData));
        Collections.sort(result);

        while (!result.isEmpty()) {
            System.out.print(result.get(result.size()-1) + " ");
            result.remove(result.get(result.size()-1));
        }

        long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

Resolve tudo muito bem! O teste (se houvesse, teria passado com estrondo). Mas na vida existem poucos arquivos contendo apenas a frase “Mamãe lavou a moldura”. Vamos alimentar nosso programa com um arquivo de 46 MB (pelos padrões atuais, não parece muito). O que é isso, o programa dura 220 segundos. Uma tentativa de alimentar um arquivo de 1 Gb à noite (o tamanho do filme MPEG4 não é da melhor qualidade) não teve sucesso. Eu ainda estava lendo o programa pela manhã - e já tinha que ir trabalhar. Qual é o problema? Provavelmente em uso ArrayList<Integer>, que contém 1 bilhão de elementos. Cada elemento ocupa no mínimo 16 bytes (Cabeçalho: 8 bytes + Campo int: 4 bytes + Alinhamento para multiplicidade 8: 4 bytes). No total, colocamos voluntariamente 16 Gb de dados na memória com um tamanho de RAM de 8. Faremos melhor. Vamos nos aprofundar nas coleções. E viva, encontramos o que precisávamos.

Conheça o TreeSet

Isso é muito:

não permite armazenar dois elementos idênticos (o que significa que armazenaremos todos os 255 elementos na memória, em vez de um bilhão!)
ao manipular seus elementos, ele se organiza automaticamente (se classifica - aqui está, o cúmulo da perfeição!)

Nós temos:

// Вариант 2. Загоняем в ТreeSet который сам сортирует (лютый win!)
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());

        byte[] arrBytes = new byte[256];
        long startTime = System.currentTimeMillis();

        SortedSet<Integer> list = new TreeSet<Integer>();
        while(inputStream.available()>0) list.add(inputStream.read());
        inputStream.close();

        while (!list.isEmpty())        {
            System.out.print(list.last() + " ");
            list.remove(list.last());
        }

		long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

A saída é: arquivo de 46 MB, 176 segundos. Arquivo de 1 Gb - 3 horas e 5 minutos. O progresso é óbvio. Conseguimos “esperar” pelos resultados e o arquivo de 46 MB foi processado visivelmente mais rápido. Vá em frente. Vamos tentar desistir das coleções (isso será terrivelmente doloroso para alguns). Usaremos arrays simples (é tão primitivo). Vamos observar uma coisa importante . O número de bytes encontrados pode ser colocado em um array de comprimento 256. Portanto, simplesmente aumentaremos o elemento do array correspondente ao byte lido em um.

Matriz - byte por byte

// Вариант 3. Считываем массив поbyteно.
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());

        long[] arrBytes = new long[256];
        long startTime = System.currentTimeMillis();

        while (inputStream.available() > 0) arrBytes[inputStream.read()]++;

		inputStream.close();
        // Выводим отсортированный по byte-codeу в обратном порядке
        for (long i = 255; i >= 0 ; i--)
            if (arrBytes[(int) i] > 0) System.out.print(i + " ");

			long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

A saída é: arquivo de 46 MB, 158 segundos. Arquivo de 1 Gb - 2 horas e 55 minutos. Novamente uma melhoria, mas pequena. E fizemos tudo com ferramentas simples. Não usei microscópio para cravar pregos . Agora uma digressão lírica. Vamos lembrar a estrutura de um computador. A memória RAM (DRAM) , onde normalmente o programa é executado e as variáveis são armazenadas, possui alta velocidade de acesso, mas é pequena em tamanho. A memória em um disco rígido/flash (HDD ou Flash drives) onde normalmente são armazenados os arquivos, ao contrário, tem baixa velocidade de acesso, mas grande tamanho. Portanto, quando lemos um arquivo de 1 Gb byte por byte (ou seja, acessamos o HDD um bilhão de vezes), passamos muito tempo trabalhando com um dispositivo de baixa velocidade (transferimos areia grão por grão da carroceria de um caminhão KamAZ na caixa de areia). Vamos tentar melhorar ainda mais.

Vamos despejar TODO o caminhão KAMAZ com areia de uma vez!

// Вариант 4. Считываем массив сразу целиком за раз в память.
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());

        long[] arrBytes = new long[256];
        long startTime = System.currentTimeMillis();

        byte fileImage[]=new byte[inputStream.available()];
        long fileSize=fileImage.length;
        inputStream.read(fileImage);
        for (int i = 0; i = 0 ; i--)
            if (arrBytes[(int) i] > 0) System.out.print(i + " ");

		long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

uma pequena, mas novamente importante digressão . Nota:

O índice arrBytes é definido entre 0..255,
fileImage é uma matriz de bytes cujos elementos têm o valor -128..127

Portanto, para contar bytes, usaremos uma construção arrBytes[fileImage[i] & 0b11111111]++; que simplesmente redefinirá o bit de sinal e nos retornará um valor no intervalo 0..255 E assim, os resultados: arquivo de 46 MB 0,13 segundos (menos de um segundo). Arquivo de 1 Gb - 9 segundos. Conseguimos! Somos incrivelmente legais! Acelerado de 3 horas para 9 segundos. É isso, você pode sentar na cadeira e tomar um chá. E agora outra experiência - vamos tentar um arquivo de 32 Gb (por exemplo, um filme HD). Como resultado, obtemos um som crepitante do disco rígido em funcionamento com o programa travando no Windows. KamAZ despejou areia no corpo e quebrou a caixa de areia! O que nós fazemos? Vamos lembrar mais um fato. Os arquivos no sistema operacional geralmente são armazenados em porções (clusters) de 2 a 64 KB (dependendo do tipo de sistema de arquivos, configurações, etc.). Leremos em porções, por exemplo 64.000 bytes. Vamos tentar descarregar o KamAZ com uma escavadeira em porções bastante grandes:

Usando um buffer

// Вариант 5. Считываем массив кусками.
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());

        long[] arrBytes = new long[256];
        long startTime = System.currentTimeMillis();

        int  bufferSize = 64000;
        byte buffer[]   = new byte[64000];

        while (inputStream.available() > 0) {
            if (inputStream.available() < 64000) bufferSize = inputStream.available();
            inputStream.read(buffer, 0, bufferSize );
            for (int i = 0; i = 0 ; i--)
            if (arrBytes[(int) i] > 0) System.out.print(i + " ");

		long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

Como resultado, obtivemos: arquivo de 46 MB 0,08 segundos (menos de um segundo). Arquivo de 1 Gb - 0,9 segundos (menos de um segundo). Arquivo de 32 GB - 31 segundos. Observe que para um arquivo de 1 Gb melhoramos o desempenho de várias horas para frações de segundos !!! Com este modesto fato, finalizaremos o experimento e melhoraremos o código inicial. Fizemos progressos em muitos aspectos - estamos satisfeitos com os novos indicadores de consumo de memória e tempo de operação. Além disso, neste caso, não extraímos coleções inúteis da biblioteca padrão. PS Alguém dirá que o exemplo é rebuscado, etc. Mas existem muitas tarefas semelhantes - analisar um grande volume de elementos que possuem um número finito de estados. Por exemplo, imagens (RGB - geralmente armazenadas em 24 bytes, no nosso caso long[] arrRGB = new long[256*256*256] ocuparia apenas 64 MB de memória), música (a amplitude geralmente é digitalizada em 16 ou 24 bits ) ou sensores indicadores discretos, etc.