找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ 海量数据处理 ] [守望者 算法面试题] 海量短信中找重复的前10条

2014-09-23 13:33| 发布者: watchmen | 查看: 2205 | 收藏

摘要: 有一千万条短信,有重复,以文本文件的形式保存,一行一条,有重复。请用5分钟时间,找出重复出现最多的前10条。
有一千万条短信,有重复,以文本文件的形式保存,一行一条,有重复。请用5分钟时间,找出重复出现最多的前10条。

你有新的观点?  

已有1参与讨论

  • 思路:

    方法1:可以用哈希表的方法对1千万条分成若干组进行边扫描边建散列表。第一次扫描,取首字节,尾字节,中间随便两字节作为hash Code,插入到hash table中。并记录其地址和信息长度和重复次数,1千万条信息,记录者几个信息还放得下。同hash code且等长就是疑似相同,比较一下。相同记录只加1次进hash table,但将重复次数加1.一次扫描以后,已经记录各自的重复次数,进行第二次hash table的处理。用线性时间选择可在O(n)的级别上完成前10条的寻找。分组后每份中的top 10必须保证各不相同,可用hash来保证。也可以直接按hash值的大小来分类。

    方法2:可以采用从小到大排序的方法,根据经验,除非是群发的过节短信,否则字数越少的短信出现重复的几率越高。建议从字数少的短信开始找起,比如一开始搜一个字的短信,找出重复出现的top10并分别记录出现次数,然后搜两个字的,比如开始搜一个字的短信,找出重复出现的top10并分别记录出现次数,然后搜两个字的,一次类推。对于相同字数的比较长的短信的搜索,除了hash之类的算法外,可以选择只抽取头、中和尾等几个位置的字符进行粗判,因为此种判断方式是为了加快查找速度但未必能得到真正期望的top10,因此需要做标记;如此搜索一遍后,可以从各次top10结果中找到备选的top10,如果这top10中有刚才做过标记的,则对其对应的所有短信进行精确搜索以找到真正的top10并在此比较。


    参考源码:


    #include<iostream>
    #include<fstream>
    #include<stdlib.h>
    #include<malloc.h>
    const int ERROR=0;

    using namespace std;

    struct LinkHash
    {
    LinkHash *next;
    char Value[10];
    int Count;
    };
    struct _Data
    {
    char Value[10];
    int Count;
    };

    class CHashTable
    {
    private:
    LinkHash *HashTable[101];
    public:
    CHashTable();
    ~CHashTable();

    void HashCollision(char const *p);
    void WriteToFile();

    };
    CHashTable::CHashTable()
    {
    int i;
    for(i=0;i<100;i++)
    {
      HashTable=(LinkHash*)malloc(sizeof(LinkHash));
      if(!HashTable)
       exit(ERROR);
      HashTable->Count=0;
      HashTable->next=NULL;

    }
    }
    CHashTable::~CHashTable()
    {

    }
    int Hash_Func(char const *p)
    {
    int Value=0;
    while(*p!='\0')
    {
      Value=*p+Value;
      p++;
    }
    return Value%100;
    }
    void CHashTable::HashCollision(char const *p)
    {
    LinkHash *newNode;
    LinkHash *head;
    newNode=(LinkHash*)malloc(sizeof(LinkHash));
    if(!newNode)
      exit(ERROR);
    newNode->next=NULL;
    //newNode->Value=p;
    strcpy(newNode->Value,p);
    newNode->Count=0;

    int pos;
    bool isRep=false;
    pos=Hash_Func(p);
    head=HashTable[pos];
    while(head->next)
    {
      head=head->next;
      if(strcmp(head->Value,p)==0)
      {
       head->Count++;
       isRep=true;
       break;
      }
    }
    if(isRep==false)
    {
      head->next=newNode;
      head=newNode;
      head->next=NULL;
      head->Count++;
    }

    }
    void CHashTable::WriteToFile()//将原短信去重后统计出重复次数后写入result.txt文件中
    {
    int i;
    ofstream fout;
    fout.open("result.txt");
    for(i=0;i<100;i++)
    {
      LinkHash *p;
      if(HashTable->next)
      {
       p=HashTable->next;
       while(p)
       {
        fout<<p->Value<<" "<<p->Count<<endl;
        p=p->next;
       }
      }
    }
    fout.clear();
    fout.close();
    }
    void MaxHeap(_Data Array[],int i,int len)//最大堆调整
    {
    int j;
    _Data data=Array;//记录当前结点的值
    for(j=2*i;j<=len;j=j*2)
    {
      if(j<len&&Array[j].Count<Array[j+1].Count)
       j++;//沿关键字较大的孩子结点向下查找
      if(Array[j].Count<data.Count)
       break;//找到合适的位置
      Array=Array[j];
      i=j;

    }
    Array=data;
    }


    int main()
    {
    int i;int len;
    int j;
    int k=10;
    char str[100];
    char instr[10];
    char outstr[10];
    _Data *Array=new _Data[11];
    int *Array1=new int[k+1];
    ifstream fin;
    ofstream fout;
    _Data InData;

    /*fout.open("MessageData.txt");

    for(i=0;i<10000000;i++)//随机生成重复的短信,短信简化为三个字母
    {
      
      for(j=0;j<3;j++)
                 str[j]='A'+rand()%10;
      str[3]='\0';
           fout<<str<<"\r\n";
       
    }
    fout.close();*/
    CHashTable CHT=CHashTable();
    fin.open("MessageData.txt");
    if(fin.is_open())
    {
          while(fin>>instr)//将原短信文档读入并通过hash表处理
       {
        CHT.HashCollision(instr);
       }
    }
    fin.close();
    fin.clear();
       CHT.WriteToFile();

       
       fin.open("result.txt");//从databig.txt中读取数据
       if(fin.is_open())
       {
        for(i=1;i<=k;i++)//先读取前k个
        {
         fin>>Array.Value>>Array.Count;
         // cout<<" !!! "<<Array.Count<<endl;
        }


        cout<<"调整为堆:"<<endl;
        for(i=k/2;i>0;i--)//对先读取前k个数建立堆
         MaxHeap(Array,i,k);






        fin>>InData.Value>>InData.Count; //继续读取文件中后面的数
        while(fin.fail()==false)//如果没有到文件尾
        {   

         if(InData.Count<Array[1].Count)//如果读取的数小于现有的堆的堆顶元素,则交换
         {
          Array[1]=InData;     
          MaxHeap(Array,1,k);//调整为堆
         }
         fin>>InData.Value>>InData.Count;
        }

       }
       for(i=1;i<=k;i++)//输出前k个数
        cout<<Array.Value<<" ------ "<<Array.Count<<endl;

       return 1;
      
    }
    zhouy

    2014-10-17 14:55

