Какие типы DataStructures могут включать параллельную обработку

Question

Двоичное дерево: Например, если нам нужно параллельно обрабатывать структуру данных дерева. Мы можем создать один поток для обработки левого узла, а другой поток для обработки правого узла. Теперь оба могут независимо работать в одной структуре данных.

Конечно, невозможно иметь такой же параллелизм для связанного списка.

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

Answer 1

Какой тип параллелизма?Вы всегда можете читать параллельно, но для записи это сложнее.Если единственное, что изменяется, это данные, хранящиеся в узле, то нет никаких причин, по которым вы не можете распараллелить LinkedList или Array, создав блокировку для каждого отдельного узла, а не для всего списка.Но если затронуты связи структуры, то есть о чем беспокоиться.

Ответ зависит от того, что вы пытаетесь сделать, и от того, как вы устанавливаете блокировки, условия и т. Д., Но ничто не является по своей сути распараллеливаемым или распараллеливающимся.

Answer 2

Когда вы говорите о параллельной обработке, мне приходят в голову две вещи: 1) Параллелизм задач 2) Параллелизм данных.Я расскажу о втором здесь.

Проверьте расширенный набор деревьев: Графики.Многие огромные проблемы с данными, основанные на Мудрости Толпы / Коллективном Разуме, могут быть смоделированы как График.Вам будет интересно пройти параллельную обработку Graph с использованием инфраструктуры Map Reduce.