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

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

大家好,又见面了,我是全栈君。

/**
 * 功能:给定一个输入文件,包含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.       

转载于:https://my.oschina.net/u/2822116/blog/792607

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108766.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • html左侧浮动广告代码,jQuery 浮动广告实现代码[通俗易懂]

    html左侧浮动广告代码,jQuery 浮动广告实现代码[通俗易懂]实现方法:浮动广告#qqonline{background-color:red;border:1pxsolid#fcc;position:absolute;top:100px;left:16px;width:100px;height:120px;}#qqonline1{background-color:red;border:1pxsolid#fcc;position:absolute;…

  • ResNet 18 的结构解读「建议收藏」

    ResNet 18 的结构解读「建议收藏」现在很多网络结构都是一个命名+数字,比如(ResNet18),数字代表的是网络的深度,也就是说ResNet18网络就是18层的吗?其实这里的18指定的是带有权重的18层,包括卷积层和全连接层,不包括池化层和BN层。下面先贴出ResNet论文中给出的结构列表。对Pytorch中ResNet18网络的源码分析(这里),我画出了大致的网络结构图。可以看出,数字18=17个…

  • mysql 练习题及答案 50道

    mysql 练习题及答案 50道此50题参考出处,题目一样,代码有出入,因为题目比较有意思,都自己做了一次。https://zhuanlan.zhihu.com/p/50662216 –1、查询课程编号为“01”的课程比“02”的课程成绩高的所有学生的学号。–方法1select*fromscoreainnerjoinscorebon(a.s_id=b.s_idanda.c_id…

  • Nhibernate学习之性能改善1

    Nhibernate学习之性能改善1Nhibernate学习之性能改善1

  • Camera 之水波纹和banding现象[通俗易懂]

    Camera 之水波纹和banding现象[通俗易懂]预览画面中出现了一条明一条暗相间隔的竖条纹,这种现象叫做“水波纹”,并对原因进行了讲解,现记录如下。其实这些“水波纹”产生是因为手机的快门频率与灯光的频率不匹配导致的。首先,我们都知道手机拍照的时候都是有一定曝光时间的,例如假设手机的快门频率为50Hz,则其拍照时的曝光时间就是20ms。同理,屏幕或者日光灯不是一直在发光的,而是更隔一段时间就会刷新一次,我们生活中的日光灯为50Hz,国外的是60Hz。例如那个50Hz,就代表每秒刷新50次,因为刷…

    2022年10月13日
  • 自监督学习(一)自监督学习介绍

    自监督学习(一)自监督学习介绍自监督学习OverviewWhatisSelf-SupervisedLearning?WhyisSelf-SupervisedLearning?SomeExamplesUnsupervisedVisualRepresentationLearningbyContextPredictionUnsupervisedRepresentationLearningbyPred…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号