9

因为 trie 数据结构具有如此巨大的分支因子，并且每个子树完全独立于其他子树，所以似乎应该有一种方法可以通过并行添加所有单词来极大地加快给定字典的 trie 构建速度。

我对如何做到这一点的最初想法如下：将互斥锁与 trie 中的每个指针（包括指向根的指针）相关联，然后让每个线程遵循将单词插入到 trie 中的正常算法。但是，在跟踪任何指针之前，线程必须首先获取该指针上的锁，这样如果它需要向 trie 添加一个新的子节点，它就可以在不引入任何数据竞争的情况下这样做。

这种方法的问题是它使用了大量的锁——一个用于 trie 中的每个指针的锁——并且进行了大量的获取和释放——一个用于每个输入字符串中的每个字符。

有没有办法在不使用几乎一样多的锁的情况下并行构建一个 trie？

4

4 回答 4

9

一个明显的无锁算法是：

  1. 按长度为k的前缀对输入字符串进行桶排序（通常k =1，但对于小字母，增加k）。
  2. 对于每个字母，构造一个包含以该字母开头的所有字符串的k后缀的 trie。
  3. 合并上一步的尝试（当k =1 时，只需添加一个根节点）。

假设前缀分布均匀，这可以为您提供高达字母表大小的k次幂的线性加速。

于 2013-01-15T17:09:06.770 回答
4

我突然想到，这可以通过对指针使用原子测试和设置操作而不是锁来实现无锁。具体来说，如果一个线程想要跟随一个指针，它会执行以下操作：

  1. 原子读取指针值。
  2. 如果指针非空，则跟随它。你完成了。
  3. 否则，分配一个新节点。
  4. 原子地测试指针是否为空，如果为空，则将其设置为新节点。
  5. （备注：这里的指针肯定是非空的。要么我们只是设置了它，要么它是由另一个线程设置的）。
  6. 跟随指针。

根据硬件，这可能会快得多，因为它避免了一直锁定和解锁的工作，并确保没有线程无限期地等待。

一个缺点是涉及的分配数量增加了，因为多个线程可能都尝试分配一个节点以在特定位置放入 trie，但只有一个可以将它放在那里。幸运的是，可以通过以下优化来缓解这种情况：如果一个线程不必要地分配了一个节点，而不是立即释放它，它只是将节点存储在临时空间中。如果稍后它需要分配一个新节点，它可以使用缓存的节点。如果没有，它可以在最后释放它。

希望这可以帮助！

于 2013-01-15T17:08:17.197 回答
1

好吧，在为一组节点（而不是一个）设置锁定的细粒度与粗粒度之间存在明显的权衡。

一个简单的方法是通过散列 - 拥有m不同的锁，并且对于您要访问的每个节点获取编号为 的锁hash(node) % m。
请注意，这种方法基本上是建议方法（使用完美散列和n == m）和串行方法（使用m == 1）的概括。

可以利用的另一件事是乐观设计- 如果该方法实际上会提高性能，当然取决于字典的分布和特里树的大小，如果冲突往往非常罕见（这可能是很长单词的字典的情况）。
这个想法是在没有任何同步的情况下将单词添加到树中，如果遇到冲突 - 回滚到最后一个已知的稳定状态（这当然需要对数据进行快照，如果我们这样做可能是不可行的谈论无法存储的数据流）。

于 2013-01-15T16:55:29.403 回答
1

根据您的字典的外观，如果您可以让每个线程构建独立的子树，您可能根本不需要锁。如果这不是在线算法，请按前缀对单词进行预排序（如果您有 < 26 个线程，则为第一个字母，如果您有更多或您知道数据不平衡，则为第一个和第二个，例如，90% 的词从 A) 开始。基本上，这将是一个 O(n) 操作，您执行一次计算以计算有多少以给定字母开头的单词，然后执行一次排序（按照您选择的前缀进行基数排序）。然后，划分线程之间的前缀，让每个线程构建这些独立的子树。最后，让一个线程将这些子树中的每一个添加到根。我将在下面介绍一个示例。

您的词典：
Bark
Apple
Cookie
和
Baby
Corn
Blue
Cake
Bacon

排序后：
苹果
和
树皮
婴儿
蓝
培根
玉米
饼干
蛋糕

然后我们在线程之间划分前缀。对于此示例，我们有 3 个线程，它们获取前缀 [A][B][C]，并构建以下树：

一个--| 乙--------| C --------|    
PN |-- A ---| 洛---| 一种
PDRBCUORK
乐视网
埃尼
                                   乙

然后你有一个线程在根处将这些组合起来，例如：

|----------- 根目录------|
一个--| 乙--------| C --------|    
PN |-- A ---| 洛---| 一种
PDRBCUORK
乐视网
埃尼
                                   乙

我希望这是有道理的。

这种方法的优点：线程基本上独立工作，您不必处理获取和释放锁的开销。

这种方法的缺点：如果您对字典一无所知，可能会出现严重的工作负载不平衡，并且在最坏的情况下（例如，所有单词都以“A”开头）它会恢复为基本上是单线程构建一颗树。有几种方法可以使这更好，例如，您可以在排序时添加一些检查，这样如果在处理单个字母前缀时工作量严重不平衡，则可以使用前 2 个字母，但实际上您可以t保证它将是平衡的。

如果假设您有 20 个线程并按第一个字母排序，那么您有时也可能有空闲线程，那么您将有大约 6 个线程必须执行两个子树，而其中 14 个线程在一半时间内处于空闲状态。您也许可以进一步细分子树来处理这个问题，但这是在预处理步骤上花费的额外时间。

Anyway, no guarantees that this is faster than your method, but its something to consider.

于 2013-01-15T17:31:55.950 回答