1

我的 ConsoleApplication 从输入生成正确的 AVL 树。对于我的大学，我需要制定一个程序：

  • 在 AVL 树中正确插入数据
  • 保持平衡
  • 给输出足够快和正确的某些输入

我的问题是为什么我在本主题后面介绍的程序的方法/部分如此缓慢（96% 的总时间程序运行）？

我的程序中也使用 treewalks 的其他方法/部分大约占我程序的 0.05% 或更少

我将解释部分/方法“树中节点的等级”，根据 DotTrace（分析工具），此方法占我整个程序的 96%（所有其他方法大约占 0.05% 或更少）。这就是为什么我在使用 dumjudge 系统提交作业时会获得 timeLimit 的原因。

  • 如果输入行以 T 开头：在 AVL 树中插入新节点

  • 如果输入行以 G 开头：指定节点排名的 derterminate 排名是得分高于您的人数 +1 比使用 Console.Writeline(variable) 的输出；

    例子：

  • 节点值：x(10) y(5) z(2) k(5) l(4) m(9)

  • 节点等级：X(1) y(3) z(6) k(3) l(5) m(2)

  • 如果输入行以其他内容开头：无需解释这部分工作正常

我已经尝试了很多东西，但我不明白为什么它会变慢我希望你们能帮助我，让我看看我做错了什么。

变量：

  • MyAVLTree T：包含 AVL 树的根
  • MyNode NodeX，包含我们要从中确定排名的节点
  • Int compareVALue，是 nodeX 的值，我们将其与其他节点进行比较以确定它是更高（counter++）还是更低（什么都不做）

当没有比 nodeX 更高的节点时，该方法将返回包含节点等级的计数器变量，以便可以将其打印为输出。

在 AVL 树中产生输出或插入数据的所有输入行大约占我程序的 0.05% 或更少……除了我的程序中产生/返回 AVL 树中节点等级的方法/部分（96%）

我希望我的代码是可读的，在此先感谢您的帮助和时间。

 public static int RankElement(MyAVLTree T, MyNode nodeX, int compareValue)
    {
        int counter = 1;

        while (true)
        {
            if (nodeX == T.root)
            {
                UnkownTreeWalk(T, nodeX.Right, compareValue, ref counter);
                return counter;
            }
            else if (nodeX == nodeX.Parent.Right)
            {
                UnkownTreeWalk(T, nodeX.Right, compareValue, ref counter);

                while (nodeX == nodeX.Parent.Right)
                {
                    nodeX = nodeX.Parent;
                    if (nodeX == T.root)
                    {
                        return counter;
                    }
                }
                nodeX = nodeX.Parent;
                if (nodeX.playerScore > compareValue)
                    counter++;
            }
            else
            {
                UnkownTreeWalk(T, nodeX.Right, compareValue, ref counter);

                nodeX = nodeX.Parent;
                if (nodeX.playerScore > compareValue)
                    counter++;
            }
        }


    }

    public static void UnkownTreeWalk(MyAVLTree T, MyNode nodeX, int compareValue, ref int counter)
    {
        if (nodeX != null)
        {
            if (nodeX.playerScore > compareValue)
            {
                counter++;
            }
            UnkownTreeWalk(T, nodeX.Right, compareValue, ref counter);

            UnkownTreeWalk(T, nodeX.Left, compareValue, ref counter);
        }
    }
4

1 回答 1

1

有三件事要调查。

首先，您有一些我认为不必要的条件。在 UnknownTreeWalk 中，我们检查节点的值是否小于 compareValue。然而， compareValue 是初始节点的值，当我们调用 UnknownTreeWalk 时，我们总是在该初始节点的右侧。向右意味着它的值更大，所以检查是不必要的。您可以进行一些类似的微小更改以使事情变得更快捷。

其次，您可能有很多 CPU 缓存未命中。您可以尝试安排您的 TreeNode 在内存中连续排列。在您的情况下，这可能没什么大不了的。

第三，也是最重要的一点，我怀疑你会花很多时间在树上跑来跑去，研究它们的大小。您可以将每个子树的大小保留在它的 MyNode 对象中，然后只需查阅它，而不是到处计算。这就是我认为最有可能让你快速到达需要的地方。

最后，Rank 的实现可能要简单得多。我鼓励你从这个实现中学到关于这个问题的知识，然后写一个新的，考虑这些知识并计算这个节点右侧的所有节点。

于 2012-08-03T10:57:37.497 回答