Bajt po bajcie praca z plikami

Specjalnie dla

Zacznijmy

Na poziomie 18 rozpoczęły się pierwsze zadania odczytu pliku bajt po bajcie: przeczytaj plik, następnie znajdź minimalną/maksymalną liczbę bajtów lub wyprowadź go w uporządkowanej formie itp.

Ludzie tutaj są bardzo mądrzy. Wiedzą o kolekcjach oraz o tym, że potrafią sortować i wstawiać. Kolekcje to potężny mechanizm. Wielu w ogóle ich nie używało przed JavaRush. Oczywiście godne pochwały jest ich przestudiowanie i próba trafienia w niewłaściwe miejsca. Więc. Weźmy problem, którego nie ma w zadaniach (aby nie było spoilerów przy jego rozwiązywaniu), ale są bardzo podobne:

Wprowadź nazwę pliku z konsoli
Odczytaj wszystkie bajty z pliku.
Ignorując powtórzenia, posortuj je według kodu bajtowego w kolejności malejącej.
Wyświetlacz
Zamknij strumień we/wy

Przykładowe bajty pliku wejściowego 44 83 44 Przykładowe wyjście 83 44 Dodatkowo wprowadziliśmy zmienne startTimeoraz finishTimezapis czasu wykonania programu. Do obliczeń użyłem i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64 (przykłady programów w opcjach 1-2 pochodzą z forum info.javarush, są one nieco zmodyfikowane tylko do sortowania w porządku rosnącym, ok - to znaczy, że są PRAWDZIWE!!)

Rozwiążmy to od razu:

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

Rozwiązuje wszystko świetnie! Test (gdyby był, przeszedłby z hukiem). Ale w życiu jest niewiele plików zawierających tylko wiersz „Mama umyła ramę”. Zasilmy nasz program plikiem o wielkości 46 MB (według dzisiejszych standardów nie wydaje się to dużo). Co to jest, program działa przez 220 sekund. Próba przesłania wieczorem pliku 1 Gb (rozmiar filmu MPEG4 nie jest najlepszej jakości) nie powiodła się. Nadal czytałem poranny program - a już musiałem iść do pracy. Jaki jest problem? Prawdopodobnie w użyciu ArrayList<Integer>, który ma w środku 1 miliard elementów. Każdy jego element zajmuje minimum 16 bajtów (nagłówek: 8 bajtów + pole int: 4 bajty + wyrównanie dla krotności 8: 4 bajty). W sumie dobrowolnie umieściliśmy w pamięci 16 Gb danych przy rozmiarze RAM 8. Zrobimy to lepiej. Zagłębmy się w kolekcje. I hurra, znaleźliśmy to, czego potrzebowaliśmy.

Poznaj TreeSet

To dużo:

nie pozwala na przechowywanie dwóch identycznych elementów (co oznacza, że w pamięci będziemy przechowywać wszystkie 255 elementów, zamiast miliarda!)
manipulując swoimi elementami, automatycznie organizuje (sam się sortuje – oto szczyt doskonałości!)

Otrzymujemy:

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

Wynik to: plik 46MB, 176 sekund. Plik 1 GB - 3 godziny 5 minut. Postęp jest oczywisty. Udało nam się „poczekać” na rezultaty i plik ważący 46MB jest przetwarzany zauważalnie szybciej. Zacząć robić. Spróbujmy zrezygnować ze zbiórek (dla niektórych będzie to potwornie bolesne). Będziemy używać prostych tablic (to takie prymitywne). Zwróćmy uwagę na jedną ważną rzecz . Liczbę napotkanych bajtów można umieścić w tablicy o długości 256. Zatem po prostu zwiększymy o jeden element tablicy odpowiadający odczytanemu bajtowi.

Tablica - bajt po bajcie

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

Dane wyjściowe to: plik 46 MB, 158 sekund. Plik 1 GB - 2 godziny 55 minut. Znów poprawa, ale niewielka. A wszystko zrobiliśmy za pomocą prostych narzędzi. Nie używałem mikroskopu do wbijania gwoździ . A teraz dygresja liryczna. Przypomnijmy sobie budowę komputera. Pamięć RAM (DRAM) , w której zwykle wykonywany jest program i przechowywane są zmienne, ma dużą szybkość dostępu, ale jest niewielka. Wręcz przeciwnie , pamięć na dysku twardym/flash (dysku twardym lub dysku flash), na którym zwykle przechowywane są pliki, ma niską prędkość dostępu, ale duży rozmiar. Kiedy więc czytamy bajt po bajcie plik o wielkości 1 Gb (czyli uzyskujemy dostęp do dysku twardego miliard razy), spędzamy dużo czasu pracując z urządzeniem o niskiej prędkości (przenosimy ziarno piasku po ziarnku z nadwozia ciężarówki KamAZ do piaskownicy). Spróbujmy to jeszcze ulepszyć.

Wysypmy od razu CAŁĄ ciężarówkę KAMAZ z piaskiem!

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

mała, ale znowu ważna dygresja . Uwaga:

Indeks arrBytes jest zdefiniowany w zakresie 0..255,
fileImage to tablica bajtowa, której elementy mają wartość -128..127

Dlatego do liczenia bajtów zastosujemy konstrukcję arrBytes[fileImage[i] & 0b11111111]++; , która po prostu zresetuje bit znaku i zwróci nam wartość z zakresu 0..255 I tak wyniki: plik 46MB 0,13 sekundy (mniej niż sekunda). Plik 1 GB - 9 sekund. Zrobiliśmy to! Jesteśmy niesamowicie fajni! Przyspieszono z 3 godzin do 9 sekund. To wszystko, możesz usiąść wygodnie w fotelu i napić się herbaty. A teraz kolejny eksperyment - spróbujmy z plikiem 32 Gb (na przykład filmem HD). W rezultacie otrzymujemy trzaskający dźwięk z pracującego dysku twardego przy zawieszaniu się programu w systemie Windows. KamAZ wyrzucił ciało piaskiem i rozbił piaskownicę! Co robimy? Przypomnijmy jeszcze jeden fakt. Pliki w systemie operacyjnym są zwykle przechowywane w porcjach (klasterach) o wielkości od 2 do 64 KB (w zależności od typu systemu plików, ustawień itp.). Będziemy czytać porcjami, na przykład 64 000 bajtów. Spróbujmy rozładować KamAZ koparką w dość dużych porcjach:

Korzystanie z bufora

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

W efekcie otrzymaliśmy: plik 46MB w czasie 0,08 sekundy (mniej niż sekunda). Plik 1 GB - 0,9 sekundy (mniej niż sekunda). Plik 32 GB - 31 sekund. Uwaga, dla pliku 1 Gb poprawiliśmy wydajność z kilku godzin do ułamków sekund !!! Tym skromnym faktem zakończymy eksperyment i ulepszymy początkowy kod. Poczyniliśmy postępy pod wieloma względami – jesteśmy zadowoleni z nowych wskaźników zużycia pamięci i czasu działania. Również w tym przypadku nie pobieramy bezużytecznych zbiorów ze standardowej biblioteki. PS Ktoś powie, że przykład jest naciągany itp. Ale istnieje wiele podobnych zadań - analizowanie ogromnej liczby elementów o skończonej liczbie stanów. Na przykład obrazy (RGB - zwykle przechowywane w 24 bajtach, w naszym przypadku long[] arrRGB = new long[256*256*256] zajmowałyby tylko 64MB w pamięci), muzyka (amplituda jest zwykle digitalizowana w 16 lub 24 bitach ) lub dyskretne czujniki wskaźników itp.