对于32位的计算机而言,只有2G的内存(2的三十一次方),而十亿大概是2的32次方。因此,不能将其直接放到内存中进行处理。 一个byte有八位,我们可以开辟长度为2的29次方的byte数组,利用位映射原理,将要处理的数对8进行除法取商,商作为byte数组的下标,数组存储的元素可以转化为八位二进制,若二进制数的第i位为一,则表示该数对8取模的值为i。如:
假设某数据为9。9=8*1+1,即对8的商为1,对8取模为1。应该存在byte[1],将byte[1]的值改为00000002,即把2的一次方赋予byte[1]。
可以看到,新开数组的所需大小并不取决于数据量的大小,而是取决于某数据值的大小,新开的数组byte的大小N与所需处理的数据集之中的最大值Max有关,N>=Max/8。那么,先得到最大值,再进行查重可不可行呢,效率相对于直接开大空间有多大的提升呢?有待探究。
按照之前并不优雅的做法,就把数据量降低了n倍,得以对其进行各种操作。
下面上代码!
package SearchRepeatition; /** * @author lzj lzj.997@qq.com: * @version 创建时间:2015-1-31 下午5:05:42 类说明 :10亿数量级的查重 */ public class searchRepeat { // 查询方法 public void search(int[] array) { byte[] bytes = new byte[20];// 一个byte有8个bit,00000000 int[] binary = new int[8];// 开辟存储对应二进制数的数组 // 根据位图映射,得知byte数组的大小取决于数据集中的max; // 因此对数据大小相差大的集合处理效果并不理想 for (int i = 0; i < array.length; i++) { int index = (int) array[i] / 8;// 得到数字在bytes数组中的下标 int mod = array[i] % 8;// 得到数字对8的模 for (int j = 6; j >= 0; j--) { binary[j] = bytes[index] % 2; // 转成二进制存到binary数组,因转为二进制码要倒过来读,所以从6开始 bytes[index] = (byte) (bytes[index] / 2); } bytes[index] = (byte) Math.pow(2, mod); System.out.println("j=" + i + " index=" + index + " bytes[index]=" + bytes[index] + " mod=" + mod); // 如果binary[7-mod]为0,说明没有重复 if (binary[6 - mod] != 0) { System.out.println("数字:" + (mod + 8 * index) + "重复了"); } } } public static void main(String[] args) { int[] array = { 9, 1, 17, 38, 11, 26, 1, 1, 1, 9 }; searchRepeat sr = new searchRepeat(); long time = System.nanoTime(); sr.search(array); System.out.println("==time cost==" + (System.nanoTime() - time)); } }最后修改于2015/01/31.
相关推荐
\数据结构flash演示\版本1\10-3-4快速排序.swf \数据结构flash演示\版本1\10-4-2堆排序大顶堆.swf \数据结构flash演示\版本1\10-4-3堆排序大顶堆.swf \数据结构flash演示\版本1\10-4-4堆排序建立堆.swf \数据...
一、填空 ...试在0~19的散列地址空间中对关键字序列(19,01,23,14,55,20,84,27,68,11,10,77)造哈希表,并求等概率下查找成功时的平均查找长度。 .......
(2) 设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。 测试数据:构建二叉排序树的输入序列如下: 第一组数据: 100,150,120,50,70,60,80,170,180,160,110,30,40,35,175 ...
数据结构——二叉查找树(BST)静态查找表,使用数据结构实现BST
线性数据结构部分: 一、填空题 1. 数据结构包括数据的逻辑结构、 数据的储存结构 和数据的运算三个方面。 2. 数据结构包括 逻辑结构 、数据的存储结构和数据的运算三个方面。 3. 在算法"正确"的前提下,评价算法...
C++数据结构 数据结构 C++ 数据结构 C/C++ 数组允许定义可存储相同类型数据项的变量,但是结构是 C++ 中另⼀种⽤户⾃定义的可⽤的数据类型,它允许您存储不同类型的数 据项。 结构⽤于表⽰⼀条记录,假设您想要跟踪...
在复合数据结构中不 仅介绍了哈希链表、哈希红黑树、哈希AIL树等容器,还介绍了复合数据结构的通用设计方 法:在动态数据结构中主要介绍了动态环形队列、动态等尺寸内存管理算法。在内存管理中介 绍了在应用程序层...
自己整理的用C语言写的数据结构和排序查找算法。数据结构包括:栈,队列,两个队列实现一个栈,两个栈实现一个队列,二叉树的创建,添加,平衡二叉树天界旋转等,红黑树,创建,添加节点,删除节点,调整。算法包括...
c++数据结构c++数据结构c++数据结构c++数据结构
数据结构 试卷6 10 数据结构 试卷7 12 数据结构 试卷8 14 数据结构 试卷9 16 数据结构 试卷10 18 数据结构 试卷11 20 数据结构 试卷12 22 数据结构 试卷13及答案 24 数据结构 试卷14 28 数据结构试卷14答案...
软件工程09~10数据结构习题集的答案,对应《数据结构(C语言版)》
1、设计合适的数据结构存储朋友、分组信息,将以上文件内容导入其中(如果你觉得以上文件中的信息不合适,可以自行处理,删除某列、增加属性、规范化数据均可,如果你认为有必要,甚至去掉“编号”都可以)。...
个人根据各自的理解的不同而有不同 的表述方法: Sartaj Sahni在他的《数据结构、算法与应用》一书中称:"数据结构是数据对象,以与存在于该 对象的实例和组成实 例的数据元素之间的各种联系。这些联系可以通过定义...
这种特性是如此重要以至于在System.Collections.Generic命名空间中存在一个专门的泛型数据结构库。当数据结构具有在此库中能找到的泛型实现时,就会讨论它的用途。本章结尾处介绍了衡量书中讨论的数据结构与算法性能...
能理解数据结构在程序设计中的重要性。 5. 熟练掌握插入排序、Shell排序、堆排序、快速排序、基数排序等常用的各种排序算法及其时间和空间开销。 6. 了解文件管理(数据在外存中的组织形式)和外排序技术。 7...
数据结构与算法课程08 第八章 查找(共91页).ppt 数据结构与算法课程09 第九章 内存管理(共50页).ppt 数据结构与算法课程10 第十章 文件(共41页).ppt 数据结构与算法课程11 第十一章 随机数(共84页).ppt
又比如在一个数据库(关系式数据库)中,一个记录可称为一个数据元素,而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准,但是它包括以下三方面内容:逻辑结构、存储结构、和对数据的操作。这一...
本课程内容取自清华大学出版社出版的《数据结构》(C语言版)中的第1至第7章、第9至第10章,其中第1章综述数据、数据结构和抽象数据类型等基本概念;第2章至第7章从抽象数据类型的角度,分别讨论线性表、栈、队列、串...
数据结构基本实验程序,编程实现表的定义及常用操作:1)判断表示表是否为空;2)获取第i个节点的内容;3)删除;4)插入