文档章节

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

BravoZu
 BravoZu
发布于 2012/09/05 19:07
字数 427
阅读 371
收藏 4
点赞 0
评论 0

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

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

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

背景:使用随机书产生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#控制台应用程序——防伪码

摘 要 1. 生成多个防伪码,防伪码的长度和个数由用户指定。 2. 防伪码由"0123456789ABCDEFGHJKLMNPQRSTUVWXYZ"字符组成,生成的防伪码不可以 重复,必须是唯一的。 3. 防伪码的生成要具有随机...

1027 ⋅ 2014/06/17 ⋅ 0

Python 随机数标准库(1) -- random()

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

达闻西 ⋅ 2016/06/02 ⋅ 0

c#随机产生不重复数组

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

awbeci ⋅ 2011/04/14 ⋅ 0

shell实例浅谈之三产生随机数七种方法

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

898009427 ⋅ 2017/12/29 ⋅ 0

转载:在批处理中使用随机数字

在批处理中使用随机数字 RANDOM 是一个动态环境变量,用于返回一个0~32767 之间的随机整数。 当 CMD.exe 捕获到 RANDOM 关键字后,会调用相关函数生成一个基于当前系统时间的随机整数。 在代...

beijing_zbs ⋅ 2014/10/11 ⋅ 0

说说随机数

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

hubert_yu ⋅ 2016/03/14 ⋅ 0

shell 生成指定范围随机数与随机字符串

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

bobwei ⋅ 2016/02/04 ⋅ 0

微信红包金额分配的算法

以下内容转载自网络,仅供学习和吐槽 虽然春节已经过去一段时间,但不少微信群里面依旧乐此不疲的在玩发红包活动,用户自发的将最初的一个春节拜年的场景功能慢慢演化成一个长尾功能。 用户在...

李朝强 ⋅ 2016/05/31 ⋅ 0

bash脚本编程之数组及随机变量

变量:用来存储存在值的内存空间;特点是一个变量中仅能存储一个数值。 数组:能够容纳多个数组元素的连续的内存空间;包括两种类型:1.稀疏数组(bash属于稀疏数组):在数组中的元素编号可...

花花很漂漂 ⋅ 2017/11/29 ⋅ 0

浅谈Java中的几种随机数

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

迷途d书童 ⋅ 2012/03/21 ⋅ 14

没有更多内容

加载失败,请刷新页面

加载更多

下一页

oAuth2 升级Spring Cloud Finchley.RELEASE踩坑分享

背景 6.19号,spring团队发布了期待已久的 Spring Cloud Finchley.RELEASE 版本。 重要变化: 基于Spring Boot 2.0.X 不兼容 Spring Boot 1.5.X 期间踩过几个坑,分享出来给大伙,主要是关于...

冷冷gg ⋅ 38分钟前 ⋅ 0

OSChina 周一乱弹 —— 理发师小姐姐的魔法

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @冰冰棒- :分享田馥甄的单曲《My Love》 《My Love》- 田馥甄 手机党少年们想听歌,请使劲儿戳(这里) @Li-Wang :哎,头发又长了。。。又要...

小小编辑 ⋅ 今天 ⋅ 4

Kafka1.0.X_消费者API详解2

偏移量由消费者管理 kafka Consumer Api还提供了自己存储offset的功能,将offset和data做到原子性,可以让消费具有Exactly Once 的语义,比kafka默认的At-least Once更强大 消费者从指定分区...

特拉仔 ⋅ 今天 ⋅ 0

个人博客的运营模式能否学习TMALL天猫质量为上?

心情随笔|个人博客的运营模式能否学习TMALL天猫质量为上? 中国的互联网已经发展了很多年了,记得在十年前,个人博客十分流行,大量的人都在写博客,而且质量还不错,很多高质量的文章都是在...

原创小博客 ⋅ 今天 ⋅ 0

JavaScript零基础入门——(十一)JavaScript的DOM操作

JavaScript零基础入门——(十一)JavaScript的DOM操作 大家好,欢迎回到我们的JavaScript零基础入门。最近有些同学问我说,我讲的的比书上的精简不少。其实呢,我主要讲的是我在开发中经常会...

JandenMa ⋅ 今天 ⋅ 0

volatile和synchronized的区别

volatile和synchronized的区别 在讲这个之前需要先了解下JMM(Java memory Model :java内存模型):并发过程中如何处理可见性、原子性、有序性的问题--建立JMM模型 详情请看:https://baike.b...

MarinJ_Shao ⋅ 今天 ⋅ 0

深入分析Kubernetes Critical Pod(一)

Author: xidianwangtao@gmail.com 摘要:大家在部署Kubernetes集群AddOn组件的时候,经常会看到Annotation scheduler.alpha.kubernetes.io/critical-pod"="",以表示这是一个关键服务,那你知...

WaltonWang ⋅ 今天 ⋅ 0

原子性 - synchronized关键词

原子性概念 原子性提供了程序的互斥操作,同一时刻只能有一个线程能对某块代码进行操作。 原子性的实现方式 在jdk中,原子性的实现方式主要分为: synchronized:关键词,它依赖于JVM,保证了同...

dotleo ⋅ 今天 ⋅ 0

【2018.06.22学习笔记】【linux高级知识 14.4-15.3】

14.4 exportfs命令 14.5 NFS客户端问题 15.1 FTP介绍 15.2/15.3 使用vsftpd搭建ftp

lgsxp ⋅ 今天 ⋅ 0

JeeSite 4.0 功能权限管理基础(Shiro)

Shiro是Apache的一个开源框架,是一个权限管理的框架,实现用户认证、用户授权等。 只要有用户参与一般都要有权限管理,权限管理实现对用户访问系统的控制,按照安全规则或者安全策略控制用户...

ThinkGem ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部