为什么将此代码段从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];
        }
    }
}

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

我已经深入研究了这一点,似乎在我的C++代码中,构造函数需要47秒,而使用F()中的树运行时间为48毫秒,这比C#快10倍.

结论

似乎主要问题在于insertSuffix(),也许是我对unordered_map结构缺乏了解和理解.任何人都可以对此有所了解吗？我是否在C++变体中犯了一些新手错误导致对象构造花了这么长时间？

有条件的信息

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

Answer 1

在C#中,System.String包含其Length,因此您可以在恒定时间内获取长度.在C++中,std::string还包括它的大小,因此它也可以在恒定时间内使用.

但是,您没有使用C++ std::string(对于算法的良好翻译,您应该使用C++ ); 你正在使用C风格的以null结尾的char数组.这char*字面意思是"指针char",而只是告诉你在哪里字符串的第一个字符是.该strlen函数char从指向前的那个查看每个函数,直到找到一个空字符'\0'(不要与空指针混淆); 这很昂贵,而且你在循环的每次迭代中都会这样做insertSuffix.这可能至少占你减速的一个合理部分.

在做C++时,如果你发现自己使用原始指针(任何涉及a的类型*),你应该总是想知道是否有更简单的方法.有时答案是"不",但通常是"是"(随着语言的发展,这种情况越来越普遍).例如,考虑你的struct node和node* root.两者都使用node指针,但在这两种情况下你都应该node直接使用,因为不需要那个间接(在这种情况下node,需要一定量的间接,所以你没有让每个节点无限地包含另一个节点,但那是提供std::unordered_map).

其他一些提示:

• 在C++中,您通常不希望在构造函数的主体中执行任何工作,而是使用初始化列表.
• 如果您不想复制作为参数传递的内容,则应将参数作为参考; 而不是insertSuffix改为将a std::string作为第一个参数,使其成为std::string const&; 同样,contains应该采取std::string const&.更好的是,既然insertSuffix可以看到该text成员,它根本不需要采用第一个参数就可以使用from.
• C++支持类似于foreach的构造,for在迭代字符串的字符时,您可能更喜欢使用标准循环.
• 如果你正在使用最新的非技术上最终但足够接近的C++,C++ 17版本,你应该使用std::string_view而不是std::string只需要查看字符串,而不需要更改它或者保持对它的引用.这将是有用的contains,因为你想在text成员中创建一个本地副本,即使对于构造函数也是如此; 它在text成员本身中没用,因为被查看的对象可能是临时的.但是,在C++中,有时候生命周期很棘手,直到你掌握了它,你可能只是想要std::string安全地使用它.
• 由于node在概念之外没有用suffixTree,它应该在它内部,就像在C#版本中一样.从C#版本的偏差,你可能想使类型node和数据成员root和text成private,而不是public成员.