Special for

Начнем'c

В 18 уровне начались первые задачи побайтного чтения файлов: прочитать файл, далее найти минимальные/максимальные байты или вывести в упорядоченном виде и т.п.
Побайтовая работа с файлами - 1
Народ тут весьма ушлый. Знают про коллекции и про то, что они могут сортировать, вставлять. Коллекции — мощный механизм. И многие не применяли их вообще до JavaRush-а. Оно, конечно, похвально изучать их и пытаться приткнуть куда не попадя. И так. Возьмем задачу, которой нет в заданиях (чтобы не было спойлеров при решении), но есть сильно похожие:
  • Ввести с консоли имя файла
  • Считать все байты из файла.
  • Не учитывая повторений - отсортировать их по байт-коду в убывающем порядке.
  • Вывести на экран
  • Закрыть поток ввода-вывода
Пример байт входного файла 44 83 44 Пример вывода 83 44 Мы дополнительно завели переменные startTime и finishTime — чтобы засечь время выполнения программы. Для вычисления использовал i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64 (примеры программ в вариантах 1-2 взяты из форума info.javarush , они чуть модифицированы только для сортировки в возрастающем порядке - то есть они РЕАЛЬНЫЕ!!)

Решаем в лоб:


// Вариант 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.");
    }
}
Frontend-университет
Решает все замечательно! Тест (если бы был — прошелся бы на ура). Но в жизни мало файлов содержащих только строчку "Мама мыла раму". Давайте скормим нашей программе файл в 46Мб (по нынешним меркам вроде и не особо много). Что такое, программа выполняется 220 секунд. Попытка скормить с вечера 1Gb файл (размер MPEG4 фильма не в самом лучшем качестве) не увенчалась успехом. Программа утром все еще читала - а мне идти на работу уже. В чем проблема? Наверное в использовании ArrayList<Integer> у которого внутри 1 миллиард элементов. Каждый элемент его занимает 16 байт минимум (Заголовок: 8 байт + Поле int: 4 байта + Выравнивание для кратности 8: 4 байта). Итого мы добровольно загоняем в память 16 Gb данных при размере оперативы в 8. Будем делать лучше. Нырнем в коллекции глубже. И ура, нашлось то, что нам нужно.

Встречаем 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.");
    }
}
Имеем на выходе: 46Мб файл 176 секунд. 1Gb файл - 3 часа 5 минут. Прогресс на лицо. Мы смогли "дождаться" результатов, да и 46Мб файл заметно быстрее обрабатывается. Идем дальше. Давайте попытаемся отказаться от коллекций (это будет для некоторых мучительно больно). Будем использовать простые массивы (это так примитивно). Заметим одну важную вещь. Кол-во встречающихся байт можно загнать в массив длиной 256. Так просто будем увеличивать на единицу соответствующий считанному байту элемент массива.

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


// Вариант 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.");
    }
}
Имеем на выходе: 46Мб файл 158 секунд. 1Gb файл - 2 часа 55 минут. Опять улучшение, но небольшое. И мы сделали все простыми инструментами. Не использовали микроскоп для забивания гвоздей. Теперь лирическое отступление. Вспомним устройство компьютера. Память ОЗУ (DRAM) где обычно выполняется программа и хранятся переменные имеет высокую скорость доступа, но небольшой размер. Память на жестком/flash диске (HDD или Flash-накопители) где обычно хранятся файлы, наоборот имеет низкую скорость доступа, но большой размер. Так что когда мы побайтно читаем 1Gb файл (то есть миллиард раз обращаемся к HDD) - мы тратим много времени на работу с низкоскоростным устройством (по песчинке перекладываем песок с кузова КамАЗа в песочницу). Попробуем еще улучшить.

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


// Вариант 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
Поэтому для подсчета байт будем использовать конструкцию arrBytes[fileImage[i] & 0b11111111]++; которая банально сбросит бит знака и вернет нам значение в диапазоне 0..255 И так, результаты: 46Мб файл 0.13 секунд (меньше секунды). 1Gb файл - 9 секунд. Мы сделали это! Мы невероятно круты! Ускорились с 3 часов до 9 секунд. Все, можно откинуться в кресле и попить чайку. А теперь еще один эксперимент - попробуем файл в 32 Gb (например, HD фильм). Получим в результате треск работающего HDD с вываливанием программы в Windows. КамАЗ вывалив кузов с песком сломал песочницу! Что будем делать? Вспомним еще один факт. Файлы в ОС хранятся обычно порциями (кластерами) по 2-64Кб (зависит от типа файловой системы, настроек и т.п.). Будем считывать порциями, для примера в 64000 байт. Попытаемся разгрузить КамАЗ экскаватором достаточно большими порциями:
Java-университет

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


// Вариант 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.");
    }
}
В итоге получили: 46Мб файл 0.08 секунд (меньше секунды). 1Gb файл - 0.9 секунд(меньше секунды). 32Gb файл - 31 секунда. Заметим для 1 Gb файла мы улучшили производительность с нескольких часов до долей секунд!!! На этом скромном факте закончим эксперимент и улучшение начального кода. Мы достигли прогресса во многом - нас радуют новые показатели расхода памяти и времени работы. Также мы не подтягиваем в данном случае бесполезные коллекции из стандартной библиотеки. P.S. Кто-то скажет пример надуманный и т.п. Но полно похожих задач — проанализировать огромный объем элементов, имеющих конечное число состояний. Например изображения (RGB - обычно хранятся в 24 байтах, в нашем случае long[] arrRGB = new long[256*256*256] занял бы в памяти всего 64Мб), музыка (амплитуда обычно оцифровывается в 16 или 24 бита) или дискретные показатели датчиков и т.п.