推荐阅读

[守望者 内推职位]中电科网络信息安全有限责任公司
[守望者 内推职位]中电科网络信息安全
中国电子科技集团公司第三十研究所(以下简称:三十所)创建于1965年,是集通
[猎头职位] 英国金融公司 liquid(利源软件)Linux C++高级开发
[猎头职位] 英国金融公司 liquid(利源
Liquid Capital Group 是一家总部位于伦敦的专门从事金融衍生品交易和做市业
【守望者 内推职位】腾讯平台架构后台开发工程师
【守望者 内推职位】腾讯平台架构后台
守望者:腾讯后端开发,职位在深圳,年薪30~35W,成都主要为游戏开发相关职位
[守望者 猎头职位] 某民机航电公司  研发技术副总监 VxWorks软件高级工程师 Linux软件 ...
[守望者 猎头职位] 某民机航电公司 研
以下职位为猎头职位。有兴趣可将简历发送到362528717@qq.com或者加QQ交流,匹
[猎头职位] 加拿大 宏利金融  .Net 高级开发
[猎头职位] 加拿大 宏利金融 .Net 高
守望者:本职位为金融开发相关陪伴,要求有较强的架构设计能力,开发能力,分
[猎头职位] 高级嵌入式系统架构师
[猎头职位] 高级嵌入式系统架构师
高级嵌入式系统架构师
【猎头职位】欧美软件开发公司  ASP.NET高级工程师
【猎头职位】欧美软件开发公司 ASP.NE
公司专门对欧美软件外包服务提供商。公司在多个领域有着独到和突出的技术,包
[猎头职位] 系统测试__安全产品测试
[猎头职位] 系统测试__安全产品测试
系统测试__安全产品测试
[内部推荐]重庆金鑫智慧java高级程序员
[内部推荐]重庆金鑫智慧java高级程序员
守望者:重庆金鑫智慧是重庆南桐矿业集团公司旗下的子公司,有专业的队伍进行
[猎头职位] windows客户端开发工程师或leader 公共技术客户端高级架构师(深圳) ... .. ...
[猎头职位] windows客户端开发工程师或
守望者:以下两个职位为互动娱乐高端管理职位。主要工作为游戏开发及项目管理
【守望者  面试交流】HR谈 如何使用E-mail投递简历
【守望者 面试交流】HR谈 如何使用E-m
守望者:现在的简历一般都使用E-mail发送,然而,随着信息泛滥,HR需要从浩瀚

推荐阅读

[守望者 内推职位]中电科网络信息安全有限责任公司
[守望者 内推职位]中电科网络信息安全
中国电子科技集团公司第三十研究所(以下简称:三十所)创建于1965年,是集通
[猎头职位] 英国金融公司 liquid(利源软件)Linux C++高级开发
[猎头职位] 英国金融公司 liquid(利源
Liquid Capital Group 是一家总部位于伦敦的专门从事金融衍生品交易和做市业
【守望者 内推职位】腾讯平台架构后台开发工程师
【守望者 内推职位】腾讯平台架构后台
守望者:腾讯后端开发,职位在深圳,年薪30~35W,成都主要为游戏开发相关职位
[守望者 猎头职位] 某民机航电公司  研发技术副总监 VxWorks软件高级工程师 Linux软件 ...
[守望者 猎头职位] 某民机航电公司 研
以下职位为猎头职位。有兴趣可将简历发送到362528717@qq.com或者加QQ交流,匹
[猎头职位] 加拿大 宏利金融  .Net 高级开发
[猎头职位] 加拿大 宏利金融 .Net 高
守望者:本职位为金融开发相关陪伴,要求有较强的架构设计能力,开发能力,分
[猎头职位] 高级嵌入式系统架构师
[猎头职位] 高级嵌入式系统架构师
高级嵌入式系统架构师
【猎头职位】欧美软件开发公司  ASP.NET高级工程师
【猎头职位】欧美软件开发公司 ASP.NE
公司专门对欧美软件外包服务提供商。公司在多个领域有着独到和突出的技术,包
[猎头职位] 系统测试__安全产品测试
[猎头职位] 系统测试__安全产品测试
系统测试__安全产品测试
[内部推荐]重庆金鑫智慧java高级程序员
[内部推荐]重庆金鑫智慧java高级程序员
守望者:重庆金鑫智慧是重庆南桐矿业集团公司旗下的子公司,有专业的队伍进行
[猎头职位] windows客户端开发工程师或leader 公共技术客户端高级架构师(深圳) ... .. ...
[猎头职位] windows客户端开发工程师或
守望者:以下两个职位为互动娱乐高端管理职位。主要工作为游戏开发及项目管理
【守望者  面试交流】HR谈 如何使用E-mail投递简历
【守望者 面试交流】HR谈 如何使用E-m
守望者:现在的简历一般都使用E-mail发送,然而,随着信息泛滥,HR需要从浩瀚