0

前段时间我发布了一个关于从磁盘保存/检索后缀树的问题。终于可以正常工作了，但是现在构造非常缓慢，我现在不想弄乱 Ukkonen 算法（线性构造）。

因此，我想进行并发插入以加速该过程，而不必使树线程安全。

后缀树按其初始字符存储单词（看我上一个问题上发布的图像），因此，单词 Banana 位于根节点的“B”子节点中，Apple 将位于“A”子节点中，依此类推. 因此，插入以“B”开头的单词永远不会干扰以“A”开头的插入。我的想法是为要插入的单词集的每个初始字符都有一个线程：一个线程插入'A'，另一个线程插入'B'，等等。

所以我在考虑一个Executer类，它只是将单词添加到每个单词的队列中 Process（如果它不存在，首先创建它）。

class Executer:
    #...
    def concurrent_insertion(word):
        k = word[0]
        processes.get(k, Process()).add(word)
    # ...

类Process是进行插入的类。每个Process实例都是一个独立的线程，其中Queue包含仍然需要插入的单词。

在这个Process类中我遇到了麻烦，我猜它应该继承自threading.Thread，因为每个实例都应该是一个线程，但是在所有文本处理完成之前我如何让它保持活力呢？我的意思是，它应该从它Queue的单词中插入单词，但是当Queue为空时，线程不应该死，只是继续等待，直到更多的单词填充Queue，“唤醒”并继续插入。

4

1 回答 1

2

线程在退出之前不会死亡，因此您可以通过while True循环使它们保持活力。

通常的模式如下所示：

q = Queue.Queue()             # word insertion queue
terminate = object()          # sentinel value to tell a thread to terminate

def worker(q):
    while True:
         word = q.get()       # block until next word is available
         if word is terminate:
             break
         insert_word(word)

启动worker并发送消息到队列后，主线程需要等待所有工作完成，然后它应该关闭worker。

for word in wordlist:
    q.put(word)
for i in range(numthreads):
    q.put(terminate)          # terminate all the worker threads
for t in threadlist:
    t.join()                  # wait for them all to finish

等待所有工作完成的另一种方法是使用q.task_doneand q.join。队列模块文档的页面底部显示了如何使用它们的示例。

于 2011-12-10T16:49:32.560 回答