逐位元組處理文件

在 Random-TW 群組發布

特別適合

讓我們開始吧

在第18級，開始了逐位元組文件讀取的第一個任務：讀取文件，然後找到最小/最大位元組或以有序形式輸出等。

這裡的人非常聰明。他們了解集合並且可以排序和插入。集合是一個強大的機制。許多人在 JavaRush 之前根本沒有使用過它們。當然，研究它們並嘗試在錯誤的地方打擊它們是值得讚揚的。所以。我們來舉一個任務中沒有的問題（這樣解決的時候就不劇透了），但是也有非常相似的問題：

從控制台輸入檔名
從檔案中讀取所有位元組。
忽略重複，依字節碼降序排序。
展示
關閉I/O流

輸入檔的位元組範例 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.");
    }
}

解決一切都很棒！測試（如果有的話，它會轟然通過）。但人生很少文件只包含「媽媽洗了鏡框」這句話。讓我們為我們的程序提供一個 46MB 的文件（按照今天的標準，這似乎並不多）。這是什麼，程式運行了 220 秒。嘗試在晚上傳輸 1Gb 檔案（MPEG4 電影的大小不是最好的品質）沒有成功。早上我還在看節目——而且我已經要去上班了。問題是什麼？可能正在使用 ArrayList<Integer>，裡面有10億個元素。它的每個元素至少佔用 16 個位元組（標頭：8 個位元組 + Field int：4 個位元組 + 多重性對齊 8：4 個位元組）。總共，我們自願將 16 GB 的資料放入 RAM 大小為 8 的記憶體中。我們會做得更好。讓我們更深入地了解這些集合。萬歲，我們找到了我們需要的東西。

認識樹集

這是很多：

不允許儲存兩個相同的元素（這意味著我們將在記憶體中儲存所有 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.");
    }
}

輸出為： 46MB 文件，176 秒。1Gb 檔案 - 3 小時 5 分鐘。 進步是顯而易見的。我們能夠「等待」結果，並且 46MB 檔案的處理速度明顯更快。前進。讓我們嘗試放棄收藏（這對某些人來說將是極其痛苦的）。我們將使用簡單的陣列（它太原始了）。讓我們注意一件 重要的事情。遇到的位元組數可以放入長度為256的陣列中。因此我們只需將讀取的位元組對應的陣列元素加一即可。

數組 - 逐字節

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

輸出為： 46MB 文件，158 秒。1Gb 檔案 - 2 小時 55 分鐘。 又是一個進步，但幅度很小。我們用簡單的工具完成了一切。 沒有使用顯微鏡來釘釘子。 現在是抒情的題外話。 讓我們記住計算機的結構。 RAM記憶體(DRAM)通常是執行程式和儲存變數的地方，存取速度高，但尺寸小。相反，通常儲存檔案的 硬碟/快閃磁碟機（HDD 或快閃磁碟機）上的記憶體具有較低的存取速度但尺寸較大。因此，當我們逐字節讀取 1Gb 檔案（即訪問 HDD 十億次）時，我們會花費大量時間使用低速設備（我們從 KamAZ 卡車車身上一粒一粒地傳輸沙子）進入沙箱）。讓我們嘗試進一步改進它。

讓我們立即將整輛卡瑪斯卡車與沙子一起倒掉！

// Вариант 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 範圍內的值，因此，結果： 46MB 檔案 0.13 秒（不到一秒）。1Gb 檔案 - 9 秒。 我們做到了！我們太酷了！從3小時加速到9秒。就這樣，你可以坐在椅子上喝點茶了。現在進行另一個實驗 - 讓我們嘗試 32 GB 檔案（例如，高清電影）。結果，我們在 Windows 中聽到工作硬碟發出劈啪聲，程式崩潰。卡瑪茲用沙子傾倒屍體，打破了沙箱！我們做什麼？讓我們再記住一個事實。作業系統中的檔案通常儲存在2-64Kb的部分（簇）中（取決於檔案系統的類型、設定等）。我們將分部分讀取，例如 64,000 位元組。讓我們嘗試用挖土機卸載相當大的部分 KamAZ：

使用緩衝區

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

結果，我們得到： 46MB檔案0.08秒（不到一秒）。1Gb 檔案 - 0.9 秒（不到一秒）。32Gb 檔案 - 31 秒。 請注意，對於 1 Gb 文件，我們將性能從幾個小時提高到了幾分之一秒！有了這個不起眼的事實，我們將完成實驗並改進初始程式碼。我們在很多方面都取得了進展——我們對記憶體消耗和運行時間的新指標感到滿意。此外，在這種情況下，我們不會從標準庫中提取無用的集合。PS 有人會說這個例子牽強等等。但還有很多類似的任務——分析具有有限狀態的大量元素。例如，影像（RGB - 通常儲存在 24 位元組中，在我們的例子中 long[] arrRGB = new long[256*256*256] 將只佔用 64MB 記憶體）、音樂（振幅通常以 16 或 24 位元數位化）或離散指示器感測器等。