大文件排序求频率TOP问题

• 问题：

有一个1G大小的一个文件，里面每一行是一个词，
词的大小不超过16字节，内存限制大小是10M。返回频数最高的100个词。

• 该类型问题分析（分而治之）：

1、找出一种分类方式（找到散列方式或散列函数）；
2、特殊情况考虑，防止分类后单类文件过大问题；
3、对分类的文件进行归并。

• 本题解决思路（分而治之）：

1、分类方式（尽可能保证相同类型在一个文件中）：
按照26个英文字母及字母长度分类；
例：文件名：a4，b5，c8....
字母小于4个为一组，大于等于4小于等于5为一组，大于5为一组，工三组。
最多产生文件个数：26乘以3共78个。
2、假设一个文件多大；首先按长度再次分割，
再按第二、三.....个英文字母再次分割；假设都相同，单词相同。
3、结果（归并）。

• Java代码（未优化代码）：

package com.wqq.study.demo.service.bigdata;

import java.io.*;
import java.util.*;

/**
 * @ClassName: BigData
 * @Description:
 *
 *
 * java内存大小计算器
 * //计算指定对象及其引用树上的所有对象的综合大小，单位字节
 * long RamUsageEstimator.sizeOf(Object obj)
 * //计算指定对象本身在堆空间的大小，单位字节
 * long RamUsageEstimator.shallowSizeOf(Object obj)
 * //计算指定对象及其引用树上的所有对象的综合大小，返回可读的结果，如：2KB
 * String RamUsageEstimator.humanSizeOf(Object obj)
 * <dependency>
 *             <groupId>org.apache.lucene</groupId>
 *             <artifactId>lucene-core</artifactId>
 *             <version>4.0.0</version>
 *         </dependency>
 * @Author: wqq
 * @create: 2019/10/28
 **/
public class BigData2 {
    /**
     * 大文件位置
     */
    public  static  String BIG_FILE_NAME="C:\\Users\\wqq\\Desktop\\bigdata\\bigdata.txt";
    public  static  String SORT_FILE_NAME="C:\\Users\\wqq\\Desktop\\bigdata\\bigdatasort.txt";

    /**
     * 100
     */
    public  static  Integer LIMIT=100;

    /**
     * 换行符
     */
    public static String LINE_SEPARATOR="\r\n";


    public static void main(String[] args) throws  Exception{
        BigData2 bigData=new BigData2();
        //生成大文件
        //bigData.StringBufferDemo();
        List<Map.Entry<String,Integer>> return100=separateFile();
        System.out.println("return100:"+return100.size());
    }

