Trabajo byte a byte con archivos

Especial para

Empecemos

En el nivel 18, comenzaron las primeras tareas de lectura de archivos byte a byte: leer el archivo, luego encontrar los bytes mínimo/máximo o generarlo en forma ordenada, etc.

La gente aquí es muy inteligente. Saben de colecciones y que pueden ordenar e insertar. Las colecciones son un mecanismo poderoso. Y muchos no los usaban en absoluto antes de JavaRush. Por supuesto, es recomendable estudiarlos e intentar atacarlos en los lugares equivocados. Entonces. Cogemos un problema que no está en las tareas (para que no haya spoilers a la hora de solucionarlo), pero los hay muy parecidos:

Ingrese el nombre del archivo desde la consola
Leer todos los bytes de un archivo.
Haciendo caso omiso de las repeticiones, ordénelas por código de bytes en orden descendente.
Mostrar
Cerrar flujo de E/S

Ejemplo de bytes de un archivo de entrada 44 83 44 Ejemplo de salida 83 44 Además introdujimos variables startTimey finishTimepara registrar el tiempo de ejecución del programa. Para el cálculo utilicé i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64 (los ejemplos de programas en las opciones 1-2 están tomados del foro info.javarush, son ligeramente modificados solo para ordenar en orden ascendente, está bien, es decir, ¡¡son REALES!!)

Resolvámoslo 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.");
    }
}

¡Resuelve todo genial! La prueba (si la hubiera habido, la habría pasado con fuerza). Pero en la vida hay pocos archivos que contengan solo la línea "Mamá lavó el marco". Alimentemos nuestro programa con un archivo de 46 MB (según los estándares actuales, no parece mucho). ¿Qué es? El programa se ejecuta durante 220 segundos. Un intento de cargar un archivo de 1 Gb por la noche (el tamaño de la película MPEG4 no es de la mejor calidad) no tuvo éxito. Por la mañana todavía estaba leyendo el programa y ya tenía que ir a trabajar. ¿Cuál es el problema? Probablemente en uso ArrayList<Integer>que tiene mil millones de elementos en su interior. Cada elemento ocupa un mínimo de 16 bytes (Encabezado: 8 bytes + Campo int: 4 bytes + Alineación para multiplicidad 8: 4 bytes). En total, voluntariamente colocamos 16 Gb de datos en la memoria con un tamaño de RAM de 8. Lo haremos mejor. Profundicemos en las colecciones. Y hurra, encontramos lo que necesitábamos.

Conoce a TreeSet

Esto es mucho:

no permite almacenar dos elementos idénticos (lo que significa que almacenaremos los 255 elementos en la memoria, ¡en lugar de mil millones!)
al manipular sus elementos, automáticamente organiza (se ordena a sí mismo - ¡aquí está, el colmo de la perfección!)

Obtenemos:

// Вариант 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.");
    }
}

El resultado es: archivo de 46 MB, 176 segundos. Archivo de 1 Gb: 3 horas y 5 minutos. El progreso es obvio. Pudimos "esperar" los resultados y el archivo de 46 MB se procesa notablemente más rápido. Adelante. Intentemos renunciar a las colecciones (esto será insoportablemente doloroso para algunos). Usaremos matrices simples (es muy primitivo). Notemos una cosa importante . El número de bytes encontrados se puede poner en una matriz de longitud 256. Por lo tanto, simplemente aumentaremos en uno el elemento de la matriz correspondiente al byte leído.

Matriz: byte a 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-códigoу в обратном порядке
        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.");
    }
}

El resultado es: archivo de 46 MB, 158 segundos. Archivo de 1 Gb: 2 horas 55 minutos. De nuevo una mejora, pero pequeña. Y hicimos todo con herramientas simples. No usé un microscopio para clavar clavos . Ahora una digresión lírica. Recordemos la estructura de una computadora. La memoria RAM (DRAM) , donde normalmente se ejecuta el programa y se almacenan las variables, tiene una alta velocidad de acceso, pero es de pequeño tamaño. La memoria en un disco duro/flash (HDD o Flash drives) donde se suelen almacenar archivos, por el contrario, tiene una velocidad de acceso baja pero un tamaño grande. Entonces, cuando leemos un archivo de 1 Gb byte a byte (es decir, accedemos al disco duro mil millones de veces), pasamos mucho tiempo trabajando con un dispositivo de baja velocidad (transferimos arena grano a grano desde la carrocería de un camión KamAZ en la caja de arena). Intentemos mejorarlo aún más.

¡Tiremos TODO el camión KAMAZ con arena de una 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.");
    }
}

Una pequeña pero importante digresión .

El índice arrBytes se define entre 0..255,
fileImage es una matriz de bytes cuyos elementos tienen el valor -128..127

Por lo tanto, para contar bytes, usaremos una construcción arrBytes[fileImage[i] & 0b11111111]++; que simplemente restablecerá el bit de signo y nos devolverá un valor en el rango 0..255. Y así, los resultados: archivo de 46 MB en 0,13 segundos (menos de un segundo). Archivo de 1 Gb: 9 segundos. ¡Lo hicimos! ¡Somos increíblemente geniales! Acelerado de 3 horas a 9 segundos. Eso es todo, puedes recostarte en tu silla y tomar un poco de té. Y ahora otro experimento: probemos con un archivo de 32 Gb (por ejemplo, una película HD). Como resultado, obtenemos un sonido crepitante del disco duro en funcionamiento cuando el programa falla en Windows. ¡KamAZ arrojó el cuerpo con arena y rompió la caja de arena! qué hacemos? Recordemos un hecho más. Los archivos en el sistema operativo generalmente se almacenan en porciones (clústeres) de 2 a 64 KB (según el tipo de sistema de archivos, configuración, etc.). Leeremos en porciones, por ejemplo 64.000 bytes. Intentemos descargar KamAZ con una excavadora en porciones bastante grandes:

Usando un 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, obtuvimos: archivo de 46 MB en 0,08 segundos (menos de un segundo). Archivo de 1 Gb: 0,9 segundos (menos de un segundo). Archivo de 32 Gb: 31 segundos. Tenga en cuenta que para un archivo de 1 Gb hemos mejorado el rendimiento de varias horas a fracciones de segundos . Con este modesto dato finalizaremos el experimento y mejoraremos el código inicial. Hemos progresado en muchos aspectos: estamos satisfechos con los nuevos indicadores de consumo de memoria y tiempo de funcionamiento. Además, en este caso, no recuperamos colecciones inútiles de la biblioteca estándar. PD Alguien dirá que el ejemplo es descabellado, etc. Pero hay muchas tareas similares: analizar un gran volumen de elementos que tienen un número finito de estados. Por ejemplo, imágenes (RGB, generalmente almacenadas en 24 bytes, en nuestro caso long[] arrRGB = new long[256*256*256] ocuparía solo 64 MB en la memoria), música (la amplitud generalmente se digitaliza en 16 o 24 bits ) o sensores de indicadores discretos, etc.