tem*_*def 9 string algorithm parallel-processing trie data-structures
因为trie数据结构具有如此巨大的分支因子,并且每个子树完全独立于其他子树,所以似乎应该有一种方法通过并行添加所有单词来极大地加速给定字典的构造.
我关于如何执行此操作的初步想法如下:将互斥锁与trie中的每个指针相关联(包括指向根的指针),然后让每个线程遵循用于将单词插入到trie中的常规算法.但是,在遵循任何指针之前,线程必须首先获取该指针的锁定,以便在需要向trie添加新的子节点时,它可以在不引入任何数据争用的情况下执行此操作.
这种方法的缺点是它使用了大量的锁 - 一个用于trie中的每个指针 - 并且执行大量的获取和释放 - 每个输入字符串中的每个字符一个.
有没有办法在没有使用几乎同样多的锁的情况下并行构建一个trie？
一个明显的无锁算法是:
假设前缀的均匀分布,这可以为您提供线性加速,最大可达字母到功率k的大小.