网站正在建设中 色app下载推广

1.50 亿数据如何去重&排序？

如此大的数据集进行去重（例如50亿数据条目），我们需要考虑内存和存储空间的限制，同时还需要有一个高效的算法。一般来说，这样的数据量无法直接载入内存进行处理，因此需要采用磁盘存储和分布式处理的技术。主要有以下几种思路：

外部排序：
将数据分为多个批次，每个可以加载到内存中。
对每一批数据进行排序和去重，然后存回磁盘。
对所有排序且去重后的批次进行归并排序，同时去重。

哈希切分（Hash partitioning）:
使用哈希函数将数据分配到不同的桶（Bucket）或文件中，确保相同的数据项会落到同一个桶里。
对每个桶的数据进行内存中去重操作。对所有桶进行并行处理以提升效率，并最终合并结果。是一种分治思想。

【题目1】给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

【答案】按照每个url64字节来算，每个文件有50亿个url，那么每个文件大小为5G*64=320G（按照1000换算10亿字节=1GB）。320G远远超出内存限定的4G，所以不能将其全部加载到内存中来进行处理，需要采用分而治之的方法进行处理。逐行读取文件a，采用hash函数：Hash(url)%1000将url分割到1000个小文件中。那么理想情况下每个小文件的大小大约为300M左右。再以相同的方法对大文件b进行相同的操作再得到1000个小文件，求每对小文件中的相同url，首先将每对对小文件中较小的那个的url放到HashSet结构中，然后遍历对应这对小文件中的另一个文件，看其是否存才刚刚构建的HashSet中，如果存在说明是一样的url，将这url直接存到结果文件就ok了。

【题目2】海量日志数据，提取出某日访问百度次数最多的那个IP。

【答案】一样的操作，每个小文件获得出现次数之后，再将所有文件汇总。

【题目3】有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
【题目4】有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

分布式处理：
如果单机处理能力有限，可以使用分布式计算框架如Hadoop或Spark。
在这样的系统中可以使用MapReduce或Spark的RDD/DataFrame转化操作来进行分布式去重。 

Bitmap方法：

每一位表示一个数据，此方法适用于非负整数数据，尤其是范围较小的情况。如果数据范围过大，可以结合哈希切分使用。