从随机数开始

需求：获取一定范围内，指定个数的随机数

相信大家都会很容易就想到怎么去做

		//	获取100以内的20个随机数
		while(result.size() < 20) {
			int index = random.nextInt(100);
			if(result.contains(index)) 
				continue;
			else
				result.add(index);
		}

这个算法在数字很小的时候没什么区别，基本几毫秒就完事了。但是我们讨论以下几种情况：

1、当数字很大

需求：获取100000以内的20000个随机数

        //    获取100000以内的20000个随机数
        while(result.size() < 20000) {
            int index = random.nextInt(100000);
            if(result.contains(index)) 
                continue;
            else
                result.add(index);
        }

耗时：251MS

2、范围变小

        //    获取100000以内的99999个随机数
        while(result.size() < 99999) {
            int index = random.nextInt(100000);
            if(result.contains(index)) 
                continue;
            else
                result.add(index);
        }

耗时：耗时：69834MS（难以接受）

这种情况下，特别是后期，很明显大多数的随机结果都是重复无效的，这样耗费了大量的时间找到那一个有效数据。很明显这个算法是低效的。

说了这么多，就是想记录今天想到的一种新方式--缩小检索范围。

		// 获取100000以内的20000个随机数
		List<Integer> list = new ArrayList<Integer>();
		for(int i = 0; i < 100000; i++) {
			list.add(i);			
		}
		while(result.size() < 20000) {
			int index = random.nextInt(list.size());
			int num = list.get(index);
			result.add(num);
			list.remove(Integer.valueOf(num));
		}

　　耗时：953 MS

由于多做了一些工作，导致在选择很多的时候效率较低，花费了前一种算法的四倍时间

		// 获取100000以内的99999个随机数
		List<Integer> list = new ArrayList<Integer>();
		for(int i = 0; i < 100000; i++) {
			list.add(i);			
		}
		while(result.size() < 99999) {
			int index = random.nextInt(list.size());
			int num = list.get(index);
			result.add(num);
			list.remove(Integer.valueOf(num));
		}

　　耗时：3968MS

但是这种情况下，由于每次随机出现的数字都是有效地，这种算法花费的时间是第一种的1/17

算法是程序的灵魂，优秀的程序员在面对不同情况，不能一成不变，应该灵活的选中最优秀的算法

从随机数开始

推荐阅读