起
第一章“開篇”圍繞一個(gè)“如何給磁盤文件排序邦鲫？”的問(wèn)題展開灸叼。
具體描述是：
有一個(gè)磁盤文件，其最多包含n個(gè)正整數(shù)庆捺，每個(gè)整數(shù)一行怜姿，每個(gè)數(shù)都小于n，n=10^7疼燥，無(wú)重復(fù)整數(shù)出現(xiàn)沧卢。
而我們沒(méi)有這樣的一個(gè)文件，這意味著這章之后的一切實(shí)踐都無(wú)法進(jìn)行醉者。這是閱讀本書碰到的第一個(gè)必須解決的問(wèn)題但狭。
問(wèn)題細(xì)化與思路
由于Java編碼經(jīng)驗(yàn)不足，大多數(shù)處理都要靠查文檔撬即，分析問(wèn)題層面亦會(huì)比較注重Java語(yǔ)言本身立磁。
我打算使用Java的一個(gè)list(稱為s)結(jié)構(gòu)通過(guò)循環(huán)for(0-10^7)來(lái)向s塞入相應(yīng)的數(shù)字，此操作不會(huì)引入重復(fù)的整數(shù)剥槐。
使用隨機(jī)去掉s中的20~50個(gè)元素（這里有兩個(gè)隨機(jī)數(shù)唱歧，一個(gè)是要去掉的元素的個(gè)數(shù)，另一個(gè)是要去掉元素的位置）粒竖，最后通過(guò)選取隨機(jī)下標(biāo)將該元素pop出s并寫入文件颅崩。
主要涉及到編碼方面的以下幾點(diǎn)：
- 使用Java創(chuàng)建文件寫入內(nèi)容；
- 選擇一種合適list類蕊苗，可以根據(jù)下標(biāo)訪問(wèn)并pop元素沿后；
- 隨機(jī)數(shù)生成器的使用方法；
代碼
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個(gè)元素.
int removeCount = r.nextInt(30) + 20; // 生成20~49之間的一個(gè)整數(shù)朽砰；
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來(lái)存儲(chǔ)數(shù)字尖滚，其.get(index)與.remove(index)方法可以實(shí)現(xiàn)根據(jù)下標(biāo)位置的取值與pop。
而Random類的實(shí)例r使用.nextInt()方法時(shí)接受一個(gè)參數(shù)k瞧柔，可生成0至k-1之間的隨機(jī)整數(shù)漆弄，比較難受的寫法是要生成20~50間的隨機(jī)整數(shù)竟然要int removeCount = r.nextInt(30) + 20;，不知有沒(méi)有更直接一點(diǎn)的api啊造锅。
最后寫文件用到了PrintWriter類撼唾，其亦有println方法，讓人想到了重定向备绽，還蠻有意思的券坞。
性能問(wèn)題
該程序可以按需求生成lot-number.txt的磁盤文件。
可問(wèn)題是肺素，它太慢了恨锚，跑了2個(gè)小時(shí)左右才跑完。
ArrayList是數(shù)組結(jié)構(gòu)而不是鏈表倍靡，雖然取值為O(1)猴伶，而remove元素，則需要將它之后的元素進(jìn)行搬運(yùn)塌西，此為O(n)操作他挎。
而若使用鏈表的話，則.get(index)為O(n)捡需。
這里暫時(shí)難以兩全办桨。
同時(shí)，nextInt()方法好像也不夠快站辉。
那是否是生成隨機(jī)數(shù)占用了大量的時(shí)間呢呢撞？這個(gè)易于測(cè)試：
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++;
}
}
這段代碼運(yùn)行在40秒左右，雖然也不快（打印會(huì)占用不少時(shí)間）饰剥，但這并不是將程序運(yùn)行拖至兩個(gè)小時(shí)的因素殊霞。
回頭再來(lái)優(yōu)化這個(gè)問(wèn)題。
