编程珠玑(1)

开始看了下编程珠玑，书的开篇就是一个排序的问题，今天就来实践一下，稍作修改，如题目大意：生成1千万个1亿以内的不重复的数据集合.

public final static int count = 100000000;
private static boolean[] collect = new boolean[count];
private static int[] source = new int[count/10];

public void createDate() {
	int temp  = 0;
	for(int i = 0; i < count/10;) {
                temp = new Random().nextInt(count);
		if(!collect[temp]) {
			source[i] = temp;
			collect[temp] = true;
			System.out.println(i + " = " + source[i] );
			i++;
		}
	}
}

 这通过boolean来标识的话，速度确实加快了不少，直接变为了近O(n)了，不知道还能不能进行改进~~~

 

评论

1 楼 gangwazi0525 2012-03-07  

那个无重复随机数生成算法可以改进，楼主采用的是S算法，可以换成效率更高的F算法。F算法在编程珠玑（续）里有讲。在我的机子上楼主的算法跑下来需要19188ms，采用F算法改进的只需要1765ms。

public final static int count = 10000000;
	private static boolean[] collect = new boolean[count];
	private int[] source = new int[count/10];
	
	// 采用Floyd算法生成10000000个0~100000000之间的无重复随机整数，并对其进行排序
	public void sort() {
		int n = count;
		int m = count / 10;
		int temp = 0;
		for (int i = n-m; i < n; i ++) {
			temp = new Random().nextInt(n);
			if (!collect[temp]) {
				source[i-n+m] = temp;
				collect[temp] = true;
			} else {
				source[i-n+m] = i;
				collect[i] = true;
			}
		}
	}