【推荐】C# 实现 100G数据文件查找100个最大值 【2010支付宝西安最新笔试题】

Question

问题： 有一个100G大小的文件里存的全是数字，并且每个数字见用逗号隔开。现在在这一大堆数字中找出100个最大的数出来。
见原帖 http://topic.csdn.net/u/20091013/10/d5d371dc-6dec-4034-bf31-432a47ffce96.html
假设：1 文件中整数所占的字节数为固定
假设：2 文件中没有换行
假设：3 文件中 每两个数据之间都有个 逗号 分割
废话少说  代码如下
using System;
using System.Collections.Generic;
using System.Threading;
using System.Linq;
using System.Text;
using System.IO;
namespace BigFile
{
    class Find 
    {
        public byte[] Block;         //文件缓冲区
        public string filePath;      //文件路径
        public FileStream ft;         //文件流
        public int MaxSize;          //每次处理的最大数字个数
        public char s;               //分割符号
        public Int16 dot;            //分隔符号
        public int[] Result;         //存放的数组
        public int NumberSize = 4;   //整数所占的字节
        public int DotSize = 2;      // ，号所占的字节
        public long fileLength;      //要处理的文件总大小
        public long current;         //当前处理的位置  字节数
        public long start;            //开始读取的字节  用于多线程
        public long end;              //最后读取的字节   用于多线程
        public LinkedList<int> list; //用于存放100个数的队列
        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="file">要打开的文件的路径</param>
        public Find(string file)
        {
            this.MaxSize =10000000;   
            this.Block = new byte[MaxSize * (NumberSize + DotSize)];
            this.filePath = file;
            this.s = ',';
            this.dot = (Int16)this.s;
            this.Result = new int[100];
            this.ft = File.Open(this.filePath, FileMode.Open, FileAccess.Read, FileShare.Read);  //可以不共享模式打开
            this.fileLength = ft.Length;
            this.start = 0;
            this.end = this.fileLength;  
        }
        /// <summary>
        /// 用于多线程的构造函数
        /// </summary>
        /// <param name="file">文件路径+路径</param>
        /// <param name="start">开始处理的字节</param>
        /// <param name="end">结束处理的字节</param>
        public Find(string file, long start, long end)
        {
            this.MaxSize = 10000000;
            this.Block = new byte[MaxSize * (NumberSize + DotSize)];
            this.filePath = file;
            this.s = ',';
            this.dot = (Int16)this.s;
            this.Result = new int[100];
            this.start = start;
            this.end = end;
            this.ft = File.Open(filePath, FileMode.Open, FileAccess.Read, FileShare.Read);  //共享模式打开
            this.fileLength = ft.Length; 
        }
        /// <summary>
        /// 析构函数
        /// </summary>
        ~Find()
        {
            this.ft.Close(); 
        }
        /// <summary>
        /// 读取100个
        /// </summary>
        /// <param name="array"></param>
        public void Initial(ref int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = BitConverter.ToInt32(Block, i * (NumberSize + DotSize));
            }
        }
        /// <summary>
        ///测试专用  创造一个数据文件
        /// </summary>
        /// <param name="filepath">文件名</param>
        public static void WriteFile(string filepath,int MaxCount)
        {
            char s = ',';
            Int16  dot = (Int16)s;
           FileStream ft = File.Open(filepath, FileMode.OpenOrCreate);
           BinaryWriter w = new BinaryWriter(ft);
           //  Random ra = new Random(1000);   //随机产生数据  随机数据不好用于测试   
            for (int i = 0; i < MaxCount; i++)
            {
                w.Write(i);                  //w.Write(ra);
                w.Write(dot);   
            }
            w.Close();
            ft.Close();
        }
        /// <summary>
        /// 读取数据
        /// </summary>
        /// <param name="file">数据缓冲区</param>
        /// <param name="start">开始读取的位置</param>
        /// <param name="count">读取结束的位置</param>
        public void ReadFile( ref byte[] file, long start, int count)
        {
            this.ft.Position = start; 
            ft.Read(file, 0, count);
            this.current += count;
        }
        /// <summary>
        /// 获得排序后的数组
        /// </summary>
        public void GetArray()
        {
            Array w = this.Result.ToArray();   
            Array.Sort(w);
            this.Result =(int[]) w;    //强制转换为 int[]
        }
        /// <summary>
        /// 将数组转化成为 LinkedList     有好的发现也可以转换为其他结构
        /// </summary>
        public void GetLinkedList()
        {
           //以下代码可以将this.Result初始化为最坏的情况
            int m = 99999900;
            for (int i = 0; i < 99; i++)
                this.Result[i] = m + i;
            this.Result[0] = 0; 
            this.list = new LinkedList <int>(this.Result);
        }
        /// <summary>算法核心
        /// 大于队列最小值 则插入队列 同时Remove 掉最小值
        /// 需要改进下插入算法  能改成 二分查找 插入 效率最好
        /// </summary>
        /// <param name="mid"></param>
        public void Insert(int mid)
        { 
            //小于最小的值
            if(mid<=this.list.First.Value)
                return;
            //创建个新节点
            LinkedListNode<int> linkNode=this.list.Last ;
            //当前节点如果不小于 mid 就往前一个节点移动
            while (linkNode.Value >= mid)
            {
                linkNode = linkNode.Previous;
            }
            //加入新LinkNode
            this.list.AddAfter(linkNode, mid);
            //去掉最小的 LinkNode
            this.list.RemoveFirst();
        }
        /// <summary>处理核心 
        /// 分块载入数据 处理数据
        /// </summary>
        public void Research()
        { 
            this.ReadFile(ref this.Block,this.start, 100*(this.NumberSize+this.DotSize)); //读入指定文件位置this.start的100个数
            this.Initial(ref this.Result);
            this.GetArray();                                                              //将 this.Result 排序                                  
            this.GetLinkedList();                                                         //获得 LinkedList                                                            
            int temp=0;  
            while ((this.end - this.current) > this.Block.Length)
            {
                this.ReadFile( ref this.Block, this.current, (int)this.Block.Length);     //循环读入分块数据
                for (int i = 0; i < this.MaxSize; i++)
                {
                    this.Insert (BitConverter.ToInt32(Block, i * (NumberSize + DotSize)));//处理每个转化过来的数字  
                }
                Console.WriteLine("完成");
            }
            temp=(int)this.current;  //记录最后一次载入时候的字节流位置
            this.ReadFile( ref this.Block, this.current, (int)(this.end -this.current));
            //比较剩余的数据
            for (int i = 0; i < (this.end - temp)/(this.NumberSize+this.DotSize); i++)
            {
                this.Insert(BitConverter.ToInt32(Block, i * (NumberSize + DotSize)));
            }
        }
        //// 以下都是多线程处理
        /// <summary>
        /// 多线程处理方法
        /// </summary>
        /// <param name="count">指定一共运行几个线程</param>
        public void ThreadResearch(int count)
        {
            if (this.fileLength % count != 0)  //不能均等分数据块情况
                count++;
            long[] Start = new long[count];  //用于保存起始位置的数组
            long[] End = new long[count];     //用于保存结束位置的数组
            Thread[] Threadarray=new  Thread[count];
            Find[]   Findarray=new  Find[count]; 
            int s = (int)this.fileLength / count;
            for (int i = 0; i < count; i++)
            { 
                Start[i]=i*s;
                End[i] = (i+1) * s-1;
                Findarray[i] = new Find(this.filePath,Start[i],End[i]);
                Threadarray[i] = new Thread(Findarray[i].Research);                
            }
            ///以下三行代码 是  最后一个线程的设置
            End[End.Length - 1] = this.fileLength;  //不管能否除尽 都设置最后一个结束位置
            Findarray[Findarray.Length-1] = new Find(this.filePath, Start[Start.Length-1], End[End.Length -1]);
            Threadarray[Threadarray.Length-1] = new Thread(Findarray[Findarray.Length -1].Research); 
            //启动各个线程
            foreach (Thread td in Threadarray)
            {
                td.Start(); 
            }
            //等待线程全部结束
            foreach (Thread td in Threadarray)
            {
                while (td.IsAlive == true)
                    Thread.Sleep(100);  
            }
            //获取所有处理过后的this.List
            int[] FinalResult=new int[100*count];
            int index=0;
            foreach(Find fd in Findarray)
            {
                fd.list.CopyTo(FinalResult,index*100);
                index++;
            }
            //sort()排序
            Array w = FinalResult.ToArray();  
            Array.Sort(w);   //排序
            for (int i = 0; i < 100; i++)
            {
                this.Result[i] = FinalResult[FinalResult.Length - 100 + i]; 
            }
        }
    }
        class Program
        {
            static void Main(string[] args)
            {
                string path = @"D:\1.txt";
                // test.WriteFile(test.filePath );   //创建测试文件
                  int threadcount = 3;
                  Find test = new Find(path);
                  Console.WriteLine(DateTime.Now  );  
                  // test.ThreadResearch(threadcount);  //多线程处理 结果放在 test.Result 中
                     test.Research();                 //单线程处理 结果放在 test.List 中
                    Console.WriteLine(DateTime.Now); 
                foreach (int i in test.Result)
                {
                    Console.WriteLine(i);
                }
                Console.ReadKey();
            }
        }
    }
