Top k

-- 相对多的数据量下 找出前100小、大的数据

100亿 整数 找出最大的前1000个

一个int 4字节 32位

400 亿 字节 B

4000万 kb

4 万mb

40 Gb

• 冒泡

  • 40g内存

• 分治--大化小

  • 分成10份
  • 每个机器处理一份
  • 前1000 大/小
  • 合并10台机器结果
  • 前1000大、小

• 一部分一部分的将 数据处理

  • 做个标杆 构成100个大小的数组 On*m -> On*logm
  • 有序数组
  • 大顶堆、小顶堆
  • nlogm m= 100 n=100亿

• int 【】 result =new int【1000】；

  while(文件没到头)｛

  取出4m数据

  ​ for(4m数据)｛

  ​

  ​ ｝

  ｝

• redis hyperloglog

100亿 找出出现次数最多1000个数字

1000个文件 hash求余

123.txt

123 54

1123 556

11123 3223

先统计并分治

nlogm

10g 的日志文件 找出出现次数最多的url

10g的日志文件 找出出现次数最多的ip地址

100亿整数 给定你一个数 尽可能快的判定有没有出现过

bitmap

01010101011010101000011111111111111111111111111111

1011

int[0] 前32数字

int【1】=3 32-63

target

长度是2^32的位数组 bit 0 1

2^29B

2^19KB

2^9Mb

500MB

int 数组 正数 最大值不超过1024 自己尝试构建一个 bitmap 来存储并检查

set 设置这个值

check 检查这个值有没有在集合里边