找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

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

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

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

推荐阅读

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

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved