`
daniel_tu
  • 浏览: 183762 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

一个题目:超大量数据的排序

    博客分类:
  • Java
阅读更多

一个文件里,有一堆int,把它们排序一下,输出到另外一个文件。
这个问题很简单了,把int读入内存,排序一下,输出到文件。
但是,如果加个条件:数据量巨大,内存无法容纳,那这个问题该怎么解决呢?
嗯,直接说答案:
1) 按内存能放下的规模,顺序读入一批批的数据,排序,输出到不同的文件
2) 现在得到一堆文件,每个文件里是排好序的
3) 对这些文件进行两两归并,就是把两个各自有序的文件,归并到一个有序的文件里
4) 最后得到一个文件

下面是代码:
假设int存放的格式是文本格式,一行一个。

private void button3_Click(object sender, EventArgs e)
{
    string from=@"e:\data.txt";
    string to=@"e:\target.txt";
    SortBigFile(from, to);
    Console.WriteLine(GetLineOf(from, 123456789));
}

private void SortBigFile(string from, string to)
{
    //读入内存排序的int个数
    //2.5e7个int,占内存约 100M
    const int BatchRead = 25000000;
    //临时文件夹
    const string TempDir = @"e:\temp\";
    int fileIndex = 0;
    StreamReader reader = new StreamReader(from);
    try
    {
        int[] data=new int[BatchRead];
        int count = 0;                

        string line;
        while((line=reader.ReadLine())!=null) {
            data[count++]=int.Parse(line);
            if(count>=BatchRead) {
                //读了一批
                //排序
                Array.Sort(data,0,count);
                //写文件
                string file=TempDir+"temp"+(++fileIndex)+".txt";
                WriteFile(data,count,file);
                //继续下一批
                count = 0;
            }
        }
        if (count > 0)
        {
            //余下的不够一批的
            Array.Sort(data, 0, count);
            //写文件
            string file = TempDir + "temp" + (++fileIndex) + ".txt";
            WriteFile(data, count, file);
        }
    }
    finally
    {
        reader.Close();
    }
    //开始归并排序
    string Temp=TempDir+"Temp.txt";
    //归并,直到只剩一个文件
    while (fileIndex > 1)
    {
        int c = 0;
        for (int i = 1; i <= fileIndex; i += 2)
        {
            int b = i + 1;
            if (b <= fileIndex)
            {
                MergeFile(TempDir + "temp" + i + ".txt", TempDir + "temp" + b + ".txt", Temp);
                c++;
                string t = TempDir + "temp" + c + ".txt";
                if (File.Exists(t))
                {
                    File.Delete(t);
                }
                File.Move(Temp, t);
            }
            else
            {
                //最后一个,落单了
                c++;
                string t=TempDir+"temp"+c+".txt";
                if(File.Exists(t)) {
                    File.Delete(t);
                }
                File.Move(TempDir+"temp"+i+".txt",t);
            }
        }
        fileIndex = c;
    }
    //归并到一个文件了
    File.Move(TempDir + "temp1.txt", to);
}

private void WriteFile(int[] data, int count,string file)
{
    if (File.Exists(file))
    {
        File.Delete(file);
    }
    StreamWriter writer = new StreamWriter(file, false);
    try
    {
        for (int i=0;i< int.Parse(lb))
                        {
                            t.WriteLine(la);
                            la = ra.ReadLine();
                        }
                        else
                        {
                            t.WriteLine(lb);
                            lb = rb.ReadLine();
                        }
                    }
                    else if (la != null)
                    {
                        t.WriteLine(la);
                        la = ra.ReadLine();
                    }
                    else
                    {
                        //lb!=null
                        t.WriteLine(lb);
                        lb = rb.ReadLine();
                    }
                }
                t.Flush();
            }
            finally
            {
                t.Close();
            }
        }
        finally
        {
            rb.Close();
        }
    }
    finally
    {
        ra.Close();
    }
}

private string GetLineOf(string file, int n)
{
    StreamReader reader = new StreamReader(file);
    try
    {
        string line=null;
        for (int i = 0; i < n; i++)
        {
            line = reader.ReadLine();
            if (line == null)
            {
                break;
            }
        }
        return line;
    }
    finally
    {
        reader.Close();
    }
}
 

分享到:
评论

相关推荐

    数据结构:第10章排序A.ppt

    数据结构中的排序是计算机科学中一个基础且重要的概念,它涉及到如何有效地组织和处理大量数据。在第10章“内部排序”中,主要探讨了数据在内存中的排序方法,这些方法通常适用于数据完全在内存中的情况。排序的目的...

    数据结构里的排序问题

    例如,快速排序在大多数情况下表现优秀,而归并排序在处理大量数据时更稳定。理解并掌握这些排序算法,有助于我们根据实际需求选择最适合的排序方法,提高程序的运行效率。在实际编程中,我们还可以结合各种优化策略...

    数据结构实训题目:图书借阅管理系统

    - **功能**: 输入成绩、统计总分、排序输出,需要设计高效算法处理大量数据。 6. **文章编辑器**(B级难度) - **字符串处理**: 统计字符、数字、空格数量,查找子串,删除子串,这些都涉及到字符串操作和算法。 ...

    数据结构排序以及排序的技巧

    1. **稳定性**:一个排序算法是稳定的,如果在排序过程中相等的元素不会改变它们的相对顺序。例如,对于序列[5, 3, 5, 1],稳定的排序算法会保持两个5的相对位置。题目中提到的选择题涉及到了稳定性和不稳定性排序...

    数据结构 内部排序练习题

    数据结构中的内部排序是计算机科学中处理大量数据的关键技术之一,它主要指在内存中进行的排序过程。这里我们关注的是一组特定的内部排序练习题,涉及到建立和调整堆的过程,以及堆排序算法的应用。 堆是一种特殊的...

    数据结构 面试 题目

    数据结构是计算机科学中一个重要的概念,它涉及到数据的组织、管理以及存储方式。良好的数据结构知识是解决算法问题、提升程序效率的基础。 #### 基本数据结构类型 - **线性结构**:如数组、链表、栈、队列等。 - ...

    这些题目涵盖了递归、排序、数据结构等多个方面,是算法学习和刷题的重要资源

    - **简介**: CodeTop 是一个专注于收集各大公司常考算法题目的在线平台,支持按公司、部门、岗位分类检索题目,方便用户针对性地进行练习。 #### 其他网站 - **hihoCoder**: &lt;https://hihocoder.com/&gt; - **计蒜客**...

    数据结构 折半插入排序

    ### 数据结构之折半插入排序 #### 知识点概览 1. **折半插入排序的基本概念** 2. **折半插入排序算法原理** 3. **折半插入排序的时间复杂度分析** 4. **折半插入排序的空间复杂度分析** 5. **折半插入排序与普通...

    程序员代码面试指南 IT名企算法与数据结构题目最优解.zip

    2. **排序与搜索**:如快速排序、归并排序、堆排序、二分查找、哈希查找等,这些都是解决大量数据处理问题的核心工具。 3. **动态规划**:这是解决复杂问题的有效方法,通过将大问题分解为小问题,找出最优解。 4....

    华农数据结构实验题目集合

    2. **链表**:与数组相比,链表的元素不连续存储,每个元素(节点)包含数据和指向下一个元素的指针。链表在插入和删除时效率较高,但访问速度不如数组。 3. **栈**:是一种后进先出(LIFO)的数据结构,常用于函数...

    数据结构课程设计—排序问题

    快速排序通过分治策略高效排序大量数据;选择排序每次选择最小元素放置于序列开头,简单但效率不高;冒泡排序通过相邻元素的比较和交换来排序,也是较为基础的排序方法。 #### 排序性能比较模块 该模块专注于统计...

    尚硅谷-实验:TreeSet的自然排序与定制排序.pdf

    ·自Java语言起源始,循序渐进,知识点剖析细致且每章配备大量随堂练习,让你步步为营,学得透彻、练得明白 ·拒绝晦涩难懂的呆板教学,宋老师语言生动幽默,举例形象生动深入浅出,迅速让你把握问题本质,四两拨千...

    王道考研系列:2013年数据结构联考复习指导

    综上所述,《王道考研系列:2013年数据结构联考复习指导》是一本全面涵盖数据结构考研知识点的书籍,不仅包含了基础理论知识,还提供了大量的例题解析和模拟试题,非常适合准备参加数据结构联考的学生作为复习资料...

    12种排序算法详解(寒小阳博客转出PDF版)

    由于其较高的时间复杂度,对于大量数据的排序,插入排序效率较低,但当数据量较小时(如数据规模小于千量级),插入排序是一个不错的选择。 在笔试面试中,尽管插入排序的考察频度不高,但其基本概念和操作容易被...

    sort排序 结构体题解

    在实际编程中,sort 排序可以帮助我们快速地对大量数据进行排序。 六、总结 sort 排序是 STL 库中的一个重要函数,它可以对数组、结构体、容器等进行排序。sort 排序的原理是使用类似于快排的方法,时间复杂度为 O...

    经典排序算法,有选择排序,冒泡排序,交换排序,谢尔排序,插入排序基数排序

    希尔排序和基数排序在处理大量数据时表现出色;而快速排序、归并排序等算法虽未在题目中提及,但在实际工程中应用更为广泛,因其较高的效率和稳定性。理解这些排序算法的原理和优劣,有助于我们在面对具体问题时做出...

    课设题目数据结构

    【课程设计】是学习计算机科学和技术的重要实践环节,它涵盖了数据结构、算法、网络、数据库等多个方面的知识。以下是对各个课设题目的详细解析: 1. **链表排序**: - **链表操作**:这里涉及到单链表的创建、...

    数据结构资源

    - **题目:** 对处理大量数据的外存介质而言,索引顺序存取方法是一种方便的文件组织方法。 - **答案:** 正确 - **解析:** 索引顺序存取方法能够有效支持大数据量的快速访问。 **8. ISAM组织方法适用性** - **题目:...

    对10进制数进行基数排序 数据结构

    - **第一次排序**:按照个位数排序,将所有数根据个位数的值进行分类,如将个位为 `0` 的放在一个子表中,个位为 `1` 的放在另一个子表中等。 - **第二次排序**:按照十位数排序,重复上一步操作,这次是对十位数...

Global site tag (gtag.js) - Google Analytics