`
hwy1782
  • 浏览: 149761 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

海量数据搜索算法优化-存储/查询/排序算法

阅读更多


海量数据库的应用,如国家的人口管理系统,户籍档案管理系统,在这样的海量数据库应用中,数据库的存储设计和结构优化(如索引优化)、数据库的查询优化及分页算法尤为重要!

    随着互联网的日益普及,海量信息的增长,网格运算的到来,海量数据存储产品和海量数据存储技术方案的需求更为市场所需。

    同时,实际的海量数据处理,更是涉及很多细节,包括
海量数据存储(物理存储、逻辑存储、海量数据库的备份)、数据采集、海量数据查询(海量数据分页、海量数据排序)、海量数据安全和管理等。


百度、google海量数据搜索算法题解

下面是某同仁在baidu和google的笔试中遇到的两道“百度、google海量数据搜索算法题解”

Google和baidu,人家的数据量在那里摆着,他们的命题思路很明确,不要求具体语言,只要求程序的效率和可行性,题目大多数是关于海量数据搜索的算法问题。

百度、google的海量数据搜索算法题

  1、有1亿个浮点数,请找出其中最大的10000个。提示:假设每个浮点数占4个字节,1亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。

  2、有一篇英文文章(也就是说每个单词之间由空格分隔),请找出“csdn”着个单词出现的次数,要求效率最高,并写出算法的时间级。


Peak Wong的海量数据搜索算法题解

  1、有1亿个浮点数,请找出其中最大的10000个。提示:假设每个浮点数占4个字节,1亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。

  ~~~~~~~~~~~~~

  其实占用内存不算大, 可以接受. 呵呵.

  既然不可以一次读入内存, 那可以这么试试:

  方法1: 读出100w个数据, 找出最大的1w个, 如果这100w数据选择够理想, 那么以这1w个数据里面最小的为基准, 可以过滤掉1亿数据里面99%的数据, 最后就再一次在剩下的100w(1%)里面找出最大的1w个咯~~

  方法2: 分块, 比如100w一个块, 找出最大1w个, 一次下来就剩下100w数据需要找出1w个了.(注意消重,这剩下的100w个数据应该是互不相同的。即每找出一个块里最大的1w个,就应该hash存储。下一个块中若出现了已存储的数据,则不计在此块的top 1w里,这样才能保证最终剩下的100w里面寻找top 1w就接近1亿里面的top 1w。想想:如果每个块的top 1w都基本是重复的,不消重的话,最终的结果有可能就少于1w个。)

  对于上面提到的找出100w个数据里面最大的1w个, 说起来比较罗嗦, 还是说说找到第1w个大的数字的方法:

  用快速排序的方法, 分2堆, 如果大的那堆个数N大于1w个, 继续对大堆快速排序一次分成2堆, 如果大堆个数N小于1w, 就在小的那堆里面快速排序一次, 找第10000-N大的数字; 递归以上过程, 就可以找到第1w大的数. 据说也是STL的search_n()的方法;(更好的一种类似的方法是将这些数以5个为一组,每组通过插入排序找出其中位数,再找出其中位数的中位数,依次递归,找出最终一个中位数x,然后按照x对序列进行快排,且设x是序列的第k大的数,如果要找的是第i大的数,则比较k与i的关系,如果相等,直接返回x,否则如果k>i,则在小的那堆里面继续按照这种方式快排,如果k<i,则在大堆里面找第i-k大的数。)

  参考上面的找出第1w大数字, 相信楼主就可以类似的方法找出前1w大数字了.


  第二个问题,其实很简单。

  假设不区分大小写,由于英文字母有26个,因此,可以将单词映射为数字。csdn被映射成:

  ( 'c '- 'a ')*32*32*32+( 's '- 'a ')*32*32+( 'd '- 'a ')*32+( 'n '- 'a ')

  即:( 'c '- 'a ')*(1 < <15)+( 's '- 'a ')*(1 < <10)+( 'd '- 'a ')*(1 < <5)+( 'n '- 'a ')
因为每位都有0-25,共26个值,所以这里采用了32进制,主要是因为32>26,且32 = 1<<5,利用移位操作使得效率大大提高,不需要再按位比较字符串,通过移位之后比较两英文单词所映射得到的整数值即可(比较一次)。

分享到:
评论

相关推荐

    论文研究-基于PML结构文件的MapReduce算法优化.pdf

    运用PML和EPC编码技术保证了数据存储的完整性,采用快速排序和改进XGrind压缩技术对MapReduce算法进行优化。根据实验可知,优化后MapReduce算法减小了64%的I/O吞吐和45%的CPU耗用,同时使查询数据效率提高了75%,可...

    打败所有黑客的加密算法

    迫切性,大家都在说云计算时代来了,软件不用装了,海量信息可以存储到服务器上,走到哪里就在那里提取,但是你能保证你在服务器上的信息不泄露吗?怎么办?我的建议是,利用上面的加密思想进行加密,任何人想要暴利...

    论文研究-基于MapReduce的无线城市社团发现算法研究.pdf

    对于无线城市数据中社团发现问题,针对已有的团搜索(CS)算法运行过程生成大量重复团、生成结果冗余、算法时间复杂度较高等问题,从优化边存储、预先进行边处理、搜索建团入手,用特殊的二叉树结构存储、权重[K]...

    海量数据处理

    所谓海量数据处理,是指基于海量数据的存储、处理、和操作。正因为数据量太大,所以导致要么无 法在较短时间内迅速解决,要么无法一次性装入内存。 事实上,针对时间问题,可以采用巧妙的算法搭配合适的数据结构(如...

    论文研究-基于Spark无线城市社团发现算法的研究.pdf

    针对已有的社团发现算法存在时间复杂度较高、运行过程会产生大量重复团等问题,引入二叉树的存储结构、权重排序、深度优先遍历的概念,与Spark基于内存计算的特点相结合,提出一种改进的并行化S-T-CS算法。...

    基于划分的海量数据相似重复记录检测

    针对目前社工库存储的海量数据,数据冗余、查询效率低下的质量问题,本文提出了一种有效的基于划分的近邻排序算法.对不同渠道采集、以不同存储方式存储的社工数据进行整合形成能以二维表形式存储的海量数据集,采用...

    基于PML结构文件的MapReduce算法优化 (2016年)

    运用PML和EPC编码技术保证了数据存储的完整性,采用快速排序和改进XGrind压缩技术对MapReduce算法进行优化。根据实验可知,优化后MapReduce算法减小了64%的I/O吞吐和45%的CPU耗用,同时使查询数据效率提高了75%,可...

    大数据算法导论视频教程

    第1课 算法概论,程序=算法+数据结构,时间不允许的算法无任何意义,分而治之,贪心算法,大数据的挑战 第2课 从排序说起,估计算法复杂度 第3课 基本数据结构及应用,栈,队列,链表,哈希函数和哈希表 第4课 ...

    2020 DataFunTalk 年终大会演讲者PPT汇总(58份).zip

    阿里云数据库ClickHouse技术分享暨海量数据分析场景应用实践 贝壳基于Apache Druid 的OLAP 引擎应用实践 滴滴指标体系建设实践分享 陌陌大数据治理与优化实践 熵简-金融资管数据中台体系的探索和实践 8.数据产品 ...

    大数据下的数据分析平台架构.pdf

    ⼤数据下的数据分析平台架构 ⼤数据下的数据分析平台架构 转载: 随着互联⽹、移动互联⽹和物联⽹的发展,谁也⽆法否认,我们已经切实地迎来了⼀个海量数据的时代,数据调查公司IDC预计2011年的数 据总量将达到1.8万...

    采用k-均值聚类算法的资源搜索模型研究 (2012年)

    针对当前海量信息存储对等网络系统中资源搜索技术效率较低的问题,提出了一种采用k- 均值聚类分析的高效搜索模型.该模型利用资源描述框架(RDF )描述的元数据进行聚类分析,使得资源的搜索由全局变为局部,从而有效地...

    FreeBSD操作系统设计与实现

    7.1.2 FreeBSD海量存储I/O子系统的结构 7.1.3 设备的命名和访问 7.2 GEOM层 7.2.1 术语和拓扑规则 7.2.2 改变拓扑 7.2.3 运行 7.2.4 拓扑的灵活性 7.3 CAM层 7.3.1 SCSI子系统 7.3.2 I/O请求通过CAM子系统的路径 7.4...

    发挥医疗大数据的价值.pdf

    医院大数据分析平台的构建 医院信息应用系统在日常医疗和管理中积累了 大量历史数据,但各部门人员在日常数据录入和维 护中,只是通过统计和排序对数据进行简单的功能 操作,获得一些表面、浅显、价值不高的结果,...

    新版Hadoop视频教程 段海涛老师Hadoop八天完全攻克Hadoop视频教程 Hadoop开发

    04-hadoop对海量数据处理的解决思路.avi 05-hadoop版本选择和伪分布式安装.avi 06-hadoop版本选择和伪分布式安装2.avi 07-hdfs&mapreduce;测试.avi 08-hdfs的实现机制初始.avi 09-hdfs的shell操作.avi 10-...

    超光谱图像的三维小波嵌入零块压缩编码

    超光谱图像作为一种三维图像,其海量的数据导致在有限带宽信道上传输和存储非常困难,必须对它进行有效的压缩编码.提出了一种基于非对称三维小波变换(3D wavelet transform,简称3DWT)和三维集合块分裂的超光谱遥感图像...

    海量数据库查询语句

    以下代码说明了我们实例中数据库的“红头文件”一表的部分数据结构: CREATE TABLE [dbo].[TGongwen] ( –TGongwen是红头文件表名 [Gid] [int] IDENTITY (1, 1) NOT NULL ,–本表的id号,也是主键 ...

    《认识大数据》教学设计.docx

    交通实时监测数据分散存放在多台独立的计算机中,这就解决了海量数据存储的难题; 多台计算机分工合作完成数据的检索和处理,能确保及时完成分析任务 二、数据分析的一般过程 数据分析通常有六个步骤: 明确目的和...

Global site tag (gtag.js) - Google Analytics