मूल्य-बराबर और परिपत्र संदर्भ: अनंत रिकर्सन को कैसे हल करें?

Question

मेरे पास कुछ कक्षाएं हैं जिनमें कई फ़ील्ड हैं। मुझे मूल्य से उनकी तुलना करने की आवश्यकता है, यानी एक वर्ग के दो उदाहरण बराबर हैं यदि उनके फ़ील्ड में एक ही डेटा होता है। मैंने इसके लिए GetHashCode और Equals विधियों को ओवरराइड कर दिया है।

ऐसा हो सकता है कि इन वर्गों में परिपत्र संदर्भ शामिल हैं।

उदाहरण: हम संस्थानों (जैसे सरकारी, खेल क्लब, जो कुछ भी) मॉडल करना चाहते हैं। एक संस्थान का नाम है। एक Club एक संस्था है जिसका नाम और सदस्यों की एक सूची है। प्रत्येक सदस्य Person है जिसका नाम और पसंदीदा संस्थान है। यदि किसी निश्चित क्लब के सदस्य को यह क्लब अपने पसंदीदा संस्थान के रूप में है, तो हमारे पास एक परिपत्र संदर्भ है।

लेकिन परिपत्र संदर्भ, मूल्य समानता के संयोजन के साथ, अनंत रिकर्सन का कारण बनता है।

interface IInstitution { string Name { get; } } 

class Club : IInstitution 
{ 
    public string Name { get; set; } 
    public HashSet<Person> Members { get; set; } 

    public override int GetHashCode() { return Name.GetHashCode() + Members.Count; } 

    public override bool Equals(object obj) 
    { 
     Club other = obj as Club; 
     if (other == null) 
      return false; 

     return Name.Equals(other.Name) && Members.SetEquals(other.Members); 
    } 
} 

class Person 
{ 
    public string Name { get; set; } 
    public IInstitution FavouriteInstitution { get; set; } 

    public override int GetHashCode() { return Name.GetHashCode(); } 

    public override bool Equals(object obj) 
    { 
     Person other = obj as Person; 
     if (other == null) 
      return false; 

     return Name.Equals(other.Name) 
      && FavouriteInstitution.Equals(other.FavouriteInstitution); 
    } 
} 

class Program 
{ 
    public static void Main() 
    { 
     Club c1 = new Club { Name = "myClub", Members = new HashSet<Person>() }; 
     Person p1 = new Person { Name = "Johnny", FavouriteInstitution = c1 } 
     c1.Members.Add(p1); 

     Club c2 = new Club { Name = "myClub", Members = new HashSet<Person>() }; 
     Person p2 = new Person { Name = "Johnny", FavouriteInstitution = c2 } 
     c2.Members.Add(p2); 

     bool c1_and_c2_equal = c1.Equals(c2); // StackOverflowException! 
      // c1.Equals(c2) calls Members.SetEquals(other.Members) 
      // Members.SetEquals(other.Members) calls p1.Equals(p2) 
      // p1.Equals(p2) calls c1.Equals(c2) 
    } 
} 

c1_and_c2_equaltrue लौटना चाहिए, और वास्तव में हम (मनुष्य) देख सकते हैं कि वे मूल्य-बराबर सोच का एक छोटा सा के साथ कर रहे हैं, अनंत प्रत्यावर्तन में चलने के बिना: यहां एक कोड उदाहरण है। हालांकि, मैं वास्तव में यह नहीं कह सकता कि हम इसे कैसे समझते हैं। लेकिन चूंकि यह संभव है, मुझे उम्मीद है कि कोड में इस समस्या को हल करने का एक तरीका भी है!

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

ध्यान दें कि मुझे सामान्य रूप से परिपत्र संदर्भों को हल करने की आवश्यकता है, न केवल ऊपर से मामला। मैं c1 संदर्भ p1, और p1 संदर्भ c1 के बाद से इसे 2-सर्कल कहूंगा। अन्य एन-मंडल भी हो सकते हैं, उदा। अगर एक क्लब A में सदस्य M है जिसका पसंदीदा क्लब B है जिसमें सदस्य N है जिसका पसंदीदा क्लब A है। यह एक 4-सर्कल होगा। अन्य ऑब्जेक्ट मॉडल एन-सर्कल को विषम संख्याओं के साथ भी अनुमति दे सकते हैं n। मैं इन सभी समस्याओं को एक बार में हल करने का एक तरीका ढूंढ रहा हूं, क्योंकि मुझे पहले से पता नहीं चलेगा कि मूल्य एन क्या हो सकता है।

Answer 1

सामान्य स्थिति है कि मैं

में दिलचस्पी के लिए - जहाँ हम कक्षाओं C1, ... है, Cn जहां इन वर्गों के प्रत्येक मान के किसी भी संख्या हो सकती है (जैसे int, string ...) और साथ ही किसी भी अन्य वर्गों के लिए संदर्भ के किसी भी संख्या C1, ..., Cn (प्रत्येक प्रकार Ci एक क्षेत्र ICollection<Ci>) के लिए होने से जैसे -

सवाल "दो वस्तुओं A और B बराबर हैं? ", समानता है कि मैं यहाँ वर्णित के अर्थ में,

सवाल "दो परिमित, निर्देशन, जुड़ा हुआ है, रंग का रेखांकन G और H के लिए के बराबर हो रहा है, वहाँ G से समाकृतिकता मौजूद है H पर? "।

