Kav*_*jal 10 c++ vector hashmap data-structures
用C++编码.我需要一堆排序字符串的数据结构.我将一次性插入所有字符串而不更新它,但我会经常搜索字符串.我只需要查看结构中是否存在给定字符串.我期待这个列表大约有100个字符串.什么是更快的结构？我最初在思考hashmap,但是我看到某个地方对于这么少的元素,对矢量的二进制搜索会更好(因为它们已经排序).
Bee*_*ope 18
假设您正在谈论"全尺寸"CPU 1,那么至少相对于其他解决方案,即使只有100个元素,通过字符串进行二进制搜索也可能相当慢.对于每次搜索,您可能会遇到几个分支误预测,并且最终可能会多次检查输入字符串中的每个字符(因为您需要strcmp在二进制搜索中的每个节点重复检查).
正如有人已经指出的那样,唯一真正知道的方法就是衡量 - 但要做到这一点,你仍然需要能够弄清楚候选人是什么!此外,并不总是可以在现实场景中进行测量,因为可能甚至不知道这样的场景(例如,设想一个在许多不同情况下广泛使用的库函数).
最后,了解什么可能是快速的,让你既消除你知道会表现糟糕的候选人,并允许你用你的直觉仔细检查你的测试结果:如果某些事情比你预期的慢得多,那么值得检查为什么(是的编译器做一些愚蠢的事情,如果事情要快得多,那么也许是时候更新你的直觉了.
因此,我会尝试实际考虑快速的事情 - 假设速度在这里非常重要,您可以花一些时间来验证复杂的解决方案.作为基线,直接实现可能需要100 ns,而真正优化的实现可能需要10 ns.因此,如果你花费10个小时的工程时间,你将不得不拨打这个功能4000亿次才能获得10小时的回报5.当您考虑到错误风险,维护复杂性和其他开销时,您将需要确保在尝试优化它之前调用此函数数万亿次.这些功能很少见,但肯定存在4.
也就是说,您缺少帮助设计快速解决方案所需的大量信息,例如:
std::string还是const char *其他？上面的答案可以帮助您划分设计空间,如下所述.
如果每(4)你可以接受(可控)数量的误报2,或者每(3)你的大多数搜索将不成功,那么你应该考虑一个布隆过滤器.例如,您可以使用1024位(128字节)过滤器,并使用字符串的60位散列来索引6个10位函数.这使得假阳性率<1%.
这样做的好处是,在哈希计算之外,它与字符串的长度无关,并且它不依赖于匹配行为(例如,如果字符串倾向于长,则依赖于重复字符串比较的搜索会更慢共同前缀).
如果你可以接受误报,你就完成了 - 但是如果你需要它总是正确的但是期望大多数不成功的搜索,你可以将它用作过滤器:如果bloom过滤器返回false(通常情况下)你就完成了,但如果它返回true,则需要仔细检查下面讨论的一个始终正确的结构.所以常见的情况很快,但总是返回正确的答案.
如果在编译时知道~100个字符串的集合,或者你可以做一些一次性繁重的工作来预处理字符串,你可以考虑一个完美的哈希.如果你有一个编译时已知的搜索集,你可以将字符串打入gperf,它会吐出一个哈希函数和查找表.
比如,我刚刚喂100个随机英语单词3成gperf和它产生的散列函数只需要看两个字符来唯一区分每个字,就像这样:
static unsigned int hash (const char *str, unsigned int len)
{
static unsigned char asso_values[] =
{
115, 115, 115, 115, 115, 81, 48, 1, 77, 72,
115, 38, 81, 115, 115, 0, 73, 40, 44, 115,
32, 115, 41, 14, 3, 115, 115, 30, 115, 115,
115, 115, 115, 115, 115, 115, 115, 16, 18, 4,
31, 55, 13, 74, 51, 44, 32, 20, 4, 28,
45, 4, 19, 64, 34, 0, 21, 9, 40, 70,
16, 0, 115, 115, 115, 115, 115, 115, 115, 115,
/* most of the table omitted */
};
register int hval = len;
switch (hval)
{
default:
hval += asso_values[(unsigned char)str[3]+1];
/*FALLTHROUGH*/
case 3:
case 2:
case 1:
hval += asso_values[(unsigned char)str[0]];
break;
}
return hval;
}
现在您的哈希函数很快并且可能已经很好地预测(如果您没有太多长度为3或更少的字符串).要查找字符串,您只需索引到哈希表(也由生成者gperf),并比较您获得的输入字符串.
在一些合理的假设下,这将是你能得到的最快速度 - clang生成如下代码:
in_word_set: # @in_word_set
push rbx
lea eax, [rsi - 3]
xor ebx, ebx
cmp eax, 19
ja .LBB0_7
lea ecx, [rsi - 1]
mov eax, 3
cmp ecx, 3
jb .LBB0_3
movzx eax, byte ptr [rdi + 3]
movzx eax, byte ptr [rax + hash.asso_values+1]
add eax, esi
.LBB0_3:
movzx ecx, byte ptr [rdi]
movzx edx, byte ptr [rcx + hash.asso_values]
cdqe
add rax, rdx
cmp eax, 114
ja .LBB0_6
mov rbx, qword ptr [8*rax + in_word_set.wordlist]
cmp cl, byte ptr [rbx]
jne .LBB0_6
add rdi, 1
lea rsi, [rbx + 1]
call strcmp
test eax, eax
je .LBB0_7
.LBB0_6:
xor ebx, ebx
.LBB0_7:
mov rax, rbx
pop rbx
ret
这是一大堆代码,但具有合理数量的ILP.关键路径是通过3相关的存储器访问(查找char中值str- >查找散列值char的散列函数表- >查找在实际的哈希表的字符串),你可以期望这通常需要大约是20个周期(加上strcmp当然的时间).
这个问题的"经典"compsci解决方案是trie.对于你的问题,trie可能是一种合理的方法,特别是许多不成功的匹配可以在前几个字符内快速拒绝(这在很大程度上取决于匹配集的内容和你正在检查的字符串).
你需要一个快速的trie实现来完成这项工作.总的来说,我觉得这种方法会受到串行相关的内存访问的限制 - 每个节点都可能以一种指针追逐方式访问,因此你会受到大量的L1访问延迟的影响.
strcmp几乎所有上述解决方案都strcmp在某种程度上依赖- 例外是布隆过滤器允许误报.因此,您希望确保代码的这一部分速度很快.
特别是编译器有时会内联的"内置"的版本strcmp,而不是调用库函数:在快速测试icc做了内联,但clang并gcc选择调用库函数.没有一个简单的规则,哪个会更快,但一般来说,库例程通常是SIMD优化的,对于长字符串可能更快,而内联版本避免函数调用开销,对于短字符串可能更快.您可以测试这两种方法,并且主要强制编译器在您的情况下执行更快的操作.
更好的是,您可以利用对输入的控制来做得更好 - 如果您可以确保,例如,输入字符串将为空填充,使其长度为8的倍数,那么您可以对哈希表中的引用字符串(或任何其他结构)执行相同操作,并且可以一次比较字符串8个字节.这不仅极大地加速了匹配,而且还大大减少了分支误预测,因为它基本上量化了循环行为(1-8个字符的所有字符串循环一次,等等).
1这里我的意思是台式机,服务器,笔记本电脑CPU,甚至现代智能手机CPU,而不是嵌入式设备MCU或类似的东西.
2允许误报意味着即使输入字符串不在集合中,如果"处于设置中"有时也会返回true.请注意,它永远不会是错误的其他周围的方法:它总是当字符串返回true 是在设置-有没有假阴性.
3具体来说,awk 'NR%990==0' /usr/share/dict/american-english > words.
4例如,你strcmp在计算史上有多少次被称为？如果它甚至快1 ns,会节省多少时间？
5这在某种程度上将CPU时间与工程时间等同起来,工程时间可能超过1000倍:亚马逊AWS每小时的CPU时间收费为0.02美元,而优秀的工程师每小时可能需要50美元(第一个)世界).因此(非常粗略!)公制工程时间比CPU时间高出2500倍.所以也许你需要花费数十亿的电话才能获得10小时的工作才能获得回报......
Str*_*zel 15
在某种情况下判断哪种结构最快的最佳(也是唯一)方法是使用不同的数据结构对其进行基准测量.然后选择最快.
换句话说:衡量代码可以让您比那些认为自己太聪明而无法衡量的人更有优势.;)
对于你在问题中提到的100个元素这样的相当小的列表,你使用的结构/算法并没有多大区别,因为获得的时间可能是微不足道的 - 除非你的程序经常执行搜索.
除非您每秒进行数亿次搜索，否则您将无法辨别其中的差异。如果您每秒执行数亿次搜索，请尝试基数树。它的内存非常昂贵，但对于这么小的数据集来说，这应该不重要。
写完后，对其进行概要分析。