首页 > > > 大数据处理.doc

大数据处理.doc

大数据处理.doc

上传者: gaowei 2012-05-10 评分1 评论0 下载52 收藏10 阅读量229 暂无简介 简介 举报

简介:本文档为《大数据处理doc》,可适用于高等教育领域,主题内容包含给定a、b两个文件各存放亿个url每个url各占字节内存限制是G让你找出a、b文件共同的url?方案:可以估计每个文件安的大小为G=G远远大于内存限符等。

1. 给定 a b 两个文件,各存放 50 亿个 url ,每个 url 各占 64 字节,内存限制 4G ,让你找出 a b 文件共同的 url 方案 1 :可以估计每个文件安的大小为 50G × 64=320G ,远远大于内存限制的 4G 。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。 s 遍历文件 a ,对每个 url 求取,然后根据所取得的值将 url 分别存储到 1000 个小文件(记为)中。这样每个小文件的大约为 300M s 遍历文件 b ,采取和 a 相同的方式将 url 分别存储到 1000 各小文件(记为)。 这样处理后,所有可能相同的 url 都在对应的小文件()中,不对应的小文件不可能 有相同的 url 。然后我们只要求出 1000 对小文件中相同的 url 即可。 s 求每对小文件中相同的 url 时,可以把其中一个小文件的 url 存储到 hash_set 中。然后遍历另一个小文件的每个 url ,看其是否在刚才构建的 hash_set 中,如果是, 那么就是共同的 url ,存到文件里面就可以了。 方案 2 :如果允许有一定的错误率,可以使用 Bloomfilter 4G 内存大概可以表 340 亿 bit 。将其中一个文件中的 url 使用 Bloomfilter 映射为这 340 亿 bit ,然 后挨个读取另外一个文件的 url ,检查是否与 Bloomfilter ,如果是,那么该 url 应该 是共同的 url (注意会有一定的错误率)。 2. 10 个文件,每个文件 1G ,每个文件的每一行存放的都是用户的 query 每个文件的 query 都可能重复。要求你按照 query 的频度排序。 方案 1 s 顺序读取 10 个文件,按照 hash(query)%10 的结果将 query 写入到另外 10 个文件(记为)中。这样新生成的文件每个的大小大约也 1G (假设 hash 函数是随 机的)。

第1页

该用户的其他资料

  • 名称/格式
  • 评分
  • 下载次数
  • 资料大小
  • 上传时间

用户评论

0/200
    暂无评论
上传我的资料

相关资料

资料评价:

/ 8
所需积分:0 立即下载
返回
顶部
举报
资料
关闭

温馨提示

感谢您对爱问共享资料的支持,精彩活动将尽快为您呈现,敬请期待!