生成包含随机数磁盘文件优化

之前写了生成磁盘文件用以位向量排序。
思路很清晰简单，程序正确无误。
但问题是它不够好用，太慢了，要跑两个小时。
这和去面试时我的处理很像，看到问题，先给出一个简单直接暴力而不考虑性能的算法尝试解决。之后面试官会开始要求更好的解法，会对时间、空间复杂度做出限制。此时再进一步思考，或许也可以使面试过程更加平滑地进行。

之前解决这个问题是出于自发，若非如此，则第一章无法进行下去。
待到了课后题阶段，该问题在第4题中被正确地提了出来。

你将会面对生成小于n且没有重复的k个整数的问题。

题目中提到的简单的方法是直接使用前k个正整数，这种做法对位排序效率基本无影响，却会歪曲调用原生的sort()方法的运行时间。

之间我的思路是remove掉randomIndex的数字，访问与remove总有一个要cost大量时间。
书中的做法明显聪明很多：
使用int[]结构，访问效率很高，那么不去remove，仅通过操作下标交换元素值打乱顺序即可。
做两次遍历，第一次对各元素遍历，循环中random一个index，将被遍历的元素与index位置的元素交换位置，这样一圈下来，整个数组即被完全打乱；第二次遍历即写入文件，最后留下几个数字，就像斗地主接牌最后剩下三张一下，作为文件中的缺失的数字。

public class BetterRandomNumber {

    private final static int MAX_NUMBER = 10000000;

    public static void main(String[] args) throws IOException {
        long startAt = currentTimeMillis();
        Random r = new Random(47);
        int removeCount = r.nextInt( 30) + 20;
        int[] s = new int[MAX_NUMBER];
        for (int i=0; i<MAX_NUMBER; i++) {
            s[i] = i+1;
        }
        for (int j=0; j<MAX_NUMBER; j++) {
            int randomIndex = r.nextInt(MAX_NUMBER-1);
            int temp = s[j];
            s[j] = s[randomIndex];
            s[randomIndex] = temp;
        }
        print("We remove " + removeCount + " numbers");
        PrintWriter writer = new PrintWriter("lot-number1.txt", "UTF-8");
        for (int k=0; k<MAX_NUMBER-removeCount; k++) {
            writer.println(s[k]);
        }
        writer.close();
        long endAt = currentTimeMillis();
        print("Program cost time: " + (float) (endAt - startAt) / 1000 + "s");
    }
}

运行时间

运行结果感人，竟然只需要2秒钟，只有自己新身去思考与编写这两种做法，并且为第一种方案难受过，才会更深切地感觉到这种天差地别。

有时，不得不感叹自己的方法多呆哦！