利用归并排序算法对大文件进行排序

标签: 利用 归并排序 算法 | 发表时间:2015-01-25 20:59 | 作者:
出处:http://www.iteye.com

 

归并排序算法介绍,请参照Wikipeida

zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

基本思想:

大文件分割成行数相等的两个小文件,使用递归一直分割到所有所有小文件低于限制行数

小文件直接排序

两个排序好的小文件归并到大文件

直到最后所有排序好的文件归并到输入的大文件并返回

 

之前看了网上很多示例代码,写的很不简洁, 引入了过多的临时变量i, j, k等等, 导致程序基本没法看,

只好自己写了一个,没有很关心执行效率, 只求够用,以后有机会再优化一下吧。

JDK要求Java 8

 

package com.java.sort.merge;

import com.google.common.base.Charsets;
import com.google.common.base.Strings;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterators;
import com.google.common.collect.PeekingIterator;
import com.google.common.io.Files;
import org.apache.commons.io.FileUtils;
import org.apache.commons.io.IOUtils;
import org.apache.commons.io.LineIterator;
import org.apache.commons.io.filefilter.AndFileFilter;
import org.apache.commons.io.filefilter.PrefixFileFilter;
import org.apache.commons.io.filefilter.SuffixFileFilter;
import org.junit.AfterClass;
import org.junit.BeforeClass;
import org.junit.Test;

import java.io.File;
import java.io.FilenameFilter;
import java.io.IOException;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FileMergeSort {
    private static int limit = 9999;

    private static void cleanTempFiles() {
        FilenameFilter filter = new AndFileFilter(ImmutableList.of(new PrefixFileFilter("sort"), new SuffixFileFilter(".part")));
        ImmutableList.copyOf(FileUtils.getTempDirectory().listFiles(filter)).forEach(File::delete);
    }

    private static int lineNumber(File input) throws IOException {
        int count = 0;
        LineIterator iterator = FileUtils.lineIterator(input);
        while (iterator.hasNext()) {
            iterator.next();
            count++;
        }
        return count;
    }

    private static File split(File input, int from, int to) throws IOException {
        File part = File.createTempFile("sort", ".part");
        Long lineNumber = 0L;
        String line = null;
        List<String> lines = new ArrayList<>(to - from);
        LineIterator iterator = FileUtils.lineIterator(input);
        while (iterator.hasNext()) {
            if (lineNumber > to) break;
            line = iterator.next();
            if (lineNumber >= from && lineNumber <= to) {
                lines.add(line);
            }
            lineNumber++;
        }
        FileUtils.writeLines(part, lines);
        return part;
    }

    private static File merge(File source, File left, File right) throws IOException {
        PeekingIterator<String> leftLineIterator = Iterators.peekingIterator(FileUtils.lineIterator(left));
        PeekingIterator<String> rightLineIterator = Iterators.peekingIterator(FileUtils.lineIterator(right));
        String leftLine, rightLine;
        try (Writer writer = Files.newWriter(source, Charsets.UTF_8)) {
            writer.write("");
            while (leftLineIterator.hasNext() && rightLineIterator.hasNext()) {
                leftLine = leftLineIterator.peek();
                rightLine = rightLineIterator.peek();
                if (leftLine.compareTo(rightLine) < 0) {
                    writer.append(leftLine.concat(IOUtils.LINE_SEPARATOR));
                    leftLineIterator.next();
                } else {
                    writer.append(rightLine.concat(IOUtils.LINE_SEPARATOR));
                    rightLineIterator.next();
                }
            }
            while (leftLineIterator.hasNext()) {
                writer.append(leftLineIterator.next().concat(IOUtils.LINE_SEPARATOR));
            }
            while (rightLineIterator.hasNext()) {
                writer.append(rightLineIterator.next().concat(IOUtils.LINE_SEPARATOR));
            }
        }
        return source;
    }

    private static File directSort(File input) throws IOException {
        List<String> list = new ArrayList<>(limit);
        FileUtils.lineIterator(input).forEachRemaining(list::add);
        Collections.sort(list);
        FileUtils.writeLines(input, list);
        return input;
    }

    public static File mergeSort(File input) throws IOException {
        int total = lineNumber(input);
        if (total <= limit) {
            return directSort(input);
        }
        int half = total / 2;
        File left = mergeSort(split(input, 0, half));
        File right = mergeSort(split(input, half + 1, total));
        return merge(input, left, right);
    }


    @BeforeClass
    public static void init() throws IOException {
        cleanTempFiles();
        try (Writer writer = Files.newWriter(new File("long.txt"), Charsets.UTF_8)) {
            writer.write("");
            for (long i = 99999L; i > 0L; i--) {
                writer.append(Strings.padStart(String.valueOf(i), 5, '0').concat(IOUtils.LINE_SEPARATOR));
            }
        }
    }

    @AfterClass
    public static void clean() {
        cleanTempFiles();
    }

    @Test
    public void testSort() throws IOException {
        File sorted = mergeSort(new File("long.txt"));
    }

}

 

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.java.app</groupId>
    <artifactId>sample</artifactId>
    <version>1.0-SNAPSHOT</version>

    <dependencies>
        <dependency>
            <groupId>commons-io</groupId>
            <artifactId>commons-io</artifactId>
            <version>2.4</version>
        </dependency>       
        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>18.0</version>
        </dependency>
        <dependency>
            <groupId>javax.servlet</groupId>
            <artifactId>javax.servlet-api</artifactId>
            <version>3.1.0</version>
        </dependency>
        <dependency>
            <groupId>org.apache.logging.log4j</groupId>
            <artifactId>log4j-api</artifactId>
            <version>2.1</version>
        </dependency>
        <dependency>
            <groupId>org.apache.logging.log4j</groupId>
            <artifactId>log4j-core</artifactId>
            <version>2.1</version>
        </dependency>
        <dependency>
            <groupId>org.apache.logging.log4j</groupId>
            <artifactId>log4j-jcl</artifactId>
            <version>2.1</version>
        </dependency>
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.12</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
</project>

 



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [利用 归并排序 算法] 推荐:

