文档章节

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

BravoZu
 BravoZu
发布于 2012/09/05 19:07
字数 427
阅读 378
收藏 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
shell实例浅谈之三产生随机数七种方法

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

898009427
2017/12/29
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 生成指定范围随机数与随机字符串 1.使用系统的 $RANDOM 变量 fdipzone@ubuntu :~$ echo $RANDOM 17617 $RANDOM 的范围是 [0, 32767] 如需要生成超过32767的随机数,可以用以下方法实现...

bobwei
2016/02/04
152
0
浅谈Java中的几种随机数

众所周知,随机数是任何一种编程语言最基本的特征之一。而生成随机数的基本方式也是相同的:产生一个0到1之间的随机数。看似简单,但有时我们也会忽略了一些有趣的功能。 我们从书本上学到什...

迷途d书童
2012/03/21
43.1K
14

没有更多内容

加载失败,请刷新页面

加载更多

通过Docker容器连接代理Wormhole

Wormhole 是一个能识别命名空间的由 Socket 激活的隧道代理。可以让你安全的连接在不同物理机器上的 Docker 容器。可以用来完成一些有趣的功能,例如连接运行在容器本机的服务或者在连接后创...

Linux就该这么学
18分钟前
1
0
从架构到平台, POWER 9处理器最全解读

本文根据IBM中国芯片设计部门高级经理尹文,在「智东西公开课」的超级公开课IBM专场《POWER 9-认知时代的驱动力》 上的系统讲解整理而来。 本次讲解中,尹文老师从内核微架构、总线互连、异构...

Mr_zebra
21分钟前
1
0
openjdk和oraclejdk有什么区别吗?

1.授权协议的不同:OpenJDK采用GPL V2协议放出,而SUN JDK则采用JRL放出。两者协议虽然都是开放源代码的,但是在使用上的不同在于GPL V2允许在商业上使用,而JRL只允许个人研究使用。 2.Open...

吴伟祥
22分钟前
2
0
c++基类析构函数要声明为virtual的原因

更深层的原因不知道,不过标准规定,如果不声明为virtual,那么将会导致未定义行为。个人测试结果表明,如果不声明为virtual,那么派生类的析构函数将不会得到调用

安非他命
29分钟前
1
0
CentOS 7下protobuf的源码编译安装

protobuf的github地址:https://github.com/google/protobuf支持多种语言,有多个语言的版本,本文采用的是在CentOS 7下编译源码进行安装。 github上有详细的安装说明:https://github.com/...

xtof
35分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部