अपरिवर्तनीय स्टैक का उपयोग

Question

मैंने post को आज Microsoft.Bcl.Immutable NuGet पैकेज के स्थिर संस्करण की रिलीज़ की घोषणा की है।

मुझे आश्चर्य है: एक अपरिवर्तनीय ढेर के लिए क्या उपयोग किया जाएगा? मुझे एक उदाहरण या परिदृश्य नहीं मिल रहा है जहां यह उपयोगी होगा। अपरिवर्तनीयता की मेरी समझ हो सकती है। यदि आप कुछ प्रकाश डाल सकते हैं कि यह चीज़ उपयोगी क्यों हो सकती है, अधिमानतः एक ठोस उदाहरण के साथ, यह अच्छा होगा।

Answer 1

संग्रह में से इस पुस्तकालय के पीछे विचार, संग्रह प्रदान करने के लिए है कि जब बदल ही संग्रह है, जहां संग्रह के सभी पुराने संस्करणों अभी भी मान्य हैं के नए संस्करणों का उत्पादन है।

यह संस्करण नियंत्रण प्रणाली कैसे काम करता है इस तरह है: आप कोड बदल सकते हैं, और स्रोत पेड़ के एक नए संस्करण का उत्पादन कर सर्वर में परिवर्तन कर सकते हैं। इस बीच आप अभी भी किसी भी पिछले संशोधन की जांच कर सकते हैं।

अपरिवर्तनीय संग्रह के लिए, आप संग्रह जो बदलेगा नहीं करने के लिए एक सूचक रख कर एक पुराने संस्करण (अनिवार्य रूप से एक अपरिवर्तनीय स्नैपशॉट) को acces रहते हैं।

आप तर्क दे सकते हैं कि यह परिदृश्य ढेर के लिए कम उपयोगी है क्योंकि आप शायद प्रत्येक आइटम को एक बार जोड़ने और पुनर्प्राप्त करने के लिए एक स्टैक का उपयोग करते हैं, और ऑर्डर को भी संरक्षित करते हैं। आमतौर पर एक स्टैक का उपयोग निष्पादन के एक थ्रेड पर चलने वाले कोड से बहुत अधिक बंधे होते हैं।

लेकिन अब जब मैं टाइप कर रहा हूं, तो मैं एक विशिष्ट उपयोग केस के बारे में सोच सकता हूं यदि आपके पास आलसी पार्सर है जिसे किसी स्टैक में कुछ राज्य ट्रैक करने की आवश्यकता है। इसके बाद आप उस स्थिति में अपरिवर्तनीय ढेर में एक सूचक को सहेज सकते हैं, जो शुरुआती पार्स के दौरान था, प्रतिलिपि के बिना, और जब आप स्थगित काम का विश्लेषण करते हैं तो इसे पुनर्प्राप्त कर सकते हैं।

Answer 2

एक परिदृश्य की कल्पना करें जिससे अनुरोध एक पाइपलाइन पर आ रहे हैं और एक ढेर में संग्रहीत हैं क्योंकि अंतिम अनुरोध को प्राथमिकता के रूप में माना जाना चाहिए। तब मेरे पास थ्रेडेड अनुरोध उपभोक्ताओं का एक सेट है, जिनमें से प्रत्येक एक विशिष्ट प्रकार के अनुरोध से संबंधित है। मुख्य मार्शलिंग कोड ढेर बनाता है, फिर जब सभी उपभोक्ता तैयार होते हैं, तो उपभोक्ताओं को उस ढेर से गुजरता है और एक नया ढेर शुरू होता है।

यदि ढेर म्यूटेबल थे, तो प्रत्येक उपभोक्ता समानांतर में चल रहा होगा और अन्य उपभोक्ताओं के कारण किसी भी चरण में बदल सकता है जो एक ही स्टैक साझा करेगा। लॉकिंग को स्टैक से पॉपिंग आइटम को नियंत्रित करने की आवश्यकता होगी ताकि यह सुनिश्चित किया जा सके कि वे सभी सिंक में रहे। यदि उपभोक्ता को एक कार्य पूरा करने में लंबा समय लगता है जो स्टैक लॉक है, तो बाकी सभी को पकड़ लिया जाता है।

एक अपरिवर्तनीय ढेर होने के कारण, प्रत्येक उपभोक्ता ऐसा करने के लिए स्वतंत्र होता है जो अन्य उपभोक्ताओं की देखभाल के बिना स्टैक करना चाहता है। किसी नए आइटम में स्टैक परिणामों से किसी आइटम को रोकना और तह मूल अपरिवर्तित है। इसलिए लॉकिंग की आवश्यकता नहीं है और प्रत्येक थ्रेड दूसरों के लिए देखभाल किए बिना चलाने के लिए स्वतंत्र है।

Answer 3

