.Net 4

Question

में इस विशाल प्रदर्शन अंतर के पीछे क्या कारण है मैं रेडब्लैक ट्री पर कुछ शोध कर रहा था। मुझे पता था कि .NET 4.0 में सॉर्टेडसेट क्लास रेडब्लैक पेड़ का उपयोग करता है। इसलिए मैंने उस भाग को प्रतिबिंबित करने के रूप में लिया और एक रेडब्लैक ट्री क्लास बनाया।

RBTree took 9.27208 sec to insert 40000 values 
SortedSet took 0.0253097 sec to insert 40000 values 

कारण क्या है: अब मैं इस पर कुछ RedBlackTree पर्फ़ परीक्षण चल रहा हूँ और SortedSet 40000 अनुक्रमिक अभिन्न मान (0 से 39999 करने के लिए शुरू) डालने, मैं वहाँ विशाल पर्फ़ अंतर यह है कि देखने के लिए इस प्रकार है चकित हूँ इसके पीछे? BTW मैं रिलीज विन्यास केवल में परीक्षण भाग गया और यहां छोटे से परीक्षण कोड

  var stopWatch = new Stopwatch(); 
      var rbT = new RedBlackTree<int>();  
     stopWatch = new Stopwatch(); 
     stopWatch.Start(); 
     for (int i = 0; i < 40000; i++) { 
      rbT.Add(i); 
     } 
     stopWatch.Stop(); 
     Console.WriteLine(stopWatch.Elapsed); 

     var ss = new SortedSet<int>(); 
     stopWatch = new Stopwatch(); 
     stopWatch.Start(); 
     for (int i = 0; i < 40000; i++) { 
      ss.Add(i); 
     } 
     stopWatch.Stop(); 
     Console.WriteLine(stopWatch.Elapsed); 

संपादित

है

मैं RBTree के लिए कोड भी इतना है कि आप भी चला सकते हैं कि मैं क्या निकाला है साझा करना चाहते हैं निदान

public class Node<T> 
    { 
     public Node(){} 

     public Node(T value) 
     { 
      Item = value; 
     }  

     public Node(T value, bool isRed) 
     { 
      Item = value; 
      IsRed = isRed; 
     } 

     public T Item; 
     public Node<T> Left; 
     public Node<T> Right; 
     public Node<T> Parent; 
     public bool IsRed; 
    } 

    public class RedBlackTree<T> 
    { 
     public RedBlackTree(){} 

     public Node<T> root; 
     int count, version; 
     Comparer<T> comparer = Comparer<T>.Default;  

     public void Add(T item) 
     { 
      if (this.root == null) 
      { 
       this.root = new Node<T>(item, false); 
       this.count = 1; 
       this.version++; 
       return; 
      } 

      Node<T> root = this.root; 
      Node<T> node = null; 
      Node<T> grandParent = null; 
      Node<T> greatGrandParent = null; 
      this.version++; 

      int num = 0; 
      while (root != null) 
      { 
       num = this.comparer.Compare(item, root.Item); 
       if (num == 0) 
       { 
        this.root.IsRed = false; 
        return; 
       } 
       if (Is4Node(root)) 
       { 
        Split4Node(root); 
        if (IsRed(node)) 
        { 
         this.InsertionBalance(root, ref node, grandParent, greatGrandParent); 
        } 
       } 
       greatGrandParent = grandParent; 
       grandParent = node; 
       node = root; 
       root = (num < 0) ? root.Left : root.Right; 
      } 
      Node<T> current = new Node<T>(item); 
      if (num > 0) 
      { 
       node.Right = current; 
      } 
      else 
      { 
       node.Left = current; 
      } 
      if (node.IsRed) 
      { 
       this.InsertionBalance(current, ref node, grandParent, greatGrandParent); 
      } 
      this.root.IsRed = false; 
      this.count++; 
     } 


     private static bool IsRed(Node<T> node) 
     { 
      return ((node != null) && node.IsRed); 
     } 

     private static bool Is4Node(Node<T> node) 
     { 
      return (IsRed(node.Left) && IsRed(node.Right)); 
     } 

     private static void Split4Node(Node<T> node) 
     { 
      node.IsRed = true; 
      node.Left.IsRed = false; 
      node.Right.IsRed = false; 
     } 

     private void InsertionBalance(Node<T> current, ref Node<T> parent, Node<T> grandParent, Node<T> greatGrandParent) 
     { 
      Node<T> node; 
      bool flag = grandParent.Right == parent; 
      bool flag2 = parent.Right == current; 
      if (flag == flag2) 
      { 
       node = flag2 ? RotateLeft(grandParent) : RotateRight(grandParent); 
      } 
      else 
      { 
       node = flag2 ? RotateLeftRight(grandParent) : RotateRightLeft(grandParent); 
       parent = greatGrandParent; 
      } 
      grandParent.IsRed = true; 
      node.IsRed = false; 
      ReplaceChildOfNodeOrRoot(greatGrandParent, grandParent, node); 
     } 

     private static Node<T> RotateLeft(Node<T> node) 
     { 
      Node<T> right = node.Right; 
      node.Right = right.Left; 
      right.Left = node; 
      return right; 
     } 

     private static Node<T> RotateRight(Node<T> node) 
     { 
      Node<T> left = node.Left; 
      node.Left = left.Right; 
      left.Right = node; 
      return left; 
     } 

     private static Node<T> RotateLeftRight(Node<T> node) 
     { 
      Node<T> left = node.Left; 
      Node<T> right = left.Right; 
      node.Left = right.Right; 
      right.Right = node; 
      left.Right = right.Left; 
      right.Left = left; 
      return right; 
     } 

     private static Node<T> RotateRightLeft(Node<T> node) 
     { 
      Node<T> right = node.Right; 
      Node<T> left = right.Left; 
      node.Right = left.Left; 
      left.Left = node; 
      right.Left = left.Right; 
      left.Right = right; 
      return left; 
     } 

     private void ReplaceChildOfNodeOrRoot(Node<T> parent, Node<T> child, Node<T> newChild) 
     { 
      if (parent != null) 
      { 
       if (parent.Left == child) 
       { 
        parent.Left = newChild; 
       } 
       else 
       { 
        parent.Right = newChild; 
       } 
      } 
      else 
      { 
       this.root = newChild; 
      } 
     } 
    } 