यहाँ तुल्यता है:

• ग्राफ कोने object रों (वर्ग उदाहरण)
• ग्राफ किनारों object रों
• रंग के लिए संदर्भ के अनुरूप के अनुरूप मूल्यों के समूह और प्रकार खुद से मेल खाती है (यानी दो अक्षरों के रंग समान हैं यदि उनके संबंधित object के समान प्रकार और समान मान हैं)

यह एक एनपी-कठिन सवाल है, इसलिए मुझे लगता है कि मैं इसे लागू करने के लिए अपनी योजना को त्यागने जा रहा हूं और इसके बजाय एक परिपत्र-संदर्भ-मुक्त दृष्टिकोण के साथ जाऊंगा।

Answer 2

एक आसान कामकाज (आरडीबीएमएस में प्रयुक्त) Person (किसी भी प्रकार) की पहचान करने के लिए एक अद्वितीय Id का उपयोग करना है। फिर आपको हर दूसरी संपत्ति की तुलना करने की आवश्यकता नहीं है और आप कभी भी इस तरह के क्यूरिक्यूलर संदर्भों में भाग नहीं लेते हैं।

Equals में अलग-अलग तुलना करने का एक और तरीका है, इसलिए केवल Equals के प्रकार के लिए गहरी जांच प्रदान करें और संदर्भित प्रकारों के लिए नहीं। आप एक कस्टम comparer इस्तेमाल कर सकते हैं:

public class PersonNameComparer : IEqualityComparer<Person> 
{ 
    public bool Equals(Person x, Person y) 
    { 
     if (x == null && y == null) return true; 
     if (x == null || y == null) return false; 
     if(object.ReferenceEquals(x, y)) return true; 
     return x.Name == y.Name; 
    } 

    public int GetHashCode(Person obj) 
    { 
     return obj?.Name?.GetHashCode() ?? int.MinValue; 
    } 
} 

अब आप Club की Equals कार्यान्वयन को बदल सकते हैं से बचने के लिए कि Members (व्यक्ति) प्रति गहरा जांच करते हैं कि संस्था शामिल है, लेकिन केवल अपने Name का उपयोग करेगा:

public override bool Equals(object obj) 
{ 
    if (Object.ReferenceEquals(this, obj)) 
     return true; 

    Club other = obj as Club; 
    if (other == null) 
     return false; 

    var personNameComparer = new PersonNameComparer(); 
    return Name.Equals(other.Name) 
     && Members.Count == other.Members.Count 
     && !Members.Except(other.Members, personNameComparer).Any(); 
} 

आप देखते हैं कि मैं SetEquals का उपयोग नहीं कर सकता क्योंकि मेरे कस्टम तुलनाकर्ता के लिए कोई अधिभार नहीं है।

Answer 3

ड्राइडवुड के सुझाव के बाद, मैंने Equals विधियों को बदल दिया ताकि मैं पहले से तुलना की गई वस्तुओं का ट्रैक रख सकूं।

public class ValuePairRefEqualityComparer<T> : IEqualityComparer<(T,T)> where T : class 
{ 
    public static ValuePairRefEqualityComparer<T> Instance 
     = new ValuePairRefEqualityComparer<T>(); 
    private ValuePairRefEqualityComparer() { } 

    public bool Equals((T,T) x, (T,T) y) 
    { 
     return ReferenceEquals(x.Item1, y.Item1) 
      && ReferenceEquals(x.Item2, y.Item2); 
    } 

    public int GetHashCode((T,T) obj) 
    { 
     return RuntimeHelpers.GetHashCode(obj.Item1) 
      + 2 * RuntimeHelpers.GetHashCode(obj.Item2); 
    } 
} 

और यहाँ Club के संशोधित Equals विधि है::

static HashSet<(Club,Club)> checkedPairs 
    = new HashSet<(Club,Club)>(ValuePairRefEqualityComparer<Club>.Instance); 

public override bool Equals(object obj) 
{ 
    Club other = obj as Club; 
    if (other == null) 
     return false; 

    if (!Name.Equals(other.Name)) 
     return; 

    if (checkedPairs.Contains((this,other)) || checkedPairs.Contains((other,this))) 
     return true; 

    checkedPairs.Add((this,other)); 

    bool membersEqual = Members.SetEquals(other.Members); 
    checkedPairs.Clear(); 
    return membersEqual; 
} 

Person के लिए संस्करण अनुरूप है

पहले हम एक समानता comparer कि इसी जोड़े के तत्वों के लिए संदर्भ समानता की जाँच करता है की जरूरत है । ध्यान दें कि मैं checkedPairs को (this,other) जोड़ सकते हैं और जाँच लें कि या तो (this,other) या (other,this) क्योंकि यह हो सकता है कि c1.Equals(c2) की पहली कॉल के बाद, हम c2.Equals(c1) बजाय c1.Equals(c2) के एक कॉल के साथ समाप्त होता है। मुझे यकीन नहीं है कि यह वास्तव में होता है, लेकिन चूंकि मैं SetEquals के कार्यान्वयन को नहीं देख पा रहा हूं, मुझे विश्वास है कि यह एक संभावना है।

चूंकि मैं पहले से चेक किए गए जोड़े के लिए स्थिर क्षेत्र का उपयोग करने से खुश नहीं हूं (यह प्रोग्राम काम करने वाला नहीं होगा!), मैंने एक और प्रश्न पूछा: make a variable last for a call stack।