一个让人蛋疼的面试题啊

Question

假设有一个文件,里面每一行一个关键字，如篮球
足球
姚明
足球
....
怎么样得出每个关键字的出现的次数,并按倒序排列。假设文件很大，10G,不能直接读到内存中统计。面试已经两次遇到这样的问题了，大家什么思路,用C#怎么做啊，谢谢各位大大

Answer 1

用泛型字典保存出现次数 Dictionary<string, int>，代码懒的写

Answer 2

那就一行一行readline（）；
发现一个 放到一个字典里，键是读到的名字，值从1开始，重复就++~~ so easy~

Answer 3

10g数据，每行占6byte(一个汉字为2字节，\r\n两个字节),大约有2g行，假设每个关键词重复10次，那么不重复的关键词有200m, 我们定义一个hashtable，key ， value都是int型，key存储关键词的hashcode,value存储关键词的出现次数，这样需要大约1.6g内存，现在一般的电脑都有2g物理内存，所以速度应该不成问题，下面我们开始读取数据：Dictionary<int,int> dict =  new Dictionary<int,int>();string lineData;
while(string.IsNullOrEmpty(buf = readder.ReadLine()))
{
   if(dict.ContainsKey(buf.GetHashCode())
   {
       dict[buf.GetHashCode()]++;
   }
   else
   {
       dict.Add(buf.GetHashCode(),1);
   }
}

Answer 4

蛋疼?为什么,这个面试题很简单吧.除非这10G文件每行都不一样,或者非重复数据读入到Dictionary里面超过内存1.7G在X86下
X64下,内存足够可以直接无视,不过要使用64位编程,仍然无法使用超过1.7G
如果真是这样,可以考虑牺牲一些效能放数据库里面去在给定以下前提下,代码简单的很:
1.10G文件非重复数据读入Dictionary不超过1.7G
2.X86架构下
3.不希望使用数据库
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml.Linq;
using System.Collections;
using System.IO;namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(@"d:\test.xml", Encoding.UTF8);
            Dictionary<string, int> dicResult = new Dictionary<string, int>();
            string TempString = string.Empty;
            while (sr.Peek() > 0)
            {
                TempString = sr.ReadLine();
                if (dicResult.Keys.Contains(TempString))
                {
                    dicResult[TempString]++;
                }
                else
                {
                    dicResult.Add(TempString, 1);                }
            }      
             //根据数量倒序            //1.Linq
            var Result = from o in dicResult
                         orderby o.Value descending
                         select o;
            foreach (var r in Result)
            {
                Console.WriteLine(r.Key + " : " + r.Value.ToString());
            }    
            //2.Lambda
            foreach (KeyValuePair<string, int> kvp in dicResult.OrderByDescending(k => k.Value))
            {                Console.WriteLine(kvp.Key + " : " + kvp.Value.ToString());
            }             Console.ReadKey();
        }
    }
}

Answer 5

"X64下,内存足够可以直接无视,不过要使用64位编程,仍然无法使用超过1.7G"
==>
"X64下,内存足够可以直接无视,不过要使用64位编程,不然仍然无法使用超过1.7G"

Answer 6

个人猜测意义如下:
0.基本Stream读入操作
1.可能内存溢出的处理
2.HashTable or Dictionary应用
3.如果用到Linq就考一下Linq.
4.如果不用Linq或者内置的OrderBy,就考排序算法.

Answer 7

整个数据结构和算法总结起来就2句话：
1，查找用哈希O(1)
2，排序用二叉O（n*logn）

Answer 8

还有，用脑子想一想，人类到底有多少个词？
http://baike.baidu.com/view/6713.htm?fr=ala0_1_1
《辞海》共10，5400余条。才10万多。
http://news.qq.com/a/20081006/001065.htm
韩大学称用30年完成世界最大汉字词典编撰
约45万个单词,不到2的19次方524288
我们就算信息大爆炸，一种语言的词汇量也不可能超过2的22次方，把地球上所有语言都加起来，也不会超过int32个词。
只要他是词，不是长篇大论，汉字最长的词也不会超过10个字，恐怕还是外来词或者化学名词，而且极其的少。
所以，我觉得，这10个G里边重复的占99%以上！~~~
因此，内存是完全放得下滴！~~~
如果放不下，可以从语文的角度去想问题，而不是计算机技术的角度，因为我们做的东西是给人用的！就算机器产生的二进制数据串，完全分布随机，10个G,每行数据长度是40个字节。
我们也可以分治，比如先读前4个字节，把数据重新分配到新的硬盘空间，这样依次分治，就可以把文件分布在
10层文件夹以内。假设把象棋的所有步法，按照文件夹去分，比如炮二平五，兵三进一是第一层，马2进3，卒7进1是第2层，那么所有可能的不磨棋着法，整个地球上的硬盘都不够，但是合理的着法，一个硬盘就可以装下。
 

Answer 9

这题目怎么就让人蛋疼了，不明白的.
怎么就说复制别人的面试题不行呢.
上次是100G,这次10G 不要太友好啊.
还是用sizeof_t,分段页式,外加多线程处理
用数据结构或者数据库都行.

Answer 10

如果是文本文件txt格式，我估计想都别想了。那个东西支持64k的。超过这个数字到10/20/30M的文件都尝试过，不太容易操作了。要是10g。很够呛的 。本题目的考法，跟人感觉就是看应聘者知道不知道在win32系统下面文件操作函数支持大小和类型。
以前呢是4G。 现在把int/long 这些都改成sizeof_t了 ，这个定义跟time的那个一样 都是一个64位的。
这下就可以操作这个大文件了。 我指定打开，指定位置读多少个。 负责int/long这个类型的position 就不好用了。 这是一个考点了另外一个就是效率问题。还有一个就是用一些 hash dictionary之类 这些本身能处理多大的数据 ，内存能接受多少 。反正现场程序我肯定不写的，大概思路 方法 我写写就OK了

Answer 11

很少用Has，现在出去面试咱可能过不了第一轮

Answer 12

assiwe你有什么好的想法啊 现在大家都说是用hash减少存储空间

Answer 13

32位下可以使用/3g参数，这样.net就能访问2g以上内存了。