अपरिवर्तनीय (डबल) लिंक्डलिस्ट का कुशल कार्यान्वयन

Question

इस प्रश्न को पढ़ने के बाद Immutable or not immutable? और अपरिवर्तनीयता पर मेरे पिछले प्रश्नों के उत्तर पढ़ने के बाद, मैं अभी भी सरल लिंक्डलिस्ट के कुशल कार्यान्वयन के बारे में थोड़ा परेशान हूं जो अपरिवर्तनीय है। सरणी के संदर्भ में आसान लगता है - सरणी की प्रतिलिपि बनाएँ और उस प्रतिलिपि के आधार पर नई संरचना वापस करें।

माना जाता है हम नोड में सामान्य वर्ग का है:

class Node{ 
    private Object value; 
    private Node next; 
} 

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

मैं Immutable or not immutable? में उत्तर के बारे में भी उत्सुक हूं जो कि बाइनरी पेड़ की मदद से लॉग (एन) समय और स्थान की ओर अग्रसर सीरैन अनुकूलन का उल्लेख करते हैं। इसके अलावा, मैंने कहीं पढ़ा है कि सामने एक हाथी जोड़ना 0 (1) भी है। यह मुझे बहुत पहेली देता है, जैसे कि हम संदर्भों की प्रति प्रदान नहीं करते हैं, फिर वास्तविकता में हम दो अलग-अलग स्रोतों में एक ही डेटा संरचनाओं को संशोधित कर रहे हैं, जो अपरिवर्तनीयता को तोड़ते हैं ...

क्या आपके कोई भी उत्तर कोई काम करेगा दोगुनी से जुड़ी सूचियों पर? मैं किसी भी अन्य प्रश्न/समाधान के लिए किसी भी उत्तर/पॉइंटर्स की प्रतीक्षा करता हूं। आपकी सहायता के लिये पहले से ही धन्यवाद।

Answer 1

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

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

क्या हम तत्व को सम्मिलित करते समय सूची में सभी संदर्भों की प्रतिलिपि बनाते हैं?

आप कर सकते थे। आप यहां जो भेद प्राप्त कर रहे हैं वह अपरिवर्तनीय और लगातार के बीच का अंतर है। एक अपरिवर्तनीय डेटा संरचना को बदला नहीं जा सकता है। लगातार डेटा संरचना इस तथ्य का लाभ उठाती है कि एक डेटा संरचना अपने हिस्सों का पुन: उपयोग करने के लिए अपरिवर्तनीय है।

एक लगातार अपरिवर्तनीय लिंक्ड सूची विशेष रूप से आसान है:

abstract class ImmutableList 
{ 
    public static readonly ImmutableList Empty = new EmptyList(); 
    private ImmutableList() {} 
    public abstract int Head { get; } 
    public abstract ImmutableList Tail { get; } 
    public abstract bool IsEmpty { get; } 
    public abstract ImmutableList Add(int head); 
    private sealed class EmptyList : ImmutableList 
    { 
     public override int Head { get { throw new Exception(); } } 
     public override ImmutableList Tail { get { throw new Exception(); } } 
     public override bool IsEmpty { get { return true; } } 
     public override ImmutableList Add(int head) 
     { 
      return new List(head, this); 
     } 
    } 

    private sealed class List : ImmutableList 
    { 
     private readonly int head; 
     private readonly ImmutableList tail; 
     public override int Head { get { return head; } } 
     public override ImmutableList Tail { get { return tail; } } 
     public override bool IsEmpty { get { return false; } } 
     public override ImmutableList Add(int head) 
     { 
      return new List(head, this); 
     } 
    } 
} 
... 
ImmutableList list1 = ImmutableList.Empty; 
ImmutableList list2 = list1.Add(100); 
ImmutableList list3 = list2.Add(400); 

और वहाँ तुम जाओ। बेशक आप IEnumerable<int> विधियों जैसे बेहतर अपवाद हैंडलिंग और अधिक विधियों को जोड़ना चाहते हैं। लेकिन एक निरंतर अपरिवर्तनीय सूची है। हर बार जब आप एक नई सूची बनाते हैं, तो आप मौजूदा अपरिवर्तनीय सूची की सामग्री का पुनः उपयोग करते हैं; list3 list2 की सामग्री का दोबारा उपयोग करता है, जो सुरक्षित रूप से कर सकता है क्योंकि list2 कभी नहीं बदलेगा।

क्या आपके कोई भी उत्तर दोगुनी-लिंक्ड सूचियों पर भी काम करेगा?

आप निश्चित रूप से एक दोगुनी-लिंक्ड सूची बना सकते हैं जो हर समय संपूर्ण डेटा संरचना की पूरी प्रतिलिपि करता है, लेकिन यह गूंगा होगा; आप बस एक सरणी का उपयोग कर सकते हैं और पूरे सरणी की प्रतिलिपि बना सकते हैं।

बनाना दोगुनी-लिंक्ड सूची काफी कठिन है लेकिन इसे करने के तरीके हैं। मैं क्या करूँगा दूसरी दिशा से समस्या का सामना करना है। कहने के बजाय "क्या मैं लगातार दोगुनी जुड़ी सूची बना सकता हूं?" खुद से पूछें "एक दोगुनी-लिंक्ड सूची के गुण क्या हैं जो मुझे आकर्षक लगते हैं?" उन गुणों को सूचीबद्ध करें और फिर देखें कि क्या आप लगातार डेटा संरचना के साथ आ सकते हैं जिसमें वे गुण हैं।

उदाहरण के लिए, यदि आपको पसंद की जाने वाली संपत्ति यह है कि यदि दोगुनी-लिंक्ड सूचियों को सस्ता रूप से किसी भी अंत से बढ़ाया जा सकता है, तो दो सूचियों में आधा रूप से टूटा हुआ हो सकता है, और दो सूचियों को सस्ती रूप से एक साथ जोड़ा जा सकता है, फिर आप जो लगातार संरचना चाहते हैं वह है एक अपरिवर्तनीय catenable डेक, एक दोगुनी लिंक वाली सूची नहीं। मैं एक अपरिवर्तनीय गैर catenable Deque का एक उदाहरण यहां दे:

http://blogs.msdn.com/b/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx

यह विस्तार एक catenable Deque एक व्यायाम के रूप में छोड़ दिया जाता है कि; पेपर जो मैं उंगली के पेड़ से लिंक करता हूं वह पढ़ने के लिए एक अच्छा है।

अद्यतन:

ऊपर के अनुसार हम सम्मिलन बिंदु से ऊपर उपसर्ग कॉपी करना होगा। अपरिवर्तनीयता के तर्क से, यदि उपसर्ग से कुछ भी हटाते हैं, तो हमें एक नई सूची के साथ-साथ प्रत्यय में भी मिलता है ... फिर केवल उपसर्ग को कॉपी करने के लिए क्यों, और प्रत्यय नहीं है?

अच्छी तरह से एक उदाहरण पर विचार करें। क्या होगा अगर हमारे पास सूची (10, 20, 30, 40) है, और हम स्थिति 2 पर 25 डालना चाहते हैं? तो हम चाहते हैं (10, 20, 25, 30, 40)।

हम किन हिस्सों का पुन: उपयोग कर सकते हैं? हमारे पास पूंछ हैं (20, 30, 40), (30, 40) और (40)। स्पष्ट रूप से हम फिर से उपयोग कर सकते हैं (30, 40)।

आरेख तैयार करने से मदद मिल सकती है। हम:

10 ----> 20 ----> 30 -----> 40 -----> Empty 

और हम चाहते हैं

10 ----> 20 ----> 25 -----> 30 -----> 40 -----> Empty 

तो चलो

| 10 ----> 20 --------------> 30 -----> 40 -----> Empty 
|      /
| 10 ----> 20 ----> 25 -/ 

हम फिर से उपयोग (30, 40) कर सकते हैं क्योंकि वह हिस्सा दोनों सूचियों को आम में है बनाते हैं।

अद्यतन:

यह रूप में अच्छी तरह यादृच्छिक प्रविष्टि और हटाने के लिए कोड प्रदान करना संभव होगा?

ImmutableList InsertAt(int value, int position) 
{ 
    if (position < 0) 
     throw new Exception(); 
    else if (position == 0) 
     return this.Add(value); 
    else 
     return tail.InsertAt(value, position - 1).Add(head); 
} 

आप देख क्यों यह काम करता है कार्य करें:

यहाँ एक पुनरावर्ती समाधान है?

अब एक अभ्यास के रूप में, एक रिकर्सिव DeleteAt लिखें।

अब, एक अभ्यास के रूप में, गैर-रिकर्सिव InsertAt और DeleteAt लिखें। याद रखें, आपके पास अपने निपटान पर एक अपरिवर्तनीय लिंक सूची है, इसलिए आप अपने पुनरावर्तक समाधान में से एक का उपयोग कर सकते हैं!

Answer 2

क्या हम तत्व को सम्मिलित करते समय सूची में सभी संदर्भों की प्रतिलिपि बनाते हैं?

आपको सम्मिलन बिंदु तक, सूची के उपसर्ग को दोबारा प्रतिलिपि बनाना चाहिए।

इसका मतलब है कि एक अपरिवर्तनीय लिंक्ड सूची में सम्मिलन ओ (एन) है। (सरणी में एक तत्व डालने (ओवरराइटिंग नहीं) के रूप में है)।

इस कारण से सम्मिलन आमतौर पर (संलग्न और समावेशन के साथ) पर फेंक दिया जाता है।

अपरिवर्तनीय लिंक्ड सूचियों पर सामान्य ऑपरेशन "विपक्ष" है, यानी शुरुआत में एक तत्व जोड़ना, जो ओ (1) है।

आप स्पष्ट रूप से जटिलता को देख सकते हैं उदा। एक हास्केल कार्यान्वयन। एक पुनरावर्ती प्रकार के रूप में परिभाषित एक लिंक्ड सूची को देखते हुए:

data List a = Empty | Node a (List a) 

हम सीधे रूप में "विपक्ष" (मोर्चे पर एक तत्व डालने) को परिभाषित कर सकते हैं:

cons a xs = Node a xs 

जाहिर

एक हे (1) आपरेशन । सम्मिलन बिंदु को ढूंढकर - प्रविष्टि को रिकर्सिव रूप से परिभाषित किया जाना चाहिए। सूची को उपसर्ग (प्रतिलिपि) में तोड़ना, और नए नोड के साथ साझा करना और (अपरिवर्तनीय) पूंछ का संदर्भ देना।

महत्वपूर्ण बात यह जुड़ा हुआ सूचियों के बारे में याद करने के लिए है:

• रैखिक पहुँच

अपरिवर्तनीय सूचियों के लिए इसका मतलब है:

• एक सूची
• साझा करने के उपसर्ग को कॉपी पुंछ।

यदि आप अक्सर नए तत्व डालने वाले होते हैं, तो एक पेड़ जैसे लॉग-आधारित संरचना को प्राथमिकता दी जाती है।

Answer 3

"उत्परिवर्तन" का अनुकरण करने का एक तरीका है: अपरिवर्तनीय मानचित्रों का उपयोग करना।

स्ट्रिंग्स के किसी लिंक किए गए सूची के लिए (में स्काला शैली स्यूडोकोड):

case class ListItem(s:String, id:UUID, nextID: UUID)

तो ListItems मानचित्र में संग्रहित किया जा सकता है, जहां कुंजी UUID है: type MyList = Map[UUID, ListItem]

अगर मैं चाहता हूँ val list : MyList में

def insertAfter(l:MyList, e:ListItem)={ 
    val beforeE=l.getElementBefore(e) 
    val afterE=l.getElementAfter(e) 
    val eToInsert=e.copy(nextID=afterE.nextID) 
    val beforeE_new=beforeE.copy(nextID=e.nextID) 
    val l_tmp=l.update(beforeE.id,beforeE_new) 
    return l_tmp.add(eToInsert) 
} 

कहाँ add, update, get निरंतर समय Map का उपयोग कर लेता है: http://docs.scala-lang.org/overviews/collections/performance-characteristics

डबल लिंक्ड सूची को लागू करने में इसी तरह चला जाता है।