Fayllarla bayt-bayt iş

üçün xüsusi

Gəlin başlayaq

18-ci səviyyədə faylın bayt-bayt oxunmasının ilk tapşırıqları başladı: faylı oxuyun, sonra minimum/maksimum baytları tapın və ya onu sifarişli formada çıxarın və s.

Buradakı insanlar çox ağıllıdırlar. Onlar kolleksiyalar haqqında bilirlər və çeşidləyib daxil edə bilirlər. Kolleksiyalar güclü mexanizmdir. Çoxları JavaRush-dan əvvəl onlardan ümumiyyətlə istifadə etmirdilər. Onları öyrənmək və yanlış yerlərə vurmağa çalışmaq təbii ki, təqdirəlayiqdir. Belə ki. Tapşırıqlarda olmayan bir problemi götürək (həll edərkən heç bir spoyler olmasın), lakin çox oxşar olanlar var:

Konsoldan fayl adını daxil edin
Fayldan bütün baytları oxuyun.
Təkrarlara məhəl qoymayaraq, onları bayt koduna görə azalan ardıcıllıqla sıralayın.
Ekran
I/O axını bağlayın

Giriş faylının bayt nümunəsi 44 83 44 Çıxış nümunəsi 83 44 Biz əlavə olaraq dəyişənləri təqdim etdik startTimevə finishTimeproqramın icra müddətini qeyd etdik. Hesablama üçün mən i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64-dən istifadə etdim (1-2-ci variantda olan proqramların nümunələri info.javarush forumundan götürülüb, onlar bir qədər azdır. yalnız artan qaydada çeşidləmək üçün dəyişdirilib, tamam - yəni onlar REALdır!!)

Gəlin bunu baş-başa həll edək:

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

Hər şeyi əla həll edir! Test (əgər olsaydı, bir bang ilə keçərdi). Ancaq həyatda yalnız "Anam çərçivəni yudu" sətirindən ibarət bir neçə fayl var. Gəlin proqramımızı 46 MB-lıq bir fayl ilə qidalandıraq (bugünkü standartlara görə bu, çox görünmür). Bu nədir, proqram 220 saniyə işləyir. Axşam saatlarında 1Gb faylı qidalandırmaq cəhdi (MPEG4 filminin ölçüsü ən yaxşı keyfiyyətdə deyil) uğursuz oldu. Mən hələ səhər proqramı oxuyurdum - və artıq işə getməli idim. Problem nədir? ArrayList<Integer>Ehtimal ki , içərisində 1 milyard elementi olan istifadədədir . Onun hər bir elementi minimum 16 bayt tutur (Başlıq: 8 bayt + Sahə int: 4 bayt + Çoxluq üçün uyğunlaşdırma 8: 4 bayt). Ümumilikdə biz könüllü olaraq 8 RAM ölçüsü ilə 16 Gb məlumatı yaddaşa qoyuruq. Daha yaxşısını edəcəyik. Gəlin kolleksiyalara daha dərindən girək. Və hurray, biz lazım olanı tapdıq.

TreeSet ilə tanış olun

Bu çox şeydir:

iki eyni elementi saxlamağa imkan vermir (bu o deməkdir ki, biz milyard əvəzinə bütün 255 elementi yaddaşda saxlayacağıq!)
elementlərini manipulyasiya edərkən avtomatik olaraq təşkil edir (özünü çeşidləyir - budur, mükəmməllik zirvəsi!)

Biz əldə edirik:

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

Çıxış: 46 MB fayl, 176 saniyə. 1Gb fayl - 3 saat 5 dəqiqə. Tərəqqi göz qabağındadır. Nəticələri "gözləyə" bildik və 46MB fayl nəzərəçarpacaq dərəcədə sürətlə emal olunur. Davam et. Gəlin kolleksiyalardan imtina etməyə çalışaq (bəziləri üçün bu, dözülməz dərəcədə ağrılı olacaq). Biz sadə massivlərdən istifadə edəcəyik (bu, çox primitivdir). Bir vacib şeyi qeyd edək . Qarşılaşılan baytların sayı 256 uzunluqlu massivdə yerləşdirilə bilər. Beləliklə, biz sadəcə oxunan bayta uyğun massiv elementini bir artıracağıq.