测试数据为 1.1G左右的数据文件
留待解决的问题：  
1  单线程 的效率比 多线程的效率 感觉还要高 【难道是 IO 效率引起的问题】
2  不知道100G 的文件能否顺利处理
3  核心 插入 函数需要改进改进  【改造成个 能够实现二分查找 插入的队列】
来 高手给改进改进 100G  处理时间要论小时计算了  哎........效率问题 
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/happyer_longlong/archive/2009/10/25/4726686.aspx

Answer 1

我觉得关键在于找数的算法。
先分割文件成N个大小差不多的部分，假设每段平均有a个数。
开N个线程，流式读入a个数，用一个长度为100的堆维护，最后有序输出这TOP100。设单个数的IO时间为t，比较一次的时间为单位1，到这步为止用时 a*t+a*log(100)+100*log(100)
再将这N个Top100进行一个N路的归并排序（只需完成前100项）用时100*log（N）
所以总时间是T=100*log(N)+a*t+a*log(100)+100*log(100)
另外，N和a还要满足：N*a=总数字数
这样就可线性规划解出使T最小的N和a的理论值
在考虑内存对N的限制修正理论值。
最后可得出一个比较省时的算法。
最后那个N路归并算法要自己写，前面的堆和堆排序可以直接使用库。因为每个线程里的文件都是流式读入的所以数据规模应该问题不大。想法还不算很成熟，如有错漏，请各大牛指正。

