Побайтовая работа с файлами

Кратко

• Задача такая: посчитать, какие байты встречаются в файле, и вывести их коды по убыванию без повторов.
• ArrayList<Integer> на миллиард элементов не переживет ни один компьютер: каждое число превращается в объект и тянет за собой заголовок и ссылку.
• TreeSet снимает проблему памяти (в множестве не больше 256 элементов) и сортирует сам, но само чтение остается медленным.
• Обычный long[256] со счетчиками быстрее любой коллекции и не требует сортировки вовсе: индекс массива это и есть байт-код.
• Главный тормоз не в структуре данных, а в том, что байты читаются по одному: каждое обращение к диску стоит дорого.
• Чтение блоками по 64 000 байт ускоряет обработку гигабайтного файла с трех часов до долей секунды.

Начнем-с

• Ввести с консоли имя файла
• Считать все байты из файла.
• Не учитывая повторений - отсортировать их по байт-коду в убывающем порядке.
• Вывести на экран
• Закрыть поток ввода-вывода

Решаем в лоб:

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

Встречаем TreeSet

• не допускает хранение двух одинаковых элементов (а значит мы будем хранить в памяти все 255 элементов, вместо миллиарда!)
• при манипуляциях со своими элементами автоматом упорядочивает (само сортирует - вот он, верх совершенства!)

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

Массив: побайтно

// Вариант 3. Считываем массив побайтно.
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();
        // Выводим отсортированный по байт-коду в обратном порядке
        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.");
    }
}

Вывалим сразу ВЕСЬ КамАЗ с песком за один раз!

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

1. индекс у arrBytes определен в пределах 0..255,
2. fileImage - массив байт, элементы которого имеют значение -128..127

Используем буфер

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

Сравним все пять вариантов

Что здесь не так с точки зрения продакшена

int count;
while ((count = inputStream.read(buffer)) != -1) {
    for (int i = 0; i < count; i++) arrBytes[buffer[i] & 0b11111111]++;
}

Как это пишут сегодня

public class Solution {
    public static void main(String[] args) throws Exception {
        Path path = Paths.get(new BufferedReader(new InputStreamReader(System.in)).readLine());
        long[] arrBytes = new long[256];

        try (InputStream in = new BufferedInputStream(Files.newInputStream(path))) {
            byte[] buffer = new byte[64000];
            int count;
            while ((count = in.read(buffer)) != -1) {
                for (int i = 0; i < count; i++) arrBytes[buffer[i] & 0b11111111]++;
            }
        }

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

Вопросы и ответы

Почему побайтное чтение файла работает так медленно?

Зачем в коде побитовая маска 0b11111111?

Можно ли просто прочитать файл целиком в массив?

Какой размер буфера выбрать?

Можно ли обойтись без ручного буфера?

Почему ArrayList из Integer занимает так много памяти?

Читайте также

• Классы FileInputStream, FileOutputStream, BufferedInputStream в Java
• BufferedReader и InputStreamReader: считывание с клавиатуры
• Java.io: операции ввода-вывода в Java
• TreeSet в Java