题目：在一个2T的文本文件，每一行都是一个数字，且都不相同，请用一台256M内存的单机服务器对这个乱序的文本文件，进行全排序
-
读取一条数据A，如果A的值在[0, 1000000)之间，则将A保存到file0文件中；如果A的值在[1000000, 2000000)之间，则将A保存到file1文件中。根据A的取值范围不同，被划分到不同的文件中，合计10000个小文件
-
按步骤1进行文件的遍历，处理剩余的每条数据。这样2T的文件被分割成10000个小文件，各个小文件之间的数据是外部有序的，每个小文件内部是乱序的
-
依次处理每个小文件，对每个小文件内部的数据进行排序
-
一次读取128M数据，进行排序，保存到file0文件中
-
第二次读取128M数据，进行排序，保存到file1文件中
-
依次类推，数据被保存到10000个小文件中。在每个小文件内部数据是有序的，各个小文件之间的数据是无序的
-
采用
归并排序
，对各个文件之间的数据进行排序
归并排序
：
-
将file0文件的第一个数取出来，赋值给变量X0，file1文件的第一个数取出来，赋值给变量X2，依次类推，将file9999文件的第一个数取出来，赋值给变量X9999
-
求出X0 ~ X9999之间的最小值，将其保存到文件file_v_0中
-
再从fileN中取出值赋给XN, 重复步骤2
-
重复步骤3，如果file_v_0小文件的大小，超过128M，则将数据保存到file_v_1小文件中，依次类推。最后保存的小文件为file_v_9999
目录1. 查找大文件相同两行2. 大文件全排序1. 查找大文件相同两行题目：有一个2T的文本文件，只存在2行相同的数据，请用一台256M内存的单机服务器，找出这相同的2行数据解决步骤：读取一条数据A，求A的hashcode，然后取模，即X = a.hashcode % 10000，X的范围为0 ~ 9999，将数据A保存到fileX文件中按步骤1进行文件的遍历，处理剩余的每条数据。这样2T的文件被分割成10000个小文件，但相同的2行数据肯定在同一个小文件中依次处理每个小文件，找出在一个小文件
类似问题：已知某个
文件
内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
8位最多99 999 999，大概需要99 999 999个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M
左右
的内存表示了所有的8位数的电话）
【2】给定a、.
日志数据是最常见的一种海量数据，以拥有大量用户群体的电商平台为例，双11大促活动期间，它们可能每小时的日志数量达到百亿规模，海量的日志数据暴增，随之给技术团队带来严峻的挑战。本文将从海量日志系统在优化、部署、监控方向如何更适应业务的需求入手，重点从多种日志系统的架构设计对比；后续调优过程：横向扩展与纵向扩展，分集群，数据
分治
，重写数据链路等实际现象与问题展开。有过项目开发经验的朋友都知道：从平台的最初搭建到实现核心业务，都需要有日志平台为各种业务保驾护航。如上图所示，对于一个简单的日志应用场景，通常会准备master/slave
两个
应用。我们只需运
行
一个Shell脚本，便可查看是否存在错误信息
看完这个问题，不妨我们来思考一下如何实现...
一.解决方案
首先实现这个问题我们的第一想到的最笨的解决方案就是对每一
行
都与
文件
中后面所有的
行
进
行
比较，这种方式的时间复杂度很高为O(n^2)...
那么有没有更好的解决方案呢...
题目描述：
1T的
文件
，使用
行
储存，其中有唯一的
两行
重复，目前只有一台计算机，内存不足以容纳1T
文件
，比如是256M,128G,问如何使用单机寻找出这
两行
数据?
分析解答：
方法：
分治
法。
解题思路：对于
大数据
相关的算法题，
分治
法是一个非常好的方法。针对这一题来说，主要思路为：因为
文件
是按
行
储存的，我们可以一
行
一
行
的读取
文件
，当每读取到一
行
，取它的hashcode，可以根据实际可用内存的情况，确定...
第一种方式：使用grep
以从file1.txt和file2.txt中抽离出
相同
部分为例，注意:
文件
都是已经排好序的
grep -wf file1.txt file2.txt > same.txt
第二种方式：使用 word
在Word中本身就有这样一个功能，可以自动帮助我们检测处修改痕迹，删除痕迹，以及添加内容等等，非常方便。进入【审阅】-【比较】-【比较】放入俩个
文件
稍等一会便会出来结果
一般而言，标题含有“秒杀”，“99%”，“史上最
全
/最强”等词汇的往往都脱不了哗众取宠之嫌，但进一步来讲，如果读者读罢此文，却无任何收获，那么，我也甘愿背负这样的罪名，:-)，同时，此文可以看做是对这篇文章：十道海量数据处理面试题与十个方法大总结的一般抽象性总结。
毕竟受文章和理论之限，本文将摒弃绝大部分的细节，只谈方法/模式论，且注重用最通俗最直白的语言阐述相关问
使用位图方法bitmap，
先将一个
文件
中的数据存入bitmap中，然后将第二个
文件
中的数据和bitmap对照，如果bitmap中存在就说明
相同
。
这样就
找到
了所有的
两个
文件
中
相同
的数据。
哈希法，通过哈希值来对
文件
中的数据分到多个
文件
中，然后
两个
文件
分解完的
文件
中相对应的再进
行
数据比较，
确定是否有
相同
的数据，如果有就输出。
实现大整数乘法的一种常用算法是
分治
算法。这种算法将
两个
大整数分别拆分成
两个
小整数，然后递归地计算出它们的积，最终合并得到最终结果。以下是Python实现：
```python
def big_int_mult(x, y):
大整数乘法
:param x: 大整数
:param y: 大整数
:return: x * y 的结果
# 如果x或y只有一位，则直接返回它们的乘积
if len(x) == 1 or len(y) == 1:
return str(int(x) * int(y))
# 计算x和y的长度
n = max(len(x), len(y))
# 将x和y分成两段
mid = n // 2
x_left, x_right = x[:-mid], x[-mid:]
y_left, y_right = y[:-mid], y[-mid:]
# 递归计算x_left * y_left, x_right * y_right和(x_left + x_right) * (y_left + y_right)
p1 = big_int_mult(x_left, y_left)
p2 = big_int_mult(x_right, y_right)
p3 = big_int_mult(str(int(x_left) + int(x_right)), str(int(y_left) + int(y_right)))
# 计算结果
return str(
int(p1) * 10**(2*mid) + (int(p3) - int(p1) - int(p2)) * 10**mid + int(p2)
该算法的时间复杂度为O(n^log2(3))，其中n为
两个
大整数的长度。该算法的空间复杂度为O(n^log2(3))。
