Chinaunix首页 | 论坛 | 博客
  • 博客访问: 844239
  • 博文数量: 489
  • 博客积分: 475
  • 博客等级: 下士
  • 技术积分: 3087
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-08 16:28
文章分类

全部博文(489)

文章存档

2013年(7)

2012年(301)

2011年(181)

分类:

2011-12-22 22:10:12

原文地址:海量数据处理(3) 作者:cssjtuer

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

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

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

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


百度、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个, 说起来比较罗嗦, 还是说说找到第1w个大的数字的方法:

  用快速排序的方法, 分2堆, 如果大的那堆个数N大于1w个, 继续对大堆快速排序一次分成2堆, 如果大堆个数N小于1w, 就在小的那堆里面快速排序一次, 找第10000-N大的数字; 递归以上过程, 就可以找到第1w大的数. 据说也是STL的search_n()的方法;

  参考上面的找出第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 ')
阅读(829) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~