---

संपादित

---

मैं भाग गया कुछ अन्य डेटा संरचना पर एक ही निदान (कुछ मेरे द्वारा बनाई *, .नेट फ्रेमवर्क ** से कुछ) और यहां दिलचस्प परिणाम

*AATree     00:00:00.0309294 
*AVLTree    00:00:00.0129743 
**SortedDictionary  00:00:00.0313571 
*RBTree     00:00:09.2414156 
**SortedSet    00:00:00.0241973 

RBTree ऊपर के रूप में ही है (बाहर छीन लिया सॉर्टेडसेट क्लास से)। मैंने 400000 मूल्यों के साथ भी कोशिश की, लेकिन आरबीटीरी को ले रहा है, मुझे वास्तव में पता नहीं क्यों।

Answer 1

आपके पास Node<T> कक्षा में एक बग है। जब आप कन्स्ट्रक्टर को कॉल करते हैं जो केवल एक मान तर्क लेता है तो आपको IsRed से true पर सेट करना चाहिए।

मुझे लगता है कि निश्चित Node<T> वर्ग कुछ इस तरह दिखना चाहिए:

public sealed class Node<T> 
{ 
    public T Item { get; private set; } 
    public bool IsRed { get; set; } 
    public Node<T> Left { get; set; } 
    public Node<T> Right { get; set; } 

    public Node(T value) 
    { 
     Item = value; 
     IsRed = true; 
    } 

    public Node(T value, bool isRed) 
    { 
     Item = value; 
     IsRed = isRed; 
    } 
} 

एक अन्य विकल्प - मेरी प्राथमिकता - कि निर्माता को पूरी तरह छोड़ होगा और हमेशा IsRed की आवश्यकता स्पष्ट रूप से सेट किया जा करने के लिए जब आप का दृष्टांत एक नया नोड:

public sealed class Node<T> 
{ 
    public T Item { get; private set; } 
    public bool IsRed { get; set; } 
    public Node<T> Left { get; set; } 
    public Node<T> Right { get; set; } 

    public Node(T value, bool isRed) 
    { 
     Item = value; 
     IsRed = isRed; 
    } 
} 

और फिर इस लाइन को अपने Add विधि में बदलें ...

Node<T> current = new Node<T>(item); 

... इस के साथ ...

Node<T> current = new Node<T>(item, true); 

Answer 2

यदि अंतर इतना बड़ा नहीं था तो मैं सुझाव दूंगा कि कारण यह है कि .NET असेंबली एनजीएन-एड हैं और इसलिए वे पहले ही देशी कोड में अनुवाद कर चुके हैं। आपकी कक्षा के मामले में आईएल कोड को मूल कोड में संकलित करने का समय आपके परीक्षण के समय में बढ़ाया जाता है। लूप पुनरावृत्तियों की संख्या में वृद्धि कैसे समय को प्रभावित करती है?

Answer 3

सॉर्टेडसेट में TargetedPatchingOptOut विशेषता शामिल है, क्या आपके कॉपी किए गए संस्करण में वह शामिल है?

[TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")] 
public bool Add(T item) 
{ 
    return this.AddIfNotPresent(item); 
} 

Answer 4

1. परीक्षण का क्रम उलटने और माप दोहराएँ।
2. अपने डेटा को यादृच्छिक बनाएं। सॉर्ट किए गए सेट अजीब तरीके से व्यवहार करते हैं जब आप पूर्व-क्रमबद्ध डेटा डालते हैं।