Answer 2

上面代码 给的是最坏情况下 
把  这个函数中 for 循环 屏蔽了即可  发帖时候忘屏蔽了
public void GetLinkedList() 
        { 
          //以下代码可以将this.Result初始化为最坏的情况 
            int m = 99999900; 
            for (int i = 0; i < 99; i++) 
                this.Result[i] = m + i; 
            this.Result[0] = 0; 
            this.list = new LinkedList <int>(this.Result); 
        } 

Answer 3

首先要搞清楚出这个题目的人用意是什么，100G的文件，现实当中，如果是文本，它用程序把数据写进去都不容易。何况要你去解析这个文件，出题的人以前可能也遇到过解析大文件发生的问题，他想找到是不是与之有共同语言之人，也就是你的答案和他的处理方式相对雷同的答案。如果我的话，我就会直接把100G放内存里，然后一个Array.Sort搞定，就10行代码之内，因为他并没有说硬件限制，我会假设内存大于100G。如果，说了硬件限制，那么无非就是分段处理，处理过扔掉的逻辑。那么我想的是，具体要知道Array.Sort算法性能在当前硬件限制下的临界值，如果你是就通过经验知道的话，我建议你不要去什么支付宝工作了，知道了Array.Sort在当前硬件限制下的临界值后，按这个临界值进行分割才是性能最佳的处理方式。当然，也与你起多少个线程有关，.net Framework 可以设置一个进程最多起多少个线程，终极解决方案是都找到那个临界值，然后运行，肯定是该硬件环境下的最快速度，当然还有另一个途径，排序算法自己写，但是，你是绝对没有Array.Sort的2叉树写得好的，但是也是一个途径。这个问题说深了，说透了的话，根本不用去支付宝，直接去微软即可

Answer 4

Array.Sort在当前硬件限制下的临界值后，按这个临界值进行分割才是性能最佳的处理方式  不同电脑配置不一样   我打算弄个工厂模式来根据硬件配置各个参数

Answer 5

另外，找出一堆数字中最大的n个数，并不需要排序，只要（quick sort算法中的一个子过程叫做）划分就可以。假设方法 partition(datas,begin,end) 是给datas从begin到end划分为两部分，这个函数返回的值middle标记划分的位置，那么得到前n大数字大致只是需要计算：do
{
   middle=partition(datas,begin,end);
   if(middle<n)
     begin=middle;
   else if(middle>n)
     end=middle;
   else
     break;
}while(true);不需要排序。如果先排序，再返回前n大数字，其时间复杂度就等于排序的时间复杂度。 

Answer 6

看见了Array.Sort()，它虽然快速排序实现的，但还是排序了饿
但题目是搜索啊，搜索不要求排序，这样肯定会损失性能的
搜索最快的算法是二分法吧，类似快速排序里的分区思想

Answer 7

1 产生这个100G数据文件的程序它输出的整数除非是String类型的， 否者它的长度就是固定的
2 如果数字是string 类型的  需要修改 转化 成整数的 函数

Answer 8

