Как пройти бинарное дерево потокобезопасным способом?

Question

Мне нужен способ обхода двоичного дерева, используя несколько потоков и сохраняя элементы, которые соответствуют критериям, в список. Как мне это сделать потокобезопасным способом?

Answer 1

Как указывает SDG, ответ во многом зависит от точного характера вашей проблемы.Если вы хотите декомпозировать обход (т. Е. Проходить параллельно), вы можете иметь потоки, действующие на разные поддеревья после, скажем, уровня 2. Затем каждый поток может добавить свой собственный список, который затем можно объединить / объединить в точке соединения.,Самое простое, что нужно сделать - это предотвратить моды на дереве во время обхода.

Я просто должен добавить, что вы не продолжаете разжигать нити после достижения своего уровня.Вы делаете это только один раз.Таким образом, на уровне 2 вы стреляете максимум из 4 потоков.Каждая путевая нить обрабатывает свое поддерево как свое корневое дерево.Вы также не сделаете этого, если у вас нет стыковой нагрузки на узлы и достаточно сбалансированное дерево.Buttload - это технический термин, означающий «мера».Часть прохождения до точки разделения пересекается потоком пользовательского интерфейса.Если бы это была моя проблема, я бы долго и усердно думал о том, чего именно мне нужно было достичь, поскольку это может иметь все значение.

Позвольте мне добавить еще одну вещь (это становится эскизом Монти Пайтона?),Вам на самом деле не нужно объединять или объединять списки результатов в новый список, если все, что вам нужно, это обработать результаты.Даже если вам нужны упорядоченные результаты, все равно лучше отсортировать каждый список отдельно (возможно, параллельно), а затем «объединить» их методом извлечения GetNextItem.Таким образом, вам не нужно много дополнительной памяти.Таким способом вы можете объединить 4 списка одновременно, имея два «буфера» (могут быть указатели / индексы для фактических записей).Я пытаюсь найти способ объяснить это без рисования картинки.

                     0 1 2 3 4 5 6 7 8 9   

             L1(0):  4 4 4 5 5 6 8 
    B1[L2,3]        \  
             L2[1]:  3 4 5 5 6 7 7 8 9
 \   
             L3[1]:  2 2 4 4 5 5 6 8 
    B2[L3,2]          /
             L4[0]:  2 4 5 5 6 7 7 8 9

Вы продолжаете тянуть из того списка, который удовлетворяет нужному вам порядку.Если вы извлекаете данные из B2, вам нужно только обновить B2 и его подсписки (в этом случае мы извлекли 2 из L3 и перенесли индекс L3 в следующую запись).

Answer 2

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

Если у вас много читателей и меньше писателей, вы можете использовать ReaderLocks и WriterLocks, чтобы разрешить одновременный поиск, но полностью заблокировать мутации.

Если вы хотите что-то более мелкозернистое, это будет намного сложнее. Вам нужно определить, что вам действительно нужно, из «безопасности потока», вам, возможно, придется сократить API двоичного дерева, и вам, вероятно, придется блокировать узлы индивидуально, возможно, на время обхода поддерева.

Answer 3

Вы упускаете несколько моментов, которые помогут с ответом.

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

Когда вы ослабите любое из этих ограничений, вам нужно будет либо добавить блокировку, либо другие соответствующие средства, чтобы убедиться, что они хорошо играют вместе.