生成磁盘文件用以位向量排序

起

第一章“开篇”围绕一个“如何给磁盘文件排序？”的问题展开。

具体描述是：
有一个磁盘文件，其最多包含n个正整数，每个整数一行，每个数都小于n，n=10^7，无重复整数出现。

而我们没有这样的一个文件，这意味着这章之后的一切实践都无法进行。这是阅读本书碰到的第一个必须解决的问题。

问题细化与思路

由于Java编码经验不足，大多数处理都要靠查文档，分析问题层面亦会比较注重Java语言本身。

我打算使用Java的一个list(称为s)结构通过循环for(0-10^7)来向s塞入相应的数字，此操作不会引入重复的整数。
使用随机去掉s中的20~50个元素（这里有两个随机数，一个是要去掉的元素的个数，另一个是要去掉元素的位置），最后通过选取随机下标将该元素pop出s并写入文件。

主要涉及到编码方面的以下几点：

1. 使用Java创建文件写入内容；
2. 选择一种合适list类，可以根据下标访问并pop元素；
3. 随机数生成器的使用方法；

代码

import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Random;

public class GenerateNumberFile {

    private final static int MAX_NUMBER = 10000000;

    public static void main(String[] args) throws IOException {
        // 生成1-10^7的int list.
        Random r = new Random();
        ArrayList<Integer> s = new ArrayList<>();
        for (int i = 0; i < MAX_NUMBER; i++) {
            s.add(i+1);
        }
        // System.out.println(s.size());
        int sLen = s.size();
        // 去掉20~50个元素.
        int removeCount = r.nextInt(30) + 20; // 生成20~49之间的一个整数；
        System.out.println("now we remove " + removeCount + " item");
        while (removeCount>0) {
            int removeIndex = r.nextInt(sLen);
            s.remove(removeIndex);
            removeCount--;
            sLen--;
        }
        PrintWriter writer = new PrintWriter("lot-number.txt", "UTF-8");
        while (sLen>0) {
            int removeIndex = r.nextInt(sLen);
            int removedItem = s.get(removeIndex);
            writer.println(removedItem);
            s.remove(removeIndex);
            sLen--;
            System.out.println(sLen);
        }
        writer.close();
    }
}

这里使用ArrayList来存储数字，其.get(index)与.remove(index)方法可以实现根据下标位置的取值与pop。
而Random类的实例r使用.nextInt()方法时接受一个参数k，可生成0至k-1之间的随机整数，比较难受的写法是要生成20~50间的随机整数竟然要int removeCount = r.nextInt(30) + 20;，不知有没有更直接一点的api啊。
最后写文件用到了PrintWriter类，其亦有println方法，让人想到了重定向，还蛮有意思的。

性能问题

该程序可以按需求生成lot-number.txt的磁盘文件。
可问题是，它太慢了，跑了2个小时左右才跑完。

ArrayList是数组结构而不是链表，虽然取值为O(1)，而remove元素，则需要将它之后的元素进行搬运，此为O(n)操作。
而若使用链表的话，则.get(index)为O(n)。
这里暂时难以两全。

同时，nextInt()方法好像也不够快。
那是否是生成随机数占用了大量的时间呢？这个易于测试：

public static void main(String[] args) {
        Random r = new Random();
        int j = 0;
        for (int i=0; i<10000000; i++) {
            System.out.println(i);
            r.nextInt(10000000-j);
            j++;
        }
    }

这段代码运行在40秒左右，虽然也不快（打印会占用不少时间），但这并不是将程序运行拖至两个小时的因素。

回头再来优化这个问题。