文档章节

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

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

精选30+云产品,助力企业轻松上云!>>>

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

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

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

背景:使用随机书产生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
博文 55
码字总数 34816
作品 0
广州
程序员
私信 提问
加载中
请先登录后再评论。
[Java] [工具] - 随机数

我们从书本上学到什么? 最明显的,也是直观的方式,在Java中生成随机数只要简单的调用: java.lang.Math.random() 在所有其他语言中,生成随机数就像是使用Math工具类,如abs, pow, floor, ...

子允
2016/04/25
7
0
10.Set集合

目录介绍 1.Set集合 1.1 特点 1.2 注意 2.HashSet 2.1 特点 2.2 如何保证元素唯一性 2.3 使用HashSet集合存储自定义对象,保证元素的唯一性 2.4 存储图解 3.LinkedHashSet 3.1 特点 4.TreeSe...

潇湘剑雨
2018/04/29
15
0
redis 学习(13)-- BitMap

BitMap 什么是 BitMap BitMap,即位图,其实也就是 byte 数组,用二进制表示,只有 0 和 1 两个数字。 如图所示: 重要 API 命令 含义 getbit key offset 对key所存储的字符串值,获取指定偏...

osc_8zk7ewr4
2019/06/02
1
0
Mysql数据库理论基础之六--VIEW视图

一、简介 由MySQL AB公司开发,是最流行的开放源码SQL数据库管理系统,主要特点: 1、是一种数据库管理系统 2、是一种关联数据库管理系统 3、是一种开放源码软件,且有大量可用的共享MySQL软...

风过_无痕
2017/06/09
0
0
Java获取随机数

在 Java中我们可以使用java.util.Random类来产生一个随机数发生器。它有两种形式的构造函数,分别是Random()和 Random(long seed)。Random()使用当前时间即System.currentTimeMillis()作为发...

java-苦苦甜甜
2012/10/26
68
0

没有更多内容

加载失败,请刷新页面

加载更多

iOS14新特性探索之二:App Widget小组件应用

iOS14新特性探索之二:App Widget小组件应用 iOS 14除了引入了亮眼的App Clips功能外。还有一个也非常惹争议的功能就是App Widget。App Widget可以理解为小组件,在非常早的Android版本中就有...

珲少
15分钟前
11
0
科目二笔记

窄路掉头 行至肩膀与白线平行,向左打到底,等待车行进入窄路。待车与路程45°时,回半圈,继续前行待车与边线平行后回正。然后继续行至车盖压住前面的线后向左打到底,伸出头看前轮与边线距...

bug0day
24分钟前
6
0
Java基础系列——数组相关算法(11)

这里介绍一下数组中的常用算法 杨辉三角形 杨辉三角:它的两个边都是1,内部其它都是肩上两个数的和。 public class YangHui { public static void main(String[] args) { ...

卢佳鹏
24分钟前
23
0
thinkphp-nginx.conf

server{ listen 80; server_name test.cn; index index.php; root /data/wwwroot/test_tp5/public; include thinkphp.conf; location ~ [^/]\.php(/|$) ......

mind-blowing
26分钟前
7
0
Mysql死锁处理

1、错误信息 在mysql客户端执行update语句报错信息:ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction下面是在程序里面看到的错误信息com.mysql.cj.jdbc.ex...

简到珍
29分钟前
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部