c# - 为什么将此代码片段从 C# 转换为 C++ 会降低性能？

Question

我对C#比C++熟悉得多，所以我必须就这个问题寻求建议。我不得不将一些代码片段重写为 C++，然后(令人惊讶地)遇到了性能问题。

我已将问题缩小到这些片段:

C#

   public class SuffixTree
    {
        public class Node
        {
            public int Index = -1;
            public Dictionary<char, Node> Children = new Dictionary<char, Node>();
        }

        public Node Root = new Node();
        public String Text;

        public SuffixTree(string s)
        {
            Text = s;
            for (var i = s.Length - 1; i >= 0; --i)
                InsertSuffix(s, i);
        }

        public void InsertSuffix(string s, int from)
        {
            var cur = Root;
            for (int i = from; i < s.Length; ++i)
            {
                var c = s[i];
                if (!cur.Children.ContainsKey(c))
                {
                    var n = new Node() { Index = from };
                    cur.Children.Add(c, n);

                    return;
                }
                cur = cur.Children[c];
            }
        }

        public bool Contains(string s)
        {
            return FindNode(s) != null;
        }

        private Node FindNode(string s)
        {
            var cur = Root;
            for (int i = 0; i < s.Length; ++i)
            {
                var c = s[i];
                if (!cur.Children.ContainsKey(c))
                {
                    for (var j = i; j < s.Length; ++j)
                        if (Text[cur.Index + j] != s[j])
                            return null;
                    return cur;
                }
                cur = cur.Children[c];
            }
            return cur;
        }
    }
}

C++

struct node
{
    int index;
    std::unordered_map<char, node*> children;

    node() { this->index = -1; }
    node(int idx) { this->index = idx; }
};

struct suffixTree
{
    node* root;
    char* text;

    suffixTree(char* str)
    {
        int len = strlen(str) + 1;
        this->text = new char[len];
        strncpy(this->text, str, len);

        root = new node();
        for (int i = len - 2; i >= 0; --i)
            insertSuffix(str, i);
    }

    void insertSuffix(char* str, int from)
    {
        node* current = root;
        for (int i = from; i < strlen(str); ++i)
        {
            char key = str[i];
            if (current->children.find(key) == current->children.end())
            {
                current->children[key] = new node(from);
                return;
            }
            current = current->children[key];
        }
    }

    bool contains(char* str)
    {
        node* current = this->root;
        for (int i = 0; i < strlen(str); ++i)
        {
            char key = str[i];
            if (current->children.find(key) == current->children.end())
            {
                for (int j = i; j < strlen(str); ++j)
                    if (this->text[current->index + j] != str[j])
                        return false;
                return true;
            }
            current = current->children[key];
        }
    }
}

在这两种情况下，我都创建了一个后缀树，然后在一个与帖子无关的更大的函数中使用它(我们称之为 F())。我已经在两个随机生成的长度为 100000 的字符串上进行了测试。C# 版本构建了我的后缀树并在 F() 中使用它，总执行时间为:480 ms 而我的代码'在 48 秒

内执行“翻译成 C++”

我对此进行了深入研究，似乎在我的 C++ 代码中，构造函数花费了 47 秒，而在 F() 中使用树的运行时间为 48 毫秒这比在 C# 中快 10 倍。

结论

看来主要问题出在insertSuffix()，可能是我对unordered_map结构的认识和理解不够。任何人都可以阐明这一点吗？我是否在 C++ 变体中犯了一些菜鸟错误导致对象构造花费这么长时间？

附加信息

我已经为最大速度编译了 C# 和 C++ 程序/O2(发布)

Answer 1

在 C# 中，一个 System.String包括它的 Length , 所以你可以得到恒定时间内的长度。在 C++ 中，一个 std::string 还包括其 size , 所以它在常数时间内也是可用的。

但是，您没有使用 C++ std::string (为了算法的良好翻译，你应该这样做)；你正在使用 C-style null-terminated char array .那char*字面意思是“指向char的指针” ", 只是告诉你字符串的第一个字符在哪里。 strlen 函数查看每个 char从指向的那个开始，直到找到一个空字符 '\0' (不要与 null pointer 混淆)；这很昂贵，并且您在 insertSuffix 中的循环的每次迭代中都这样做.这可能至少占了您减速的合理部分。

在使用 C++ 时，如果您发现自己使用原始指针(任何涉及 * 的类型)，您应该总是想知道是否有更简单的方法。有时答案是“否”，但通常是"is"(随着语言的发展，这种情况变得越来越普遍)。例如，考虑您的 struct node和 node* root .两者都使用 node指针，但在这两种情况下你都应该使用 node直接是因为不需要间接寻址(在 node 的情况下，一些 数量的间接寻址是必要的，因此您不会让每个节点都包含另一个节点 ad infinitum，但这是由 std::unordered_map 提供的)。

---

其他一些提示:

• 在 C++ 中，您通常不想在构造函数的主体中做任何工作，而是使用 initialization lists .
• 当您不想复制作为参数传递的内容时，您应该将参数设为引用；而不是改变 insertSuffix采取std::string作为第一个参数，让它取 std::string const& ;同样，contains应该采取 std::string const& .更好的是，因为 insertSuffix可以看到text成员，它根本不需要采用第一个参数，只需使用 from 即可.
• C++ 支持 foreach-like construct ，你应该更喜欢标准 for在遍历字符串的字符时循环。
• 如果您使用的是最新的 C++ 版本，C++17，技术上尚未最终确定，但已经足够接近，您应该使用 std::string_view而不是 std::string每当您只想查看一个字符串，而不需要更改它或保留对它的引用时。这对 contains 很有用, 因为你想在 text 中制作一个本地拷贝成员，甚至是构造函数；它在 text 中没有用成员本身，因为正在查看的对象可能是临时的。不过，在 C++ 中，生命周期有时会很棘手，在您掌握它之前，您可能只想使用 std::string。为了安全起见。
• 自 node在 suffixTree 的概念之外没有用，它可能应该在其中，就像在 C# 版本中一样。作为与 C# 版本的偏差，您可能希望创建类型 node和数据成员 root和 text进入private而不是 public成员。