`
wbj0110
  • 浏览: 1615823 次
  • 性别: Icon_minigender_1
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

一种高效的适宜于海量数据排序的算法

阅读更多

常用的排序算法:

    冒泡序,快速排序,直接选择排序,堆排序,希尔排序,归并排序等;无指针分组排序算法

    冒泡排序不适宜于逆序

    快速排序算法能减少逆序时所消耗的扫描和数据交换次数;

    堆排序对数据的有效性不敏感,适宜于较大的序列排序

    直接插入算法排序对数据的有序性非常敏感,在最优情况下只需要经过n-1次比较,而最坏情况下需要n(n-1)/2次比较

   希尔排序也是一种基于插入排序的算法,但能够改善整个排序性能

   归并排序需要与待排序序列一样多的辅助空间,其时间复杂度固定为O(nlog n)

 

题目解析:

题目大意:移动公司需要对已经发放的所有139段的号码进行统计排序,已经发放的139号码段的文件都存放在一个文本文件中(原题是放在两个文件中),一个号码一行,现在需要将文件里的所有号码进行排序,并写入到一个新的文件中;号码可能会有很多,最多可能有一亿个不同的号码(所有的139段号码),存入文本文件中大概要占1.2G的空间;jvm最大的内存在300以内,程序要考虑程序的可执行性及效率;只能使用Java标准库,不得使用第三方工具。 
    这是个典型的大数据量的排序算法问题,首先要考虑空间问题,一下把1.2G的数据读入内存是不太可能的,就算把1一亿条数据,转都转换成int类型存储也要占接近400M的空间。当时做个题目我并没有想太多的执行效率问题,主要就考虑了空间,而且习惯性的想到合并排序,基本思想是原文件分割成若干个小文件并排序,再将排序好的小文件合并得到最后结果,算法大概如下: 

    1.顺序读取存放号码文件的中所有号码,并取139之后的八位转换为int类型;每读取号码数满一百万个(这个数据可配置)将已经读取的号码排序并存入新建的临时文件。 
    2.将所有生成的号码有序的临时文件合并存入结果文件。
 

    这个算法虽然解决了空间问题,但是运行效率极低,由于IO读写操作太多,加上步骤1中的排序的算法(快速排序)本来效率就不高(对于电话排序这种特殊情况来说),导致1亿条数据排序运行3个小时才有结果。 

    如果和能够减少排序的时间呢?首当其冲的减少IO操作,另外如果能够有更加好排序算法也行。前天无聊再看这个题目时突然想到大三时看《编程珠玑》时上面也有个问题的需求这个这个题目差不多,记得好像使用是位向量(实际上就是一个bit数组),用电话作为index,心中大喜,找到了解决此问题的最完美方案啦:用位向量存储电话号码,一个号码占一个bit,一亿个电话号码也只需要大概12M的空间;算法大概如下: 
      1.初始化bits[capacity]; 
      2.顺序所有读入电话号码,并转换为int类型,修改位向量值:bits[phoneNum]=1; 
      3.遍历bits数组,如果bits[index]=1,转换index为电话号码输出。
 
    Java中没有bit类型,一个boolean值占空间为1byte(感兴趣的可以自己写程序验证),我自己写个个用int模拟bit数组的类,代码如下: 
   

Java代码  收藏代码
  1. public class BitArray {  
  2.     private int[] bits = null;  
  3.     private int length;  
  4.     //用于设置或者提取int类型的数据的某一位(bit)的值时使用  
  5.     private final static int[] bitValue = {  
  6.         0x80000000,//10000000 00000000 00000000 00000000        
  7.         0x40000000,//01000000 00000000 00000000 00000000        
  8.         0x20000000,//00100000 00000000 00000000 00000000        
  9.         0x10000000,//00010000 00000000 00000000 00000000        
  10.         0x08000000,//00001000 00000000 00000000 00000000        
  11.         0x04000000,//00000100 00000000 00000000 00000000        
  12.         0x02000000,//00000010 00000000 00000000 00000000        
  13.         0x01000000,//00000001 00000000 00000000 00000000        
  14.         0x00800000,//00000000 10000000 00000000 00000000        
  15.         0x00400000,//00000000 01000000 00000000 00000000        
  16.         0x00200000,//00000000 00100000 00000000 00000000        
  17.         0x00100000,//00000000 00010000 00000000 00000000        
  18.         0x00080000,//00000000 00001000 00000000 00000000        
  19.         0x00040000,//00000000 00000100 00000000 00000000        
  20.         0x00020000,//00000000 00000010 00000000 00000000        
  21.         0x00010000,//00000000 00000001 00000000 00000000            
  22.         0x00008000,//00000000 00000000 10000000 00000000        
  23.         0x00004000,//00000000 00000000 01000000 00000000        
  24.         0x00002000,//00000000 00000000 00100000 00000000        
  25.         0x00001000,//00000000 00000000 00010000 00000000        
  26.         0x00000800,//00000000 00000000 00001000 00000000        
  27.         0x00000400,//00000000 00000000 00000100 00000000        
  28.         0x00000200,//00000000 00000000 00000010 00000000        
  29.         0x00000100,//00000000 00000000 00000001 00000000        
  30.         0x00000080,//00000000 00000000 00000000 10000000        
  31.         0x00000040,//00000000 00000000 00000000 01000000        
  32.         0x00000020,//00000000 00000000 00000000 00100000        
  33.         0x00000010,//00000000 00000000 00000000 00010000        
  34.         0x00000008,//00000000 00000000 00000000 00001000        
  35.         0x00000004,//00000000 00000000 00000000 00000100        
  36.         0x00000002,//00000000 00000000 00000000 00000010        
  37.         0x00000001 //00000000 00000000 00000000 00000001              
  38.     };  
  39.     public BitArray(int length) {  
  40.         if(length < 0){  
  41.             throw new IllegalArgumentException("length必须大于零!");  
  42.         }  
  43.         bits = new int[length / 32 + (length % 32 > 0 ? 1 : 0)];  
  44.         this.length = length;  
  45.     }  
  46.     //取index位的值  
  47.     public int getBit(int index){  
  48.         if(index <0 || index > length){  
  49.             throw new IllegalArgumentException("length必须大于零小于" + length);  
  50.         }  
  51.         int intData = bits[index/32];  
  52.         return (intData & bitValue[index%32]) >>> (32 - index%32 -1);  
  53.     }  
  54.     //设置index位的值,只能为0或者1  
  55.     public void setBit(int index,int value){  
  56.         if(index <0 || index > length){  
  57.             throw new IllegalArgumentException("length必须大于零小于" + length);  
  58.         }         
  59.         if(value!=1&&value!=0){  
  60.             throw new IllegalArgumentException("value必须为0或者1");  
  61.         }  
  62.         int intData = bits[index/32];  
  63.         if(value == 1){  
  64.             bits[index/32] = intData | bitValue[index%32];  
  65.         }else{  
  66.             bits[index/32] = intData & ~bitValue[index%32];  
  67.         }  
  68.     }  
  69.     public int getLength(){  
  70.         return length;  
  71.     }     
  72. }      
  73.       


    
    bit数组有了,剩下就是算法代码,核心代码如下: 
   

Java代码  收藏代码
  1. bitArray = new BitArray(100000000);   
  2. //顺序读取所有的手机号码  
  3. while((phoneNum = bufferedReader.readLine())!=null){  
  4.     phoneNum = phoneNum.trim().substring(3);//13573228432  
  5.     //取139后8位转换为int类型  
  6.     phoneNumAsInt = Integer.valueOf(phoneNum);  
  7.     //设置对应bit值为1  
  8.     bitArray.setBit(phoneNumAsInt, 1);  
  9. }     
  10. //遍历bit数组输出所有存在的号码  
  11. for(int i = 0;i<sortUnit;i++){  
  12.     if(bitArray.getBit(i)==1){  
  13.             writer.write("139" + leftPad(String.valueOf(i + sortUnit*times), 8));  
  14.             writer.newLine();                         
  15.     }                 
  16. }  
  17. writer.flush();  
  18.    


    经测试,修改后的算法排序时只需要20多M的内存,一亿条电话号码排序只要10分钟(时间主要花在IO上),看来效果还是很明显的。 
    这个算法很快,不过也有他的局限性: 
    1.只能用于整数的排序,或者可以准确映射到正整数(对象不同对应的正整数也不相同)的数据的排序。 
    2.不能处理重复的数据,重复的数据排序后只有一条(如果有这种需求可以在这个算法的基础上修改,给出现次数大于1的数据添加个计数器,然后存入Map中) 
    3.对于数据量极其大的数据处理可能还是比较占用空间,这种情况可配合多通道排序算法解决。

   

 

 

分享到:
评论

相关推荐

    一种适宜于海量数据的快速分组排序算法 (2010年)

    提出了一种高效的适宜于海量数据的无指针分组排序算法,分析了该算法的原理及其时间复杂度和空间复杂度。在最坏情况下的时间复杂度是θ(mn),最好情况和平均情况下的时间复杂度均是θ(nlog(n/mk));在最坏情况下的空间...

    决策树算法在数据挖掘中的研究

    决策树算法在数据挖掘中的研究与应用,是一个深入探讨如何从海量数据中提炼有价值信息的过程。数据挖掘,作为一门从大量、不完整、有噪声、模糊的、随机的实际应用数据中,提取隐藏其中的、人们事先未知的、但又潜在...

    基于分布式协调系统的并行频繁模式增长算法的优化.pdf

    为了应对海量数据集的挑战,研究者们提出了并行频繁模式(PFP)算法,即利用并行处理技术来挖掘频繁模式。这样的算法特别适合于分布式环境,因为它们能够高效地处理大量数据。 分布式协调系统是并行计算的基础设施...

    大数据背景下机器学习算法的综述.pdf

    C4.5算法为目前此领域中较为著名的一类算法,将基于Quinlan所设计的ID3算法予以优化后得到的一种分类决策树算法。决策树为一项预测模型,为对象值、对象属性二者间映射关系的表现方式,树中各节点分别代表不同对象,...

    基于离散粒子群算法的城市生态控制线划定方法研究

    简称DPSO)是一种经过改进的优化算法,它不仅继承了传统粒子群算法(Particle Swarm Optimization,PSO)的优势,而且还能有效解决离散空间优化问题,非常适合用于对离散化海量数据的搜索和处理。粒子群算法本质上是...

    电信设备-一种基于位置信息的散养羊智能监控方法和系统.zip

    5. 云计算:云计算平台用于存储、管理和处理海量的羊群监控数据,提供高效的数据计算和分析能力,同时确保数据的安全性和可用性。 6. 人工智能(AI):AI技术,尤其是机器学习,可以自动学习和识别羊只的行为特征,...

    数据挖掘期末项目大作业1

    本项目通过数据挖掘技术,实现了英语文本的自动分类,为英语学习者提供了智能化的阅读建议,有助于他们更高效地提升英语水平。这充分体现了数据挖掘在教育领域的应用潜力,也为未来类似项目的开发提供了参考。

    基于云计算模式的图书文献个性化推荐技术研究.pdf

    在图书文献自动推荐算法的研究中,本文提出了一种融合主题模型和关联规则的推荐方法。主题模型(如LDA)被用来分析读者信息,挖掘用户潜在感兴趣的主题和相关图书资料。关联规则挖掘则用于发现用户类别与图书资料...

    网络游戏-网络视频客户端弹幕主动屏蔽方法、系统及存储介质.zip

    随着互动性的增强,弹幕功能成为了视频观看时的一大特色,它允许观众实时发表评论,形成一种独特的社交体验。然而,弹幕过多或不适内容有时会干扰到用户的观看体验。本资料主要探讨了网络视频客户端如何实现弹幕的...

    种子发芽 (2).pptx

    数据收集之后,随之而来的便是对海量数据的分析。大数据技术在此环节大显身手,通过分析大量历史数据,科学家能够识别影响种子发芽的关键因素,并优化种子处理和萌发条件。这一过程帮助农业科学家理解种子发芽的最佳...

    大数据和农业物联网技术在智能温室环境控制中的应用——以济南科百智慧农业产业园为例.pdf

    在数据计算和应用方面,物联网系统通过分析采集到的海量数据,利用算法来计算控制逻辑,实现环境的智能控制。科百智慧农业产业园利用这些技术,在暖温带地区成功种植了莲雾、番木瓜、荔枝等原本适应热带气候的水果,...

    农业物联网技术应用-人工智能.pptx

    这些系统依赖于海量数据的训练,通过深度学习等技术模拟人类大脑处理信息的方式,从而在图像识别、语音识别和自然语言处理等领域取得重大突破。然而,弱人工智能缺乏广泛适应性,对于未知的问题处理能力有限。 相对...

    现代农业网络化智能管理系统的研究与设计.rar

    2. 大数据处理:系统收集到的海量数据需要通过大数据技术进行处理和分析。大数据技术能够挖掘出隐藏在大量农业数据中的模式和趋势,为决策提供科学依据。例如,预测病虫害的发生、评估作物生长状况、优化种植结构等...

    行业-电子政务-电力安全作业及运维智能监管系统及方法.zip

    电力安全作业及运维智能监管系统及方法是一种先进的技术解决方案,旨在提升电子政务在电力行业的安全性、效率和可靠性。这一系统利用现代信息技术,如大数据、云计算、物联网和人工智能,实现了对电力作业过程的全面...

    基于机器学习技术的在线疾病诊疗方案倾向性识别研究.pdf

    比如在疾病诊疗中,通过机器学习算法分析海量患者数据,可以迅速地从过去的病例中找到相似案例,为医生提供参考,从而缩短诊断时间,提供更为精准的治疗方案。此外,机器学习还可以协助进行病情监控,预测疾病的复发...

    农业物联网工程技术智能管理系统.zip

    总结来说,农业物联网工程技术智能管理系统是现代农业的一个重要发展方向,它借助物联网、云计算、大数据等先进技术,实现了农业生产的智能化、精细化和高效化,有助于我国农业的现代化转型和可持续发展。

    行业文档-设计装置-物联网智能温室教学模拟系统.zip

    物联网智能温室教学模拟系统是一种结合了现代信息技术与农业实践的创新教学工具,旨在提供一个模拟真实环境的学习平台,帮助学生理解和掌握物联网技术在现代农业中的应用。通过这个系统,学生可以学习到如何利用...

    百度核心志愿者审核机

    【标题】:“百度核心志愿者审核机”是一种专用于协助百度平台进行内容审核的工具,它主要服务于百度的志愿者团队,帮助他们高效、准确地完成网页内容的审查工作。这款工具的核心功能是自动化筛选和评估网页内容,以...

    河道生态治理修复解决方案.docx

    - **定义**: 大数据技术涉及到数据收集、存储、管理和分析等多个环节,旨在从海量数据中挖掘有价值的信息。 - **应用**: 收集河道水质监测数据、垃圾清理记录等多源数据,运用大数据分析方法识别监管薄弱环节,为...

    电子政务-变电站温湿度控制装置.zip

    在这个特定的压缩包文件“电子政务-变电站温湿度控制装置.zip”中,核心内容聚焦于变电站内温湿度控制装置的应用和管理,这是电子政务在电力行业中的一种具体实践。 首先,我们要理解变电站温湿度控制装置的重要性...

Global site tag (gtag.js) - Google Analytics