对于更新100个结果的数组我觉这样更简洁和快速：
首先，定义一个
List<String> Result=new List<String> Result()
...
if (Result.Count<100) // 前100个直接放进去
{
  Result.Add(读来的新值）;
  Result.Sort(); 排序
  Result.Reserve(); 反转
}  
else
{
  // 100个以后开始改为更新模式
  //  应为这个时候最早的100个数字肯定是从大到小排列的
  for (int i=0;i<Result.Count;i++)
      if (Result[i]<读来的新值)
      {
           // 所以从最大到最小循环
             // 如果发现读来的新值比当前列表某个值大         
             // 直接把读来的新值插入到这个值前面
             // 这时列表有101个值了，把最后那个最小的删除就可以了
           Result.Insert(i,读来的新值);
           Result.RemoveAt(Result.Count-1);
           Break;
      } 
}

Answer 9

呵呵,看到这个问题,想起了小时候家里收稻米.
大家都知道,稻米到米经过一系列流程的.第一步是粗分(脱壳)
第二步是细分(好像有个叫鼓风机的东西)
第三步是精分(筛子大小来分等级)
100G是什么概念,假设内存够大,就是完全读到内存中也需要一段时间!
如果不考虑读入内存的时候.我觉得做一把筛子是关键.数据一次过尽量少循环,也许速度会快一些.个人觉得 100G 
起一线程  读nM 从未读nM 找出nM大数据  处理完一次,再从n+1开始读到2n+1 未100G-n到100G-2n-1依次...
另起一个线程  读入线程一处理结果 出nM数据top100
再起一个线程  处理最后结果

Answer 10

一亿个浮点数，找出最大的1000个1.每100万个一组,读到内存（大约要4M内存）中,构建大顶堆，把堆顶（最大数）和文件号记录到一个100大小的数组A，再写回到磁盘，形成一个文件，这样共形成100个文件。 
2。这时，A数组也添满了，再对这A数组建大顶堆。 
3.堆顶A[0]输出。 
4.对堆顶对应的文件（同文件号确定）去掉堆顶后重新调整堆，再把新的堆顶放到A[0]. 
5.对A调整堆。 
6. 对2～4步循环10000次，最大的10000个数就选出来了。 

Answer 11

关键是 你的 
if (Result.Count <100) // 前100个直接放进去
{
  Result.Add(读来的新值）;
  Result.Sort(); 排序
  Result.Reserve(); 反转
} 
Result.Sort(); 比较肥时间啊 我用链表实现队列， 但是没法做二分查找插入了  ，只能顺序插入了

Answer 12

只是前100个直接文件读进来的数字而已
其实不用100次sort和reserveif (Result.Count <100)
{
  Result.Add(读来的新值）;
  if (Result.Count == 100) // 放完100个后执行一次从大到小排序就可以了
  {
    Result.Sort(); 排序
     Result.Reserve(); 反转
  }
}
else
{
 ...更新
}

Answer 13

我觉得还有一个类似算法的思维可以说一下，就是我先把从文件的钱100个数先排好序放在内存里，然后每取一个数就和这100个数比较，如果有比任何一个数大的则替换，这样性能应该保持着一种稳定状态，无非就是取一个最多比100次而已，这样的解决方案在逻辑上很简单易懂，代码如下：System.IO.StreamReader sd = System.IO.File.OpenText("G:\\CCURE9000\\sdfd.txt");
List<int> mTop100 = new List<int>();//my result and my firstList
char[] mChar=new char[100];
StringBuilder sbuff = new StringBuilder();
while(true)
{
int s=sd.Read();
char cuCh=(char)s;
if ("0123456789".IndexOf(cuCh) != -1)
{
sbuff.Append(cuCh);
}
else
{
int cIt=Convert.ToInt32(sbuff.ToString());
if (mTop100.Count < 100)
mTop100.Add(cIt);
else if (mTop100.Count == 100)
mTop100.Sort();
else
{
for(int i=0;i<mTop100.Count;i++)
{
if (mTop100[i] > cIt)
mTop100[i] = cIt;
}
}
sbuff = new StringBuilder();
}
}

Answer 14

System.IO.StreamReader sd = System.IO.File.OpenText("G:\\CCURE9000\\sdfd.txt");
List<int> mTop100 = new List<int>();//my result and my firstList
char[] mChar=new char[100];
StringBuilder sbuff = new StringBuilder();
while(true)
{
int s=sd.Read();
char cuCh=(char)s;
if ("0123456789".IndexOf(cuCh) != -1)
{
sbuff.Append(cuCh);
}
else
{
int cIt=Convert.ToInt32(sbuff.ToString());
if (mTop100.Count < 100)
mTop100.Add(cIt);
else if (mTop100.Count == 100)
mTop100.Sort();
else
{
for(int i=0;i<mTop100.Count;i++)
{
if (mTop100[i] > cIt)
mTop100[i] = cIt;
}
}
sbuff = new StringBuilder();
}
if (s == -1) break;//忘记退出了
}

Answer 15

重点在读取文件上面，排序问题不大，计算量不大，CPU很快，硬盘才是瓶颈
7200转硬盘是100MB/s
100G就要1000s