大文件排序有关问题（字符串）实际项目
大文件排序问题（字符串）实际项目
现在有一个文件中有200M个字符串，每个字符串长1000，已知绝大多数的字符串都可以由前30位来识别出来（就是前30位不一样），只有少数几十对字符串是前30位都一样的。
现在问题是如何对这么多字符串进行排序？
第一次接触大数据量排序，希望大家指点指点。
------解决方案--------------------
to #8,以下都是我个人看法，不一定是最好的方法。
因为内存速度远高于磁盘，而读磁盘又要比写磁盘快。所以有两个原则：
1> 尽量用内存
2> 尽量少写磁盘
对于大文件排序，一般比较通用的做法是：
1> 设计N个桶，桶之间是有大小关系的（例如，可以根据第一个字符的不同，分成8个桶）。顺序读一次文件，按桶将文件分割成小文件，设计桶的原则就是判断条件简单，分割数据比较平均（不平均也没关系，但是一定要保证每个小文件能够一次在内存排好序）。
2> 按照桶的顺序，每次读入一个小文件，排序，然后追加到结果文件的末尾。
这样做的代价是，读两次全部数据，写两次全部数据
对于这道题而言，每个数据都是一个1000长度的字符串，如果只用原始字符串，那么有两个缺点，一是读入后占用内存大，二是排序需要比较的时间长。所以根据#4的说法，需要将数据压缩一下，因为可能出现的字符只有8种，那么就分别用000,001,002……111对这些字符编码，可以使长度大大缩短。这样内存能够容纳的数据就大大增加了。
由于前提条件是，大部分都可以通过前30个字符区分，那么就没有必要对整个1000个长度的字符串编码了，只需要对前30个字符编码，编码后的数据（90bit）作为这个字符串的特征值进行比较。而由于这个特征值无法逆向得到原字符串，所以需要用一个数据标识这个特征值对应的是原来哪个字符串，这就是索引的作用了，索引代表的是这个特征值在原始文件中对应第几个字符串。
排序是就按照特征值的大小进行排序，这样排好序后，就可以通过特征值对应的索引，去原始文件中取原始字符串了。
所以针对这道题，就可以这样做：
1 顺序读入原始文件每个字符串的前30字节，计算好（索引，特征值），放入相应的桶，例如按第一个字符的不同分成8个桶，每当桶的数据达到一定数量，就将（索引，特征值）写入该桶对应的文件。<这一步相当于读取了原始数据3%的量，写入了3%的量，之所以不是读一条就写一条，是因为磁盘文件每次存储大块的数据会比零碎的存储节省时间>
2 从小到大，每次读取一个桶的文件，按照特征值排序，排好序后，按照特征值对应的索引，依次读取原始文件对应的字符串（例如，索引是100，那么就应该跳到该文件的1000*100的位置去读），然后写入目标文件。
<这一步读取了全部原始记录，也写入了全部原始记录>
3 针对有部分重复的问题，在第2步需要做一下特殊处理，就是排好序后，如果发现当前特征值和下一条不同，才直接写入目标文件，否则，需要将后面所有和当前特征值相同的字符串都读出来，做一个全面的排序，然后再写入目标文件。
现在有一个文件中有200M个字符串，每个字符串长1000，已知绝大多数的字符串都可以由前30位来识别出来（就是前30位不一样），只有少数几十对字符串是前30位都一样的。
现在问题是如何对这么多字符串进行排序？
第一次接触大数据量排序，希望大家指点指点。
------解决方案--------------------
to #8,以下都是我个人看法，不一定是最好的方法。
因为内存速度远高于磁盘，而读磁盘又要比写磁盘快。所以有两个原则：
1> 尽量用内存
2> 尽量少写磁盘
对于大文件排序，一般比较通用的做法是：
1> 设计N个桶，桶之间是有大小关系的（例如，可以根据第一个字符的不同，分成8个桶）。顺序读一次文件，按桶将文件分割成小文件，设计桶的原则就是判断条件简单，分割数据比较平均（不平均也没关系，但是一定要保证每个小文件能够一次在内存排好序）。
2> 按照桶的顺序，每次读入一个小文件，排序，然后追加到结果文件的末尾。
这样做的代价是，读两次全部数据，写两次全部数据
对于这道题而言，每个数据都是一个1000长度的字符串，如果只用原始字符串，那么有两个缺点，一是读入后占用内存大，二是排序需要比较的时间长。所以根据#4的说法，需要将数据压缩一下，因为可能出现的字符只有8种，那么就分别用000,001,002……111对这些字符编码，可以使长度大大缩短。这样内存能够容纳的数据就大大增加了。
由于前提条件是，大部分都可以通过前30个字符区分，那么就没有必要对整个1000个长度的字符串编码了，只需要对前30个字符编码，编码后的数据（90bit）作为这个字符串的特征值进行比较。而由于这个特征值无法逆向得到原字符串，所以需要用一个数据标识这个特征值对应的是原来哪个字符串，这就是索引的作用了，索引代表的是这个特征值在原始文件中对应第几个字符串。
排序是就按照特征值的大小进行排序，这样排好序后，就可以通过特征值对应的索引，去原始文件中取原始字符串了。
所以针对这道题，就可以这样做：
1 顺序读入原始文件每个字符串的前30字节，计算好（索引，特征值），放入相应的桶，例如按第一个字符的不同分成8个桶，每当桶的数据达到一定数量，就将（索引，特征值）写入该桶对应的文件。<这一步相当于读取了原始数据3%的量，写入了3%的量，之所以不是读一条就写一条，是因为磁盘文件每次存储大块的数据会比零碎的存储节省时间>
2 从小到大，每次读取一个桶的文件，按照特征值排序，排好序后，按照特征值对应的索引，依次读取原始文件对应的字符串（例如，索引是100，那么就应该跳到该文件的1000*100的位置去读），然后写入目标文件。
<这一步读取了全部原始记录，也写入了全部原始记录>
3 针对有部分重复的问题，在第2步需要做一下特殊处理，就是排好序后，如果发现当前特征值和下一条不同，才直接写入目标文件，否则，需要将后面所有和当前特征值相同的字符串都读出来，做一个全面的排序，然后再写入目标文件。