Параллельные вставки в Суффикс-дерево

Question

Некоторое время назад я опубликовал вопрос о сохранении / извлечении дерева суффиксов с диска. Это, наконец, работает нормально, но сейчас строительство идет очень медленно, и я не хочу сейчас связываться с алгоритмом Укконена (линейная конструкция).

Итак, я хотел сделать параллельные вставки, чтобы ускорить процесс, не делая дерево безопасным для потоков.

Дерево суффиксов хранит слова по своему начальному символу (см. Изображение, опубликованное на моем предыдущем вопросе ), таким образом, слово Banana находится в дочернем элементе «B» корневого узла, и Apple будет у ребенка "А" и так далее. Таким образом, вставка слова, начинающегося с «B», никогда не будет мешать вставке, начинающейся с «A». Моя идея состоит в том, чтобы иметь нить для каждого начального символа из набора вставляемых слов: нить, вставляющая «А», другая нить, вставляющая «В» и т. Д.

Итак, я думал о 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, "разбудить" и продолжить вставку.

Answer 1

Потоки не будут умирать, пока они не выйдут, поэтому вы можете сохранить их с помощью петли 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)

После запуска рабочих и отправки слов в очередь основной поток должен дождаться завершения всей работы, а затем долженостановите рабочих.

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_done и q.join.Пример их использования показан внизу страницы в документах для модуля очереди .