Special for
Начнем'c
В 18 уровне начались первые задачи поbyteного чтения файлов: прочитать файл, далее найти минимальные/максимальные byteы or вывести в упорядоченном виде и т.п.
Народ тут весьма ушлый. Знают про коллекции и про то, что они могут сортировать, вставлять. Коллекции — мощный механизм. И многие не применяли их вообще до JavaRush-а. Оно, конечно, похвально изучать их и пытаться приткнуть куда не попадя. И так. Возьмем задачу, которой нет в заданиях (чтобы не было спойлеров при решении), но есть сильно похожие:
- Ввести с консоли file name
- Считать все byteы из file.
- Не учитывая повторений - отсортировать их по byte-codeу в убывающем порядке.
- Вывести на экран
- Закрыть поток ввода-вывода
Пример byte входного file
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 , они чуть модифицированы только для сортировки в возрастающем порядке - то есть они РЕАЛЬНЫЕ!!)
Решаем в лоб:
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Мб (по нынешним меркам вроде и не особо много). What такое, программа выполняется 220 секунд. Попытка скормить с вечера 1Gb файл (размер MPEG4 фильма не в самом лучшем качестве) не увенчалась успехом. Программа утром все еще читала - а мне идти на работу уже. В чем проблема? Наверное в использовании
ArrayList<Integer>
у которого внутри 1 миллиард элементов. Каждый элемент его занимает 16 byte минимум (Заголовок: 8 byte + Поле int: 4 byteа + Выравнивание для кратности 8: 4 byteа). Total мы добровольно загоняем в память 16 Gb данных при размере оперативы в 8. Будем делать лучше. Нырнем в коллекции глубже. И ура, нашлось то, что нам нужно.
Встречаем TreeSet
Это множество:
- не допускает хранение двух одинаковых элементов (а значит мы будем хранить в памяти все 255 элементов, instead of миллиарда!)
- при манипуляциях со своими elementми автоматом упорядочивает (само сортирует - вот он, верх совершенства!)
Получаем:
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 minutes. Прогресс на лицо. Мы смогли "дождаться" результатов, да и 46Мб файл заметно быстрее обрабатывается. Идем дальше. Давайте попытаемся
отказаться от коллекций (это будет для некоторых мучительно больно). Будем использовать простые массивы (это так примитивно). Заметим одну
важную вещь. Кол-во встречающихся byte можно загнать в массив длиной 256. Так просто будем увеличивать на единицу соответствующий считанному byteу элемент массива.
Массив — по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();
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 minutes. Опять улучшение, но небольшое. И мы сделали все простыми инструментами.
Не использовали микроскоп для забивания гвоздей.
Теперь лирическое отступление. Вспомним устройство компьютера.
Память ОЗУ (DRAM) где обычно выполняется программа и хранятся переменные имеет высокую speed доступа, но небольшой размер.
Память на жестком/flash диске (HDD or Flash-накопители) где обычно хранятся файлы, наоборот имеет низкую speed доступа, но большой размер. Так что когда мы поbyteно читаем 1Gb файл (то есть миллиард раз обращаемся к HDD) - мы тратим много времени на работу с низкоскоростным устройством (по песчинке перекладываем песок с кузова КамАЗа в песочницу). Попробуем еще улучшить.
Вывалим сразу ВЕСЬ КамАЗ с песком за один раз!
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 - массив byte, элементы которого имеют meaning -128..127
Поэтому для подсчета byte будем использовать конструкцию
arrBytes[fileImage[i] & 0b11111111]++;
которая банально сбросит бит знака и вернет нам meaning в диапазоне 0..255
И так, результаты: 46Мб файл 0.13 секунд (меньше секунды). 1Gb файл - 9 секунд. Мы сделали это! Мы невероятно круты! Ускорorсь с 3 часов до 9 секунд. Все, можно откинуться в кресле и попить чайку. А теперь еще один эксперимент - попробуем файл в 32 Gb (например, HD фильм). Получим в результате треск работающего HDD с вываливанием программы в Windows. КамАЗ вывалив кузов с песком сломал песочницу! What будем делать? Вспомним еще один факт. Файлы в ОС хранятся обычно порциями (кластерами) по 2-64Кб (зависит от типа файловой системы, настроек и т.п.). Будем считывать порциями, для примера в 64000 byte. Попытаемся разгрузить КамАЗ экскаватором достаточно большими порциями:
We use буфер
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.");
}
}
В итоге получor: 46Мб файл 0.08 секунд (меньше секунды). 1Gb файл - 0.9 секунд(меньше секунды). 32Gb файл - 31 секунда. Заметим для 1 Gb file мы улучшor производительность с нескольких
часов до
долей секунд!!! На этом скромном факте закончим эксперимент и улучшение начального codeа. Мы достигли прогресса во многом - нас радуют новые показатели расхода памяти и времени работы. Также мы не подтягиваем в данном случае бесполезные коллекции из стандартной библиотеки. P.S. Кто-то скажет пример надуманный и т.п. Но полно похожих задач — проанализировать огромный объем элементов, имеющих конечное число состояний. Например изображения (RGB - обычно хранятся в 24 byteах, в нашем случае long[] arrRGB = new long[256*256*256] занял бы в памяти всего 64Мб), музыка (амплитуда обычно оцифровывается в 16 or 24 бита) or дискретные показатели датчиков и т.п.
GO TO FULL VERSION