文档章节

给定一个输入文件,包含40亿个非负整数。产生一个不在该文件中的整数。内存限制:1GB

一贱书生
 一贱书生
发布于 2016/11/23 09:06
字数 758
阅读 7
收藏 0
点赞 0
评论 0

/**
 * 功能:给定一个输入文件,包含40亿个非负整数。产生一个不在该文件中的整数。内存限制:1GB
 * 进阶:内存限制10MB。

 */

 

 

[java] view plain copy

 

  1. /** 
  2.  * 思路: 
  3.  *  
  4.  * 1)创建包含40个亿个比特的位向量。 
  5.  *     位向量(BV,bit vector)其实就是数组,利用整数(或另一种数据类型)数组紧凑地储存布尔值。每个整数可存储一串32比特或布尔值。 
  6.  * 2)将BV的所有元素初始化为0. 
  7.  * 3)扫描文件中的所有数字(num),并调用BV.set(num,1)。 
  8.  * 4)接着,再次从索引0开始扫描BV。 
  9.  * 5)返回第一个值为0的索引。 
  10.  *  
  11.  *  
  12.  * 值的确定: 
  13.  * 1)2^32——>40亿个不同的整数,一个整数4个字节。 
  14.  * 2)2^30字节——>1GB——>2^33bit——>80亿比特位。每一位映射一个不同的整数,可以存储之多80亿个不同的整数。 
  15.  */  
  16. long numberOfInts=((long)Integer.MAX_VALUE)+1;  
  17. byte[] bitfield=new byte[(int) (numberOfInts/8)];  
  18.   
  19. public void findOpenNumber() throws FileNotFoundException{  
  20.     Scanner in=new Scanner(new FileReader("f:\\file.txt"));  
  21.       
  22.     while(in.hasNext()){  
  23.         int n=in.nextInt();  
  24.         /* 
  25.          *  使用OR操作符设置一个字节的第n位,找出bitfield中相对应的数字。 
  26.          * (例如,10(十进制)将对应于字节数组中索引2的第2位) 
  27.          */  
  28.         bitfield[n/8]=(byte) (1<<(n%8));  
  29.     }  
  30.       
  31.     for(int i=0;i<bitfield.length;i++){  
  32.         for(int j=0;j<8;j++){  
  33.             /* 
  34.              * 取回每个字节的各个比特。当发现某个比特为0时,即找到相对应的值。 
  35.              */  
  36.             if((bitfield[i]&(1<<j))==0){  
  37.                 System.out.println(i*8+j);  
  38.                 return;  
  39.             }  
  40.         }  
  41.     }  
  42. }  

 

 

进阶:10MB

 