    /**
     * 大文件分片排序
     * @return
     */
    private static List<Map.Entry<String,Integer>> separateFile() {
        Set<String> fileNameList = new TreeSet<>();
        Map<String,FileWriter > map = new HashMap<>();
        try (BufferedReader reader = new BufferedReader(new FileReader(BIG_FILE_NAME))) {
            String line="";
            while ((line = reader.readLine()) != null) {
                line=line.toLowerCase();
                int len=line.length();
                String fileTemp = proFileName(line);
                if(map.containsKey(fileTemp)){
                    FileWriter tmpWriterTemp= map.get(fileTemp);
                    tmpWriterTemp.write(line+LINE_SEPARATOR);
                }else {
                    try {
                        FileWriter tmpWriter = new FileWriter(fileTemp);
                        map.put(fileTemp,tmpWriter);
                        tmpWriter.write(line+LINE_SEPARATOR);
                    }catch (Exception e){
                        e.printStackTrace();
                    }
                }
                fileNameList.add(fileTemp);
            }
            //统计出现频率最高的词汇
             return getSort(fileNameList);
        } catch (Exception e) {
            e.printStackTrace();
        }finally {
            //文件输入流关闭
            for (String reader : map.keySet()) {
                try {
                    map.get(reader).close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return null;
    }

    /**
     *  生成散列文件名，自己优化
     * @param line 读取文件每行
     * @return
     */
    private static String proFileName(String line) {
        int len=line.length();
        StringBuffer stringBuffer=new StringBuffer();
        stringBuffer.append("C:\\Users\\wqq\\Desktop\\bigdata\\");
        if(len<4){
            if(len>0){
                stringBuffer.append("temp"+line.substring(0,1)+"3");
            }else{
                stringBuffer.append("temp"+"3");
            }
        }else if(3<len &&len<5){
            stringBuffer.append("temp"+line.substring(0,1)+"4");
        }else if(4<len &&len<6){
            stringBuffer.append("temp"+line.substring(0,1)+"5");
        }else{
            stringBuffer.append("temp"+line.substring(0,1)+"6");
        }
        stringBuffer.append(".txt");
        return stringBuffer.toString();
    }


    /**
     * 排序 注意：特殊情况自己来补充，比如取前100的时候，120的单词频率和100一样，自己优化
     * @param fileNameList
     * @return
     * @throws Exception
     */
    public static List<Map.Entry<String,Integer>> getSort(Set<String> fileNameList) throws Exception{
        List<Map.Entry<String,Integer>> entrysReturn=new ArrayList<>();
        for(String fileNameSet:fileNameList){
            Map<String,Integer> countMap=new HashMap<>();
            try (BufferedReader readerSet = new BufferedReader(new FileReader(fileNameSet))) {
                String lineSet="";
                while ((lineSet = readerSet.readLine()) != null) {
                    if(countMap.containsKey(lineSet)){
                        int value=countMap.get(lineSet);
                        value++;
                        countMap.put(lineSet,value);
                    }else {
                        countMap.put(lineSet,1);
                    }
                }
            }
            List<Map.Entry<String,Integer>> entrys=new ArrayList<>(countMap.entrySet());
            Collections.sort(entrys, new Comparator<Map.Entry<String, Integer>>() {
                // 升序排序
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                    return o2.getValue().compareTo(o1.getValue());
                }
            });
            if(entrys.size()>LIMIT){
                entrysReturn.addAll(entrys.subList(0,LIMIT));
            }else{
                entrysReturn.addAll(entrys);
            }
        }
        Collections.sort(entrysReturn, new Comparator<Map.Entry<String, Integer>>() {
            // 升序排序
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        if(entrysReturn.size()>LIMIT){
            return entrysReturn.subList(0,LIMIT);
        }else{
            return entrysReturn;
        }
    }




    /*生成数据方法start*/

    /**
     * 随机获取长度为12~20的大小写字母混杂的“单词”
     */
    private String randomWord() {
        // 12~20长度，包含12及20
        int length = 2 + (int) (Math.random() * 5);
        String word = "";
        for (int i = 0; i < length; i++) {
            word += (char) randomChar();
        }
        return word;
    }
    /**
     * 随机获取'a'~'z' 和 'A'~ 'Z'中的任一字符
     *
     * 'A'~ 'Z'对应ASCII值：65~90
     *
     * 'a'~'z'对应ASCII值：97~122
     *
     * @return
     */
    private byte randomChar() {
        // 0<= Math.random()< 1
        int flag = (int) (Math.random() * 2);// 0小写字母1大写字母
        byte resultBt;
        if (flag == 0) {
            byte bt = (byte) (Math.random() * 26);// 0 <= bt < 26
            resultBt = (byte) (65 + bt);
        } else {
            byte bt = (byte) (Math.random() * 26);// 0 <= bt < 26
            resultBt = (byte) (97 + bt);
        }
        return resultBt;
    }
    public void StringBufferDemo() throws IOException{
        File file=new File("C:\\Users\\wqq\\Desktop\\bigdata\\bigdata.txt");
        if(!file.exists())
            file.createNewFile();
        FileOutputStream out=new FileOutputStream(file,true);
        BigData2 bigData=new BigData2();;
        for(int i=0;i<100000000;i++){
            StringBuffer sb=new StringBuffer();
            sb.append(bigData.randomWord());
            sb.append("\r\n");
            out.write(sb.toString().getBytes("utf-8"));
        }
        out.close();
    }
}