文档章节

使用Random产生100个无重复随机数,使用Set存储和使用位图存储的效率对比

BravoZu
 BravoZu
发布于 2012/09/05 19:07
字数 427
阅读 385
收藏 4

       今天读《编程珠玑》开篇就被里面的内容深深的吸引住了,很后悔之前只是单单听说它的大名,却从没有拜读,胜感遗憾。

    粗略的看了第一章关于位图数据结构的:该数据结构描述了一个有限定义域内的稠密集合,每个元素并且出现一次没有与其他数有关联。

   于是想到了想用随机数来测试一下,看看效果如何。

背景:使用随机书产生1000个不相同的数字,并且按从小到大排列。

(1)采用java的Set数据结构存储,并进行排序,代码如下:

		Set<Integer> datas= new HashSet<Integer>();
		Random random = new Random();
		int i = 0;
		long start = System.currentTimeMillis();
		while (i < 1000) {
			int a = Math.abs(random.nextInt() % 1000);
			if (datas.add(a)) {
				i++;
			}

		}
		Arrays.sort(datas.toArray());
		long end = System.currentTimeMillis();
		System.out.println("set 花费时间:" + (end - start));

(2)采用位图数据结构,具体代码如下:

		byte[] b = new byte[1001];
		int i = 0;
		Random random = new Random();
		long start = System.currentTimeMillis();
		while (i < 1000) {
			int a = Math.abs(random.nextInt() % 1000);
			if (b[a] == 0) {
				b[a] = 1;
				i++;
			}
		}
		long end = System.currentTimeMillis();
		System.out.println("位图 花费的时间:" + (end - start));

 测试结果:

         (1)采用Set数据结构花费的时间:6ms。

          (2)采用位图数据结构花费的时间:1ms.

      从上面的测试结果,让我想到了百度以前的一道笔试题,在最大的数小于500万的数中存在两个相同的数,将其找出来,要求花费最少的时间,和空间(大致好像就是这个意思),个人感觉采用位图数据结构应该是很不错的方法。

 

© 著作权归作者所有

共有 人打赏支持
BravoZu
粉丝 13
博文 54
码字总数 34332
作品 0
广州
程序员
私信 提问
Python 随机数标准库(1) -- random()

Python random包可以用来生成随机数。随机数不仅可以用于数学用途,还经常被嵌入到算法中,用以提高算法效率,并提高程序的安全性。如果想要更加高级的数学功能,可以考虑选择标准库之外的n...

达闻西
2016/06/02
0
0
c#随机产生不重复数组

在.NET技术 C#区看到一个小问题:从1,50随机20个不重复数。 问题不复杂,提问者其实已经有了自己的答案,但他似乎觉得答案不太理想。 ArrayList list =new ArrayList(); int k =0; do { k =r...

awbeci
2011/04/14
0
0
shell实例浅谈之三产生随机数七种方法

一、问题 Shell下有时需要使用随机数,在此总结产生随机数的方法。计算机产生的的只是“伪随机数”,不会产生绝对的随机数(是一种理想随机数)。伪随机数在大量重现时也并不一定保持唯一,但...

898009427
2017/12/29
0
0
shell 生成指定范围随机数与随机字符串

shell 生成指定范围随机数与随机字符串 1.使用系统的 $RANDOM 变量 fdipzone@ubuntu :~$ echo $RANDOM 17617 $RANDOM 的范围是 [0, 32767] 如需要生成超过32767的随机数,可以用以下方法实现...

bobwei
2016/02/04
152
0
说说随机数

常用的java产生整型随机数的方法有三种: Math.random() Random.nextint() Random.nextint(int) 基本功能: 第一个产生0(包括)到1(不包括)之间的一个double类型的随机数。 第二个是产生一...

hubert_yu
2016/03/14
30
0

没有更多内容

加载失败,请刷新页面

加载更多

远程获得的有趣的linux命令

使用这些工具从远程了解天气、阅读资料等。 我们即将结束为期 24 天的 Linux 命令行玩具日历。希望你有一直在看,如果没有,请回到开始,从头看过来。你会发现 Linux 终端有很多游戏、消遣和...

Linux就该这么学
10分钟前
0
0
Apollo配置详细步骤(Windows环境)

一. 准备工作 1.下载 apollo 安装包 下载链接:http://activemq.apache.org/apollo/download.html 2.下载 java JDK 安装包 ( apollo 依赖 java 环境) 下载链接:http://www.oracle.com/techn......

morpheusWB
31分钟前
0
0
聊聊flink的AsyncWaitOperator

序 本文主要研究一下flink的AsyncWaitOperator AsyncWaitOperator flink-streaming-java_2.11-1.7.0-sources.jar!/org/apache/flink/streaming/api/operators/async/AsyncWaitOperator.java ......

go4it
57分钟前
1
0
Java并发编程基础(四)

ThreadGroup 在主线程创建得线程,如果没有给他指定线程组,那么创建的线程,默认和主线程同一个线程组。线程组可以底下可以是线程,也可以实线程组。 构建线程组的方法: private ThreadGr...

chendom
今天
2
0
Scala学习(一)

学习Spark之前需要学习Scala。 参考学习的书籍:快学Scala

柠檬果过
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部