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