|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Mike Roschin 2:5030/243.1 05 Oct 2002 22:54:01
To : Gennady Mayko
Subject : Алгоритм параллельного обхода дерева
--------------------------------------------------------------------------------
щTo All written 01.Oct.2002, 11:27
Ave Gennady Mayko!
GM> Есть некоторое дерево, точная структура его не известна. Какие есть
GM> алгоритмы полного обхода дерева
ВОзможно, что я чего-то не понимаю, но IMHO есть один-единствный способ обхода
дерева: взался за корешок -> обошел левую ветку -> обошел правую ветку.
Hебольшие нюансы - непринципиальны.
GM> с использованием нескольких потоков (процессоров)?
GM> Количество узлов дерева гораздо больше, чем количество потоков,
GM> которые практически можно создать.
PROCEDURE ОбходДерева ( КорневойУзел : УзелДерева );
BEGIN
ВыполнитьОперациюHадУзлом ( КорневойУзел );
IF ЕстьСвободныйПроцесс THEN
ЗапуститьПроцесс ( ОбходДерева ( КорневойУзел->Левое ) );
ELSE
ОбходДерева ( КорневойУзел->Левое );
END;
IF ЕстьСвободныйПроцесс THEN
ЗапуститьПроцесс ( ОбходДерева ( КорневойУзел->Правое ) );
ELSE
ОбходДерева ( КорневойУзел->Правое );
END;
END ОбходДерева;
Примерно так. В рельности придется добавить массу приседаний для
взаимоувязывания процессов, как то: обеспечить реентерабельность процедур
обработки, локнуть обращение к разделяемым ресурсам, в зависимости от
организации мультитридовой надстройки согласовать проверку наличных пустых
тридов и запуск нового трида.
Get Warped 3.0! \\Thesis
---
* Origin: Слоны по деревьям не лазают! \\The Oxygen. (2:5030/243.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Алгоритм параллельного обхода дерева 