मुझे अपरिवर्तनीय संग्रह पसंद हैं लेकिन वे अक्सर किसी समस्या की आवश्यकता के समाधान की तरह महसूस करते हैं। how they are implemented के कारण वे unexpectedly slow हो सकते हैं: वे foreach लूप और इंडेक्सर्स को अधिक एल्गोरिदमिक जटिल बनाने की लागत पर कुशलता से स्मृति का उपयोग करने के लिए बहुत मेहनत करते हैं। कितनी मेमोरी है, उस लागत को औचित्य देना मुश्किल हो सकता है। अपरिवर्तनीय संग्रह (ImmutableArray<T> के अलावा) के सफल उपयोगों के बारे में वेब पर मिलने वाली जानकारी की कमी है। इसे सुधारने के प्रयास में, मैंने सोचा कि मैं इस मामले के बारे में इस 3+ वर्षीय प्रश्न का उत्तर जोड़ूंगा जहां मुझे ImmutableStack<T> वास्तव में उपयोगी होने के लिए मिला।

public class TreeNode 
{ 
    public TreeNode Parent { get; private set; } 
    public List<TreeNode> ChildNodes { get; set; } 

    public TreeNode(TreeNode parent) 
    { 
     Parent = parent; 
    } 
} 

मैं वर्गों है कि इस बुनियादी पैटर्न कई, कई बार पालन करें, और व्यवहार में, यह मुझे हमेशा के लिए काम किया है बना लिया है:

यह बहुत ही बुनियादी पेड़ की तरह संरचना पर विचार करें। हाल ही में, मैं इस तरह कुछ करने के लिए शुरू कर दिया है:

public class TreeNode 
{ 
    public ImmutableStack<TreeNode> NodeStack { get; private set; } 
    public ImmutableStack<TreeNode> ParentStack { get { return NodeStack.IsEmpty ? ImmutableStack<TreeNode>.Empty : NodeStack.Pop(); } } 
    public TreeNode Parent { get { return ParentStack.IsEmpty ? null : ParentStack.Peek(); } } 

    public ImmutableArray<TreeNode> ChildNodes { get; set; } 

    public TreeNode(TreeNode parent) 
    { 
     if (parent == null) 
      NodeStack = ImmutableStack<TreeNode>.Empty; 
     else 
      NodeStack = parent.NodeStack.Push(this); 
    } 
} 

कई कारणों से के लिए, मैं एक TreeNode की ImmutableStack<T> उदाहरणों है कि मैं केवल एक संदर्भ के बजाय जड़ को पार कर सकते हैं भंडारण पसंद करते हैं पर आए हैं Parent उदाहरण के लिए।

• ImmutableStack<T> का कार्यान्वयन मूल रूप से एक लिंक की गई सूची है। ImmutableStack<T> का प्रत्येक उदाहरण वास्तव में एक लिंक की गई सूची पर एक नोड है। यही कारण है कि ParentStack संपत्ति PopNodeStack है। ParentStackImmutableStack<T> के Parent.NodeStack के समान उदाहरण लौटाएगा।
• यदि आप ParentTreeNode का संदर्भ संग्रहीत करते हैं, तो सर्कुलर लूप बनाना आसान होगा जो रूट नोड को कभी समाप्त नहीं करने के लिए संचालन का कारण बनता है, और आपको या तो एक स्टैक ओवरफ़्लो या अनंत लूप मिल जाएगा। दूसरी ओर, ImmutableStack<T>, Pop -ing द्वारा चढ़ाया जा सकता है, यह गारंटी देता है कि यह समाप्त हो जाएगा।
  • तथ्य यह है कि आप एक संग्रह (ImmutableStack<T>) का उपयोग का मतलब है कि आप बस यकीन है कि parentTreeNode दो बार नहीं होती है जब TreeNode निर्माण बनाकर पहली जगह में हो रहा से परिपत्र छोरों रोका जा सकता है।

बस के साथ शुरू करने के लिए है कि। मुझे लगता है कि ImmutableStack<T> पेड़ के संचालन को सरल और सुरक्षित बनाता है। आप (सुरक्षित रूप से) LINQ का उपयोग कर सकते हैं। जानना चाहते हैं कि एक TreeNode दूसरे का वंशज है या नहीं? आप बस ParentStack.Any(node => node == otherNode)

अधिक आम तौर पर कर सकता है, ImmutableStack<T> वर्ग किसी भी मामले में जहां आप चाहते हैं एक Stack<T> कि आप गारंटी ले सकते हैं संशोधित होगा कभी नहीं किया है, या आप एक एक Stack<T> "स्नैपशॉट" प्राप्त करने के लिए एक आसान तरीका की जरूरत है, लेकिन के लिए है उस ढेर की प्रतियों का एक गुच्छा बनाने के लिए नहीं बनाना चाहते हैं। यदि आपके पास नेस्टेड चरणों की एक श्रृंखला है, तो आप प्रगति को ट्रैक करने के लिए ImmutableStack<T> का उपयोग कर सकते हैं, और इसलिए जब कोई चरण पूरा हो जाता है, तो यह कार्य को अपने मूल चरण में बंद कर सकता है। जब आप समानांतर में काम करने की कोशिश कर रहे हैं तो इसकी अपरिवर्तनीय प्रकृति विशेष रूप से सहायक होती है।