Special for
Народ тут дуже вульгарний. Знають про колекції та про те, що вони можуть сортувати, вставляти. Колекції – потужний механізм. І багато хто не застосовував їх взагалі до JavaRush-а. Воно, звичайно, схвально вивчати їх і намагатися приткнути куди не потрапивши. І так. Візьмемо завдання, якого немає в завданнях (щоб не було спойлерів при вирішенні), але є дуже схожі:
Почнемо'c
У 18 рівні розпочалися перші завдання побайтного читання файлів: прочитати файл, далі знайти мінімальні/максимальні байти або вивести упорядкованому вигляді тощо.- Ввести з консолі ім'я файлу
- Вважати всі байти з файлу.
- Не враховуючи повторень - відсортувати їх за байт-кодом у спадному порядку.
- Вивести на екран
- Закрити потік введення-виводу
startTime
і
finishTime
щоб засікти час виконання програми. Для обчислення використовував
i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64 (приклади програм у варіантах 1-2 взяті з форуму порядку - тобто вони РЕАЛЬНІ!!)
Вирішуємо в лоб:
// Вариант 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 файлу ми покращабо продуктивність з кількох
годин до
часток секунд!!! На цьому скромному факті закінчимо експеримент та покращення початкового коду. Ми досягли прогресу багато в чому – нас тішать нові показники витрати пам'яті та часу роботи. Також ми не підтягуємо в цьому випадку непотрібні колекції зі стандартної бібліотеки. PS Хтось скаже приклад надуманий тощо. Але схожих завдань — проаналізувати величезний обсяг елементів, що мають кінцеву кількість станів. Наприклад зображення (RGB - зазвичай зберігаються у 24 байтах, у разі long[] arrRGB = new long[256*256*256] зайняв би у пам'яті всього 64Мб), музика (амплітуда зазвичай оцифровується в 16 чи 24 біта) чи дискретні показники датчиків тощо.