• 注册
  • 后端开发博客 后端开发博客 关注:0 内容:2357

    几个常见的大数据查找问题

  • 查看作者
  • 打赏作者
  • 当前位置: 职业司 > 后端开发 > 后端开发博客 > 正文
    • 后端开发博客
    • 问题分析

      • 对于从较大的数据集中查找的问题(内存无法全部容纳)
        • 首先考虑的就应该是用 hash 函数,加上固定的区域,将其划分成为多个小文件,对于小文件就可以将其全部放入到内存中进行查找

      1 如何从大量的URL中查找到相同的URL?

      • 通过 Hash(URL) % 1000,将其划分成为1000个小文件,而后将每一个小文件拉到内存中进行判断是否存在相同的URL,如果小文件还是太大了,可以尝试将小文件再次进行 hash 运算

      2 如何从大量数据中找到高频词?

      • 同样通过 Hash(词语) % 1000 ,划分成为 1000个小文件,和上述方式一样

      3 如何找出访问百度网站最多的IP?

      • 同样是一个找相同的方式,同样采用 hash 进行运算,划分成为小文件,
      • 由于查找的是最大的,所以只需要找到每一个小文件中最大的,然后再比较所有小文件中最大的就可以了

      4 如何再大量的数据中找到不重复的整数?

      方法1 hash

      • 同样是找相同和找不同的问题,首先考虑的就是 hash 拆分的方式

      方法2 位图

      • 对于数字类问题,有一种比较巧妙的解决方案就是位图法
      • 创建一个非常大的bit 数组,用每一个bit位来定义每个数字是否存在

      5 如何从大量数据中判断一个数是否存在

      和问题4 是同一种类型的问题,采用位图法或者是 分治

      6 如何查询最热门的查询串

      方法1 hash

      • 查询相同字符串的问题,同样可以考虑用 hash 进行分隔后,再进行进一步的判断

      方法2 前缀树

      • 利用前缀树来保存每一个字母

      7 统计不同电话号码的个数

      • 本质还是求相同的问题
      • 可以采用位图法,进行判断

      从 5 亿个数字中找到中位数

      • 这种不是找相同找不同的问题

      方法1 双堆法

      双堆法需要将5 亿个数字全部提前到内存中,需要本身内存较大

      方法2 分治

      可以通过 数字每一个位是 0 还是 1 进行划分,划分成为 2 个较小的区间
      如果第一位是0 的 有 4 亿个 第一位是 1 的有 1 亿个,说明中位数的第一位是0 ,一致分治下去

      有 10 个文件,每个文件大小为 1G,每个文件的每一行存放的都是用户的 query,每个文件的 query 都可能重复。要求按照 query 的频度排序。

      -还是找相同找不同的问题,直接分治理

      从一个较大的数据集中找到排名前500的数

      • topK 问题,建立一个 大小是 K 的堆,把所有的数都往里面丢一遍,留下最后堆里面的500个

      小结

      • 大体的方向,都是分治法进行处理,把大文件变小文件
      • 对于数字类问题,可以考虑以下用 位图法和01分治法
      • 对于TopK 问题,可以考虑下用堆的方式
      • 对于字符串问题,可以考虑下用前缀树

      参考

      • github.com/doocs/advan…

      请登录之后再进行评论

      登录

      手机阅读天地(APP)

      • 微信公众号
      • 微信小程序
      • 安卓APP
      手机浏览,惊喜多多
      匿名树洞,说我想说!
      问答悬赏,VIP可见!
      密码可见,回复可见!
      即时聊天、群聊互动!
      宠物孵化,赠送礼物!
      动态像框,专属头衔!
      挑战/抽奖,金币送不停!
      赶紧体会下,不会让你失望!
    • 实时动态
    • 签到
    • 做任务
    • 发表内容
    • 偏好设置
    • 到底部
    • 帖子间隔 侧栏位置:
    • 还没有账号?点这里立即注册