遍历状态模式

引言

TraversalStatePattern 模式可用于识别**已处理的实体**，而无需额外的 **集合**，并在完成完整或部分遍历后重置 IsProcessed **标志**，从而无需再次迭代所有节点来清除该标志。它可用于图遍历或处理其他类型的实体。

背景

其思想是在每个 Node 中包含一个 **整数状态** 值，以及一个用于与 Node 的状态进行比较的 **全局整数状态**，以 **确定** **节点是否已被处理**。Node 的状态值将被设置为全局值以 **标记为已处理**。在每次遍历之前，我们递增全局状态数字，这有效地在遍历之前将所有节点重置为未处理状态。

示例场景

我们想要应用模式的图节点示例

/// <summary>
/// This class contains all logic and data related to its basic functionality
/// </summary>
public partial class ExampleNode
{
    public readonly int Value;

    #region Graph hierarchy
    private readonly List<ExampleNode> _children = new();
    public IReadOnlyList<ExampleNode> Children => _children;

    public void AddChild(ExampleNode child)
    {
        _children.Add(child);
    }
    #endregion
}

模式代码

通过使用 partial class，我们可以将所有模式逻辑移至单独的文件

/// <summary>
/// This class contains all pattern members necessary to implement TraversalStatePattern
/// </summary>
public partial class ExampleNode
{
    private static int _globalTraversalState;
    private int _nodeTraversalState = -1;//set to -1 to not be IsProcessed() by default
   
    public static void NewTraversal()
    {
        _globalTraversalState++;
    }

    public void MarkProcessed()
    {
        _nodeTraversalState = _globalTraversalState;
    }

    public bool IsProcessed() => _nodeTraversalState == _globalTraversalState;
}

我们可以将 MarkProcessed() 和 IsProcessed() 方法合并为一个。它只会在使用第一次时返回 'True'

public bool CheckSetProcessed()
{
    if (_nodeTraversalState == _globalTraversalState) //check is processed
        return true;
    _nodeTraversalState = _globalTraversalState;

    return false;
}

模式用法

示例图遍历方法

public void GraphTraversal(ExampleNode root, Action<ExampleNode> procedure)
{
    //Start a new traversal. Now method CheckSetProcessed() in all nodes
    //will return False after this
    ExampleNode.NewTraversal();
    
    var queue = new Queue<ExampleNode>();//Using Queue for BFS 
                                         //(or Stack can be used for DFS traversal)

    //process start node
    queue.Enqueue(root);
    root.CheckSetProcessed();

    while (queue.TryDequeue(out var node))
    {
        foreach (var resultChild in node.Children)
        {
            //Use status pattern
            if (resultChild.CheckSetProcessed())
            {
                continue;//skip node that has been already processed
            }

            //Do some work
            procedure(resultChild);

            //process node children
            queue.Enqueue(resultChild);
        }
    }
}

多线程用法

对于多线程处理，我们应该稍微修改一下代码

public partial class ExampleNode
{
    private static int _globalTraversalState;
    private int _nodeTraversalState = -1;

    public static void NewTraversal()
    {
        _globalTraversalState++;
    }

    public bool CheckSetProcessed()
    {
        var newState = Interlocked.Exchange
                       (ref _nodeTraversalState, _globalTraversalState);

        //if the original value was now equal to global, then node was not processed
        return newState == _globalTraversalState;
    }
}

以下是如何在多线程运行的代码中使用它的示例。我使用了 BackgroundWorkers，但你可以使用其他方法，如 Tasks

public void GraphTraversal(
    ExampleNode root,
    Action<ExampleNode> procedure,
    int threads,
    int nodes)
{
    ExampleNode.NewTraversalMultithreaded(); //Start a new traversal. 
                                             //Now all nodes IsProcessed() will give False

    //Do multithreaded traversal
    var waitEvent = new CountdownEvent(threads);

    var processingBC = new BlockingCollection<ExampleNode> { root };

    for (var i = 0; i < threads; i++)
    {
        var worker = new BackgroundWorker();

        worker.DoWork += (_, _) =>
        {
            foreach (var exampleNode in processingBC.GetConsumingEnumerable())
            {
                procedure(exampleNode);//process node

                if (Interlocked.Decrement(ref nodes) == 0)
                    processingBC.CompleteAdding();

                foreach (var child in exampleNode.Children)
                {
                    if (child.CheckSetProcessedMultithreaded())
                    {
                        continue;//skip node that has been already processed
                    }

                    processingBC.Add(child);
                }
            }
        };

        worker.RunWorkerCompleted += (_, _) =>
        {
            waitEvent.Signal();
            worker.Dispose();
        };
        worker.RunWorkerAsync();
    }

    waitEvent.Wait();
}

并行多线程用法

(并行多线程意味着对同一结构进行多次并发迭代，其中每次迭代都使用多线程运行。)

Git 仓库 包含一个并行、多线程的示例，说明如何使用它，但基准测试表明它比使用 ConcurrentDictionary 快 5-10%。ConcurrentDictionary 方法。

不使用额外集合的并行多线程方法，带有位操作和 64 个并行操作的限制：ParallelStatePatternGraphTraversal.cs

NodeParallelUtils.cs（提供线程遍历上下文以跟踪标志位）。

历史

• 2023年12月3日：初始版本