登录 注册

【经验】大文件排序实验—代码

针对超出内存大小的大文件排序的简单算法和性能实验
时间:2016-07-24 15:04:48 作者:Mr.d


实验场景

        阿里云服务器配置:单核CPU、1G内存

实验代码及过程

        首先得先有一个超过我服务器内存的文件,那就随机生成一个吧,写一个简单的循环循环99999999次,每一行都是一个数字,数字是随机数,随机数的范围是0  -(999999999*2),在我自己的电脑上测试过,99999999条数据生成的文件大概在1个G多点,那么肯定不能一次性写到文件里了,只能分批往文件里去写了(这里是往文件尾部追加数据,网上有很多代码),那就这么做吧。

            public static void main(String[] args) {
		
		String path = "/home/things/data2.txt";
		List list = new ArrayList();
		for (int i = 0; i 0 && i % 1000 == 0) {
				System.out.println("start to append file.....   index="+i);
				FileUtils.appendFile(path, list);
				list = null;
				
				System.out.println("finish to append file.....   index="+i);
			}
			if (list == null)
				list = new ArrayList();
			
			int ran = (int)(Math.random() * (99999999 * 2));
			list.add(ran+"");
		}
		
		System.out.println("。。。。finish。。。。");
		
	}


        第二步要对文件进行分割,对文件的分割也只能是一行行的读出来,然后根据行数进行分割(这里不知道有多少行,所以设定一个固定的阈值,触发阈值则进行分割),这里创建了一个FileBean的类,这个类里设置和初始化时获取File对象和Scanner对象(从网上查的,使用scanner对象对文件以行为单位的读取效率较高),并提供可以获取文件每行的方法。

public class FileBean {

	private String filePath;
	private File file;
	private Scanner scanner;
	private FileBean(){};
	
	public FileBean(String filePath){
		this.filePath = filePath;
		this.file = new File(filePath);
		try {
			scanner = new Scanner(file, "utf-8");
		} catch (Exception e) {
			e.printStackTrace();
		}
		
	}
	
	public int readLineInt(){
		return StringUtil.toInteger(this.readLine(), -1);
	}
	
	public String readLine(){
		if (scanner == null)
			return null;
		
		if (scanner.hasNextLine())
			return scanner.nextLine();
		return null;
	}
	