利用归并排序算法对大文件进行排序

- - ITeye博客
归并排序算法介绍,请参照Wikipeida. 大文件分割成行数相等的两个小文件,使用递归一直分割到所有所有小文件低于限制行数. 两个排序好的小文件归并到大文件. 直到最后所有排序好的文件归并到输入的大文件并返回. 之前看了网上很多示例代码,写的很不简洁, 引入了过多的临时变量i, j, k等等, 导致程序基本没法看,.

Java排序算法:归并排序

- - zzm
 Java排序算法(九):归并排序. 归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的. 然后再把有序子序列合并为整体有序序列. 归 并排序是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.

HipHop算法:利用微博互动关系挖掘社交圈

- - CSDN博客互联网推荐文章
       /* 版权声明:可以任意转载,转载时请务必标明文章原始出处和作者信息 .*/.                  CopyMiddle: 张俊林                    .                  TimeStamp:2012年3 月.         在微博环境下,如何自动挖掘某个微博用户的社交圈子或者兴趣圈子是个很基础且重要的问题.

利用Mahout实现在Hadoop上运行K-Means算法

- - CSDN博客云计算推荐文章
    K-Means算法是基于分划分的最基本的聚类算法,是学习机器学习、数据挖掘等技术的最基本的 知识,所以掌握其运行原理是很重要的.     转载请注明出处:  http://hanlaiming.freetzi.com/?p=144.      一、介绍Mahout.     Mahout是Apache下的开源机器学习软件包,目前实现的机器学习算法主要包含有 协同过滤/推荐引擎, 聚类和 分类三个部分.

IJCAI 2019 丨利用半参表示算法缓解推荐系统中的冷启动问题

- - 雷锋网
由于常见电商、视频等推荐系统 (淘宝首猜、优酷推荐等) 用户量巨大, 而且用户个性化兴趣差异明显, Item-CF 较于 User-CF 有着天然的巨大优势,它因此被广泛运用于推荐系统中. 常见的 Item-CF 推荐系统中, 服务器收到用户访问请求, 经解析、查询得到用户 profile(包括用户长期画像、历史足迹等) 后,通过 Item2Item、tag 等方式进行候选召回,参与后续排序和后处理.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.