忘记密码   免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 2858 | 回复: 2

[应用] 寻找字符串 [复制链接]

论坛徽章:
1
2015亚冠之塔什干火车头
日期:2015-06-08 10:15:34
发表于 2018-04-20 09:21 |显示全部楼层
大家好,向大牛们咨询一个编程问题,
比如有100w个字符串,随机输入一个字符串,判断是不是这个100w个字符串中的?
我的思路是这样的,通过头尾来寻找字符串。
char*p[100w];
char a=xxx
for(i = 0; i < (100w/2); i++)
{
    if(strcmp(p[i],a) == 0)
    {   
            do_something;
            break;
     }
    if(strcmp(p[100w-1-i], a) == 0)
    {   
           do_something;
           break;
     }
}
但是这样100w个字符串也要循环50w次,效率不是很高,有没有更好的方法?
谢谢!


论坛徽章:
0
发表于 2018-05-03 20:23 来自手机 |显示全部楼层
做出每个字符串的hash去比较

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2018-07-17 15:35 |显示全部楼层
建立N个hash桶,将100w个字符串计算hash值 取模N分布到N个桶中。
输入字符串hash值 取模N 得到桶位置,在桶中比较,

1. 如果桶中的可以有序可以二分快些。
2. 不考虑内存把桶数据放大些。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:wangnan@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP