逐字节处理文件

已在 Random-ZH 群组中发布

特别适合

让我们开始吧

在第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 位数字化）或离散指示器传感器等。