[java] view plain copy

 

  1. /** 
  2.  * 思路:对数据集进行两次扫描,就可以找出不在文件中的整数。可以将全部整数划分为同等大小的区块。 
  3.  * 第一次扫描数组:确定每个数组的元素个数。 
  4.  * 第二次扫描位向量:确定该范围内少的数字。 
  5.  *  
  6.  * bitSize::第一次扫描时每个块范围的大小。 
  7.  * blockNum:第一次扫描时块的个数。 
  8.  *  
  9.  * 值的确定: 
  10.  * 1)10MB——>2^23Byte。一个整数4个字节,因此,最多包含2^21个元素的数组。 
  11.  * 2)bitSize=(2^32/blockNum)<=2^21,所以,blockNum>=2^11。 
  12.  * 2^11<=bitSize<=2^26。 
  13.  * 在这些条件下,挑选出越靠中间的值,那么,在任何时候所诉的内存就越少。 
  14.  */  
  15.   
  16. int bitSize=1048576;  
  17. int blockNum=4096;  
  18.   
  19. byte[] bitfield2=new byte[bitSize/8];  
  20. int[] blocks=new int[blockNum];  
  21.   
  22. public void findOpenNumber2() throws FileNotFoundException{  
  23.     Scanner in=new Scanner(new FileReader("f:\\file.txt"));  
  24.       
  25.     int starting=-1;  
  26.     while(in.hasNext()){  
  27.         int n=in.nextInt();  
  28.         blocks[n/bitfield2.length*8]++;  
  29.     }  
  30.       
  31.     for(int i=0;i<blocks.length;i++){  
  32.         /* 
  33.          * 若小于,则说明该块中至少少了一个数字 
  34.          */  
  35.         if(blocks[i]<bitfield2.length*8){  
  36.             starting=i*bitfield2.length*8;  
  37.             break;  
  38.         }  
  39.     }  
  40.       
  41.     in =new Scanner(new FileReader("f:\\file.txt"));  
  42.     while(in.hasNext()){  
  43.         int n=in.nextInt();  
  44.         if(n>=starting&&n<starting+bitfield2.length*8){  
  45.             bitfield2[(n-starting)/8]=(byte) (1<<((n-starting)%8));  
  46.         }  
  47.     }  
  48.       
  49.     for(int i=0;i<bitfield2.length;i++){  
  50.         for(int j=0;j<8;j++){  
  51.             /* 
  52.              * 取回每个字节的各个比特。当发现某个比特为0时,即找到相对应的值。 
  53.              */  
  54.             if((bitfield2[i]&(1<<j))==0){  
  55.                 System.out.println(i*8+j+starting);  
  56.                 return;  
  57.             }  
  58.         }  
  59.     }  
  60.       

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 723
码字总数 600072
作品 0
万变不离其宗之海量数据下的算法问题处理思路

本文介绍 万变不离其宗之海量数据下的算法问题处理思路 万变不离其宗之海量数据下的算法问题处理思路 本文由在当地较为英俊的男子金天大神原创,版权所有,欢迎转载,但请保留这段版权信息,...

Nicholas_Jela
2017/09/06
0
0
算法精讲学习笔记 大数据和位运算

1.哈希函数 (1)哈希函数即散列函数 哈希函数的输入域可以是非常大的范围, 但是输出域是固定范围。 (2)哈希函数的性质: a.典型的哈希函数都有无线的输入值域 b.输入值相同时,返回值相同...

范大脚脚
2017/11/16
0
0
《编程珠玑》第二章:啊哈!算法——左旋转&&变位词

本章讲解的是算法的作用,“看起来很困难的问题也可以有一个简单的、意想不到的答案。”在任何愿意在编程之前、之中和之后进行认真思考的程序员都有机会捕捉到这灵光一闪。 文章从三个问题展...

陈凯俊
2012/11/19
0
0
COGS 1299. bplusa【听说比a+b还要水的大水题???】

1299. bplusa 输入文件: 输出文件: 评测插件 时间限制:1 s 内存限制:128 MB 【题目描述】 输入一个整数n,将其拆为两个非负整数a,b,使a,b的和等于n。 【输入格式】 输入数据只有一行,为...

angel_kitty
2017/07/13
0
0
编程珠玑--位图法排序

位图法是《编程珠玑》第一章中出现的磁盘排序算法。 题目:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7,且所有正整数都不重复。求如何将这n个正整数升序排列。 约束:最多有1MB...

王二狗子11
01/08
0
0
[转]海量数据处理的面试题的方法总结

处理海量数据问题,无非就是: 分而治之/hash映射 + hash统计 + 堆/快速/归并排序; Bloom filter/Bitmap; Trie树/数据库/倒排索引; 外排序; 分布式处理之hadoop/mapreduce。 本文接下来的...

十一11
2016/03/11
172
0
题目2:递归解压缩文件,并计算压缩包中的所有文件内保存的数字之和

一、题目 定义文件 xx.tar.gz 的产生方式如下: 以 xx 为文件名的文件通过 tar 和 gzip 打包压缩产生,该文件中以字符串的方式记录了一个非负整数; 或者以 xx 为名的目录通过 tar 和 gzip 打...

北风其凉
2015/04/02
0
0
Hadoop面试45个题目及答案

本人博客开始迁移,博客整个架构自己搭建及编码http://www.cookqq.com/listBlog.action 1.Hadoop集群可以运行的3个模式? 单机(本地)模式 伪分布式模式 全分布式模式 2. 单机(本地)模式中...

cookqq
2014/03/18
0
0
海量数据处理:十道面试题与十个海量数据处理方法总结

1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射...

ahucsxl
2015/10/08
165
0
十道海量数据处理面试题与十个方法大总结

海量数据处理:十道面试题与十个海量数据处理方法总结 本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。 出处:http://blog.csdn.net/vJULYv。 第一部分、十道海量数据处理面试题...

吟啸_徐行
2014/04/02
0
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

about git flow

  昨天元芳做了git分支管理规范的分享,为了拓展大家关于git分支的认知,这里我特意再分享这两个关于git flow的链接,大家可以看一下。 Git 工作流程 Git分支管理策略   git flow本质上是...

qwfys
今天
2
0
Linux系统日志文件

/var/log/messages linux系统总日志 /etc/logrotate.conf 日志切割配置文件 参考https://my.oschina.net/u/2000675/blog/908189 dmesg命令 dmesg’命令显示linux内核的环形缓冲区信息,我们可...

chencheng-linux
今天
1
0
MacOS下给树莓派安装Raspbian系统

下载镜像 前往 树莓派官网 下载镜像。 点击 最新版Raspbian 下载最新版镜像。 下载后请,通过 访达 双击解压,或通过 unzip 命令解压。 检查下载的文件 ls -lh -rw-r--r-- 1 dingdayu s...

dingdayu
今天
1
0
spring boot使用通用mapper(tk.mapper) ,id自增和回显等问题

最近项目使用到tk.mapper设置id自增,数据库是mysql。在使用通用mapper主键生成过程中有一些问题,在总结一下。 1、UUID生成方式-字符串主键 在主键上增加注解 @Id @GeneratedValue...

北岩
今天
2
0
告警系统邮件引擎、运行告警系统

告警系统邮件引擎 cd mail vim mail.py #!/usr/bin/env python#-*- coding: UTF-8 -*-import os,sysreload(sys)sys.setdefaultencoding('utf8')import getoptimport smtplibfr......

Zhouliang6
今天
1
0
Java工具类—随机数

Java中常用的生成随机数有Math.random()方法及java.util.Random类.但他们生成的随机数都是伪随机的. Math.radom()方法 在jdk1.8的Math类中可以看到,Math.random()方法实际上就是调用Random类...

PrivateO2
今天
2
0
关于java内存模型、并发编程的好文

Java并发编程:volatile关键字解析    volatile这个关键字可能很多朋友都听说过,或许也都用过。在Java 5之前,它是一个备受争议的关键字,因为在程序中使用它往往会导致出人意料的结果。在...

DannyCoder
昨天
1
0
dubbo @Reference retries 重试次数 一个坑

在代码一中设置 成retries=0,也就是调用超时不用重试,结果DEBUG的时候总是重试,不是0吗,0就不用重试啊。为什么还是调用了多次呢? 结果在网上看到 这篇文章才明白 https://www.cnblogs....

奋斗的小牛
昨天
2
0
数据结构与算法3

要抓紧喽~~~~~~~放羊的孩纸回来喽 LowArray类和LowArrayApp类 程序将一个普通的Java数组封装在LowArray类中。类中的数组隐藏了起来,它是私有的,所以只有类自己的方法才能访问他。 LowArray...

沉迷于编程的小菜菜
昨天
1
0
spring boot应用测试框架介绍

一、spring boot应用测试存在的问题 官方提供的测试框架spring-boot-test-starter,虽然提供了很多功能(junit、spring test、assertj、hamcrest、mockito、jsonassert、jsonpath),但是在数...

yangjianzhou
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部