	public void destory(){
		if (scanner != null)
			scanner.close();
	}
	
}


        这里设置分割的长度为10W行,因为在测试的时候试验过,10W行的数字生成文件,大小大概在1M左右,这里设置了10W为阈值(这里可以随意设置,根据服务器的情况设置),每次读取10W行,并对文件进行一个排序,最后生成一个新的文件,新的文件会有一个标识,这个标识就是分割的次数的次数

        public static int splitSortFile(String path) {
		long time = System.currentTimeMillis();
		FileBean baseFile = new FileBean(path);
		int valueIndex = 0;
		int groupIndex = 0;
		List intList = null;
		while(true) {
			
			if (valueIndex > 0 && valueIndex % GOUPR_LENGTH == 0) {
				long startTime = System.currentTimeMillis();
				createNewFileSync(intList,groupIndex);
				System.out.println("create new file finish  file_index:"+groupIndex+"  cost:"+(System.currentTimeMillis() - startTime));
				intList = null;
				groupIndex++;
			}
			
			int value = baseFile.readLineInt();
			if (value == -1){
				break;
			}
			
			if (intList == null)
				intList = new ArrayList();
			
			intList.add(value);
			valueIndex++;
		}
		
		createNewFileSync(intList,groupIndex);
		groupIndex++;
		intList = null;
		
		System.out.println(".....finish split file cost:"+(System.currentTimeMillis() - time)+".....");
		return groupIndex;
	}
	
	private static void createNewFileSync(List list,int index) {
		//排序  从小到大
		list = sortList(list);
		String newPath = NEW_FILE_PATH.replace("&INDEX&", index+"");
		TestFileUtils.writeFile(newPath, list);
	}
	
	public static List sortList(List list){
		Collections.sort(list, new Comparator() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if (o1 >= o2)
					return 1;
				else 
					return -1;
			}
		});
		
		return list;
	}


        接下来就是根据分割出来的小文件进行排序,并生成最终的排序后的文件。这里我初始化了2个Map一个存放着每个文件读出来的那一行数据(Map),另一个存放着每个小文件的file对象(Map),Map的KEY都是单个小文件的那个标识,因为每个小文件都已经进行过排序(从小到大),那么每个文件的第一行中取到的最小值就是整个大文件中的最小值,将这个最小值写进文件,并从这个最小值所在的文件中再次读取一行,循环,当其中某一个文件读到了最后一行,那么将这个文件在MAP中的元素删除,循环继续,直至MAP为空的时候,则认为整个排序过程结束,这里在写文件的时候,也是分批的往文件中去写,分组的数量也是10W条写一次。实验的第一次时没有进行分组写入,99999999条数据一共用了一个多小时才全部写完,虽然每次写文件的耗时基本上是在纳秒级别的,但是架不住一共1亿次的写入....第二次分组写入,一共用时大概15分钟左右,那么基本上效率查了5、6倍左右吧...

        public static void margeSortFiles(int num){
		
		Map valueMap = new HashMap(num+10);
		Map fileMap = new HashMap(num+10);
		long startTime = System.currentTimeMillis();
		//初始化valueMap 和 fileMap
		for (int i=0 ;i<=num;i++) {
			String newPath = NEW_FILE_PATH.replace("&INDEX&", i+"");
			FileBean bean = new FileBean(newPath);
			int value = bean.readLineInt();
			//取值等于-1表示该文件里面已经木有东西了
			if (value == -1) {
				bean.destory();
				continue;
			}
			fileMap.put(i, bean);
			valueMap.put(i, value);
		}
		System.out.println("初始化文件相关数据结束   cost :"+(System.currentTimeMillis() - startTime));
		System.out.println("生成最终排序的大文件开始。。。");
		List list = null;
		long time = System.currentTimeMillis();
		int index = 0;
		while(!fileMap.isEmpty()) {
			
			if (list != null && list.size() % GOUPR_LENGTH == 0) {
				long appendTime = System.currentTimeMillis();
				TestFileUtils.appendFile(RESULT_FILE_PATH, list);
				System.out.println("append value:"+list.size()+"  costTime:"+(System.currentTimeMillis() - appendTime) +" index:"+index);
				list = null;
			}
			
			
			index++;
			//先获取一个最小值
			int minIndex = getMinIndex(valueMap);
			int value = valueMap.get(minIndex);
			
			//把数据放入集合, 批量写入
			if (list == null)
				list = new ArrayList();
			list.add(value+"");
			//把最小值写进文件里
			
			//然后从这个最小值所在的文件里再拿一个数出来,重新放进去
			FileBean file = fileMap.get(minIndex);
			int newValue = file.readLineInt();
			//如果获取出来的为-1,则认为这个文件读到末尾了,把这个文件从队列里去除
			if (newValue == -1) {
				valueMap.remove(minIndex);
				fileMap.remove(minIndex);
				continue;
			}
			//把原来的数给替换掉
			valueMap.put(minIndex,newValue);
		}
		
		long appendTime = System.currentTimeMillis();
		TestFileUtils.appendFile(RESULT_FILE_PATH, list);
		System.out.println("append value:"+list.size()+"  costTime:"+(System.currentTimeMillis() - appendTime) +" index:"+index);
		list = null;
		
		System.out.println("生成最终排序的大文件结束   cost:"+(System.currentTimeMillis()-time));
		
	}


        代码中的FileUtils 和 TestFileUtils  其实是一个类,只不过我写在了两个工程里, 然后拷贝过去的时候改了个名

    public class FileUtils {
	
	
	public static List readFileString(String path) {
		System.out.println("文件读取开始.");
		File file = new File(path);
		Scanner scanner = null;
		List list = new ArrayList();
		try {
			scanner = new Scanner(file, "utf-8");
			String str = null;
			while (scanner.hasNextLine()) {
				str = scanner.nextLine();
				System.out.println(str);
				list.add(str);
			}
		} catch (Exception e) {
			e.printStackTrace();
			System.out.println("文件读取异常.");
			list = null;
		}
		System.out.println("文件读取结束.-------->读取数据条数:"+(list == null ? 0 : list.size()));
		return list;
	}
	
	
	
	public static void writeFile(String filePath ,Collection list) {
		
		FileWriter fw = null;
		try {
			fw = new FileWriter(filePath,false);
			for (Object obj : list) {
				fw.write(obj.toString()+"\r\n");
			}
			fw.flush();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} finally {
			if (fw != null) {
				try {
					fw.close();
					fw = null;
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
		}
	}
	
	public static void writeFileString(String filePath ,Collection list) {
		
		FileWriter fw = null;
		try {
			fw = new FileWriter(filePath,false);
			for (String str : list) {
				fw.write(str+"\r\n");
			}
			fw.flush();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} finally {
			if (fw != null) {
				try {
					fw.close();
					fw = null;
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
		}
	}
	
	public static void appendFile(String filePath,List list){
		StringBuffer content = new StringBuffer();
		for (String str : list) {
			content.append(str).append("\r\n");
		}
		appendFile(filePath,content.toString());
	}
	
	public static void appendFile(String filePath ,String content){
		RandomAccessFile randomFile = null;
		File file =new File(filePath);
		try {
			if(!file.exists()){
				file.createNewFile();
			}
            randomFile = new RandomAccessFile(filePath, "rw");
            // 文件长度,字节数
            long fileLength = randomFile.length();
            //将写文件指针移到文件尾。
            randomFile.seek(fileLength);
            randomFile.writeBytes(content);
            randomFile.close();
		} catch (Exception e) {
			Logs.geterrorLogger().error("FileUtil appendFile exception:",e);
			e.printStackTrace();
		} finally {
			try {
				if (randomFile != null) {
					randomFile.close();
				}
			} catch (Exception e2) {
				Logs.geterrorLogger().error("FileUtil appendFile close writer exception:",e2);
			}
			
		}
		
	}
	
}




评论


暂无评论