之前寫了生成磁盤文件用以位向量排序。
思路很清晰簡單攒岛，程序正確無誤。
但問題是它不夠好用胞锰，太慢了，要跑兩個小時嗅榕。
這和去面試時我的處理很像，看到問題誊册，先給出一個簡單直接暴力而不考慮性能的算法嘗試解決领突。之后面試官會開始要求更好的解法案怯，會對時間、空間復雜度做出限制嘲碱。此時再進一步思考金砍，或許也可以使面試過程更加平滑地進行麦锯。
之前解決這個問題是出于自發(fā)，若非如此扶欣，則第一章無法進行下去。
待到了課后題階段料祠，該問題在第4題中被正確地提了出來骆捧。
你將會面對生成小于n且沒有重復的k個整數(shù)的問題髓绽。
題目中提到的簡單的方法是直接使用前k個正整數(shù)，這種做法對位排序效率基本無影響顺呕，卻會歪曲調用原生的sort()方法的運行時間枫攀。
之間我的思路是remove掉randomIndex的數(shù)字，訪問與remove總有一個要cost大量時間株茶。
書中的做法明顯聰明很多：
使用int[]結構来涨，訪問效率很高，那么不去remove启盛，僅通過操作下標交換元素值打亂順序即可扫夜。
做兩次遍歷，第一次對各元素遍歷，循環(huán)中random一個index笤闯，將被遍歷的元素與index位置的元素交換位置堕阔，這樣一圈下來，整個數(shù)組即被完全打亂颗味；第二次遍歷即寫入文件超陆，最后留下幾個數(shù)字，就像斗地主接牌最后剩下三張一下浦马，作為文件中的缺失的數(shù)字时呀。
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秒鐘晶默，只有自己新身去思考與編寫這兩種做法谨娜，并且為第一種方案難受過，才會更深切地感覺到這種天差地別磺陡。
有時趴梢，不得不感嘆自己的方法多呆哦！
