【讨论】100G数字文件查找100个最大值感兴趣的给改进改进【2010支付宝西安最新笔试题】

Question

问题： 有一个100G大小的文件里存的全是数字，并且每个数字见用逗号隔开。现在在这一大堆数字中找出100个最大的数出来。
http://topic.csdn.net/u/20091013/10/d5d371dc-6dec-4034-bf31-432a47ffce96.html
假设：1 文件中整数所占的字节数为固定
假设：2 文件中 每两个数据之间都有个 逗号 分割
C#  代码如下  不是java的 见谅    
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

100G 我的电脑处理需要 最好情况要 4100秒  最坏情况需要 21000 秒  将近5个小时吧 
cup  intel双核 1.6  Ram 512M  （小了点） 
万转的服务器 处理起来应该快些

Answer 2

原帖是 java 这里抛出来的这里关注人多吧 嘿嘿

Answer 3

上面代码 给的是最坏情况下 
把  这个函数中 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 4

c#是什么？c，两个+号放在一起，就变成了c#了？呵呵。