Massiv - bayt bayt

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

Çıxış: 46MB fayl, 158 saniyə. 1Gb fayl - 2 saat 55 dəqiqə. Yenə təkmilləşdirmə, lakin kiçik. Və biz hər şeyi sadə alətlərlə etdik. Dırnaq sürmək üçün mikroskopdan istifadə etmədi . İndi lirik bir təxribat. Kompüterin quruluşunu xatırlayaq. Proqramın adətən icra edildiyi və dəyişənlərin saxlandığı RAM yaddaşı (DRAM) yüksək giriş sürətinə malikdir, lakin ölçüsü kiçikdir. Faylların adətən saxlandığı sərt/flash diskdə (HDD və ya Flash disklər) yaddaş, əksinə, aşağı giriş sürətinə malikdir, lakin böyük ölçüyə malikdir. Beləliklə, 1Gb faylı bayt-bayt oxuduqda (yəni HDD-yə milyard dəfə daxil oluruq), biz aşağı sürətli bir cihazla işləmək üçün çox vaxt sərf edirik (biz KamAZ yük maşınının gövdəsindən qum taxılını taxılla köçürürük) qum qutusuna). Gəlin onu daha da təkmilləşdirməyə çalışaq.

Gəlin BÜTÜN KAMAZ-ı bir anda qumla boşaldaq!

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

kiçik, lakin yenə də vacib bir sapma.Qeyd :

arrBytes indeksi 0..255 daxilində müəyyən edilir,
fileImage elementləri -128..127 dəyərinə malik bayt massivdir

arrBytes[fileImage[i] & 0b11111111]++; Buna görə baytları saymaq üçün sadəcə işarə bitini sıfırlayacaq və bizə 0..255 diapazonunda bir dəyər qaytaracaq konstruksiyadan istifadə edəcəyik. Beləliklə, nəticələr: 46MB fayl 0.13 saniyə (bir saniyədən az). 1Gb fayl - 9 saniyə. Biz bunu etdik! Biz inanılmaz dərəcədə sərinik! 3 saatdan 9 saniyəyə qədər sürətləndirildi. Budur, kresloda oturub çay içə bilərsiniz. İndi başqa bir təcrübə - 32 Gb faylı (məsələn, HD film) sınayaq. Nəticədə, proqramın Windows-da çökməsi ilə işləyən HDD-dən xırıltılı bir səs alırıq. KamAZ cəsədi qumla tökdü və qum qutusunu sındırdı! Biz nə edirik? Bir faktı daha xatırlayaq. ƏS-də fayllar adətən 2-64Kb (fayl sisteminin növündən, parametrlərindən və s. asılı olaraq) hissələrdə (klasterlərdə) saxlanılır. Biz hissə-hissə oxuyacağıq, məsələn, 64.000 bayt. KamAZ-ı ekskavatorla kifayət qədər böyük hissələrdə boşaltmağa çalışaq:

Buferdən istifadə

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

Nəticədə, əldə etdik: 46 MB fayl 0,08 saniyə (bir saniyədən az). 1Gb fayl - 0,9 saniyə (bir saniyədən az). 32 Gb fayl - 31 saniyə. Qeyd edək ki, 1 Gb fayl üçün performansı bir neçə saatdan saniyələrin fraksiyalarına qədər artırdıq !!! Bu təvazökar faktla biz təcrübəni bitirəcəyik və ilkin kodu təkmilləşdirəcəyik. Biz bir çox cəhətdən irəliləyiş əldə etdik - yaddaş istehlakının və işləmə müddətinin yeni göstəriciləri bizi qane edir. Həmçinin, bu halda biz standart kitabxanadan lazımsız kolleksiyaları götürmürük. P.S. Biri deyəcək ki, misal çox uzaqdır və s. Ancaq bir çox oxşar vəzifələr var - sonlu sayda vəziyyətə malik olan çox sayda elementi təhlil etmək. Məsələn, şəkillər (RGB - adətən 24 baytda saxlanılır, bizim vəziyyətimizdə long[] arrRGB = new long[256*256*256] yaddaşda yalnız 64MB yer tutur), musiqi (amplituda adətən 16 və ya 24 bitdə rəqəmsallaşdırılır. ) və ya diskret göstəricilər sensorlar və s.