快速计算最大匹配数的算法

Question

问题：给定两组节点，求无重复的最大匹配数。

给定两组节点，获得最大数量的无重复匹配。 匹配的定义是 f(n1, n2) > t.

试图。

        private int CountMatches(ImmutableArray<Node> expectedNodes, ImmutableArray<Node> actualNodes)
        {
            var expectedCount = expectedNodes.Length;
            var actualCount = actualNodes.Length;
            var stacks = StackPool.Rent(expectedCount);
            var matches = MatchPool.Rent(actualCount);

            for (var index = 0; index < actualCount; index++)
            {
                matches[index] = Invalid;
            }

            for (var x = 0; x < expectedCount; x++)
            {
                var stack = stacks[x];

                if (stack == null)
                {
                    stack = stacks[x] = new Stack<int>(actualCount);
                }
                else
                {
                    stack.Clear();
                }

                for (var y = 0; y < actualCount; y++)
                {
                    if (GetNodeScore(expectedNodes[x], actualNodes[y]) > Threshold1)
                    {
                        stack.Push(y);
                    }
                }

                var currentX = x;

                while (stack.TryPop(out var y))
                {
                    var nextX = matches[y];
                    var nextStack = nextX != Invalid ? stacks[nextX] : null;

                    if (nextStack == null)
                    {
                        matches[y] = currentX;
                        break;
                    }

                    if (nextStack.Count == 0) continue;

                    matches[y] = currentX;
                    currentX = nextX;
                    stack = nextStack;
                }
            }

            var count = 0;

            for (var index = 0; index < actualCount; index++)
            {
                if (matches[index] != Invalid) count++;
            }

            StackPool.Return(stacks);
            MatchPool.Return(matches);

            return count;
        }

问题：

我正在做的项目对性能很关键 在对执行情况进行分析后 这个函数占了大部分的执行时间。 我的直觉是，应该有一个更直接的方法来直接获得计数，因为现在这个函数是计算节点元组，然后计数。 有没有更好的方法来计算最大匹配数，从而使平均执行速度更快？

更新一下。

• GetNodeScore 只是一个锯齿形数组的封装器。
• StackPool 和 MatchPool 是来自 ArrayPool<Stack<int>>.Shared 和 ArrayPool<int>.Shared

Answer 1

我在这个方法中发现了一个微优化，但能够通过更有选择性地调用它来更多地帮助性能。 它不是在最后迭代，而是在搜索过程中统计计数。

 private int CountMatches(ImmutableArray<Node> expectedNodes, ImmutableArray<Node> actualNodes)
    {
        const int invalid = -1;

        var count = 0;
        var m = expectedNodes.Length;
        var n = actualNodes.Length;
        var matches = ArrayPool<int>.Shared.Rent(n);
        var stacks = ArrayPool<Stack<int>>.Shared.Rent(m);

        for (var index = 0; index < n; index++)
        {
            matches[index] = invalid;
        }

        for (var x = 0; x < m; x++)
        {
            var stack = stacks[x] ??= new Stack<int>(n);

            stack.Clear();

            for (var y = 0; y < n; y++)
            {
                if (GetScore(expectedNodes[x], actualNodes[y]) > Threshold1)
                {
                    stack.Push(y);
                }
            }

            var currentX = x;

            while (stack.TryPop(out var y))
            {
                var nextX = matches[y];

                if (nextX == invalid)
                {
                    matches[y] = currentX;
                    count++;
                    break;
                }

                var nextStack = stacks[nextX];

                if (nextStack.Count == 0) break;

                matches[y] = currentX;
                currentX = nextX;
                stack = nextStack;
            }
        }

        ArrayPool<int>.Shared.Return(matches);
        ArrayPool<Stack<int>>.Shared.Return(stacks);

        return count;
    }