文档章节

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

BravoZu
 BravoZu
发布于 2012/09/05 19:07
字数 427
阅读 375
收藏 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
粉丝 12
博文 54
码字总数 34332
作品 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
Python 随机数标准库(1) -- random()

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

达闻西
2016/06/02
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

没有更多内容

加载失败,请刷新页面

加载更多

redis 系列一 -- 简介及安装

1.简介 redis -- remote dictionary server 远程字典服务 使用 C 语言编写; 高性能的 key-value数据库; 内存数据库,支持数据持久化。 Redis 是一个开源(BSD许可)的,内存中的数据结构存...

imbiao
31分钟前
1
0
nginx log记录请求响应时间

有时为了方便分析接口性能等,需要记录请求的时长,通过修改nginx的日志格式可以做到,如 添加一个新的log_format log_format timed_combined '$remote_addr - $remote_user [$time_local] "...

swingcoder
54分钟前
2
0
Spring MVC之RequestMappingHandlerMapping匹配

对于RequestMappingHandlerMapping,使用Spring的同学基本都不会陌生,该类的作用有两个: 通过request查找对应的HandlerMethod,即当前request具体是由Controller中的哪个方法进行处理; 查...

爱宝贝丶
58分钟前
2
0
Java Web--增删改查之二界面后台java代码(转载参考)

/** *  *//** * @author Administrator * */package dao; import java.sql.*;public class DBConn {/** * 链接数据库 * @return */  ...

小橙子的曼曼
今天
2
0
Redis源码阅读笔记-对象及其类型和编码

总结之《Redis设计与实现》 对象 Redis中是使用对象来便是数据库中的键和值。 结构 // server.h...#define LRU_BITS 24...typedef struct redisObject { unsigned type:4; ...

Jian_Ming
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部