मैं एक कस्टम गणक के साथ अनंत रिकर्सन से कैसे बचूं?

Question

मैंने संग्रह में लगातार मूल्यों की संख्या को खोजने के लिए एक विस्तार विधि बनाई है। चूंकि यह सामान्य है, इसलिए मैं कॉलर को "incrementor" को परिभाषित करने की अनुमति देता हूं जो एक Func <> है जो "अगले" मान के अस्तित्व की जांच के लिए मान को बढ़ाने के लिए माना जाता है।

हालांकि, फोन करने वाले एक अनुचित incrementor गुजरता है अगर (अर्थात एक्स => x), यह एक अनंत पुनरावर्ती पाश का कारण होगा। इसे रोकने के लिए एक साफ तरीके से कोई सुझाव?

public static int CountConsecutive<T>(this IEnumerable<T> values, T startValue, Func<T, T> incrementor) 
{ 
    if (values == null) 
    { 
     throw new ArgumentNullException("values"); 
    } 
    if (incrementor == null) 
    { 
     throw new ArgumentNullException("incrementor"); 
    } 
    var nextValue = incrementor(startValue); 
    return values.Contains(nextValue) 
     ? values.CountConsecutive(nextValue, incrementor) + 1 
     : 1; 
} 

Answer 1

शुद्धतम अर्थ में, यह Halting Problem पर एक प्रयास है और अनिर्णनीय है। सबसे सरल मामलों के लिए, आपको अपनी विधि को कॉल करने वाले लोगों पर भरोसा करना होगा।

की तरह दूसरों से पता चला है, तो आप को दिखाने के लिए है कि अगले मान भिन्न है समानता का एक सरल जांच कर सकते हैं। प्रत्येक विज़िट किए गए T को संग्रहीत करना काम करेगा, लेकिन आपको स्मृति अंततः मेमोरी के बारे में चिंता करनी होगी।

एक के रूप में अलग रूप में, यहाँ एक आसानी से लागू किया StackOverflowException है तो आप किसी भी डेटा सेट कि लगातार मूल्यों पर बहुत कुछ करना होगा से सावधान रहना होगा।

var x = Enumerable.Range(1, 100000).CountConsecutive(1, x => x+1); 

Answer 2

आप startValue को nextValue तुलना कर सकते हैं (आप IComparable लागू करने के लिए टी की आवश्यकता होगी)।

यह इस बग का समाधान होगा, यह एक बुरा incrementor बग कि एक पाश रिटर्न का समाधान नहीं होगा - A1, A2, A3, ..., एक, A1। मुझे नहीं लगता कि आप को संभालने के लिए इस मामले चाहते हैं, हालांकि

Answer 3

सबसे सामान्य स्थिति से निपटने के लिए, आप यह कर सकते हैं:

var nextValue = incrementor(startValue); 
if (nextValue.Equals(startValue)) { 
    throw new ArgumentException("incrementor"); 
} 

सामान्य मामले के लिए, इस कार्य करें:

public static int CountConsecutive<T>(this IEnumerable<T> values, T startValue, Func<T, T> incrementor) { 
    if (values == null) { 
     throw new ArgumentNullException("values"); 
    } 
    if (incrementor == null) { 
     throw new ArgumentNullException("incrementor"); 
    } 
    ISet<T> seen = new HashSet<T>(); 
    return CountConsecutive(values, startValue, incrementor, seen); 
} 

private static int CountConsecutive<T>(IEnumerable<T> values, T startValue, Func<T, T> incrementor, ISet<T> seen) { 
    if (!seen.Add(startValue)) { 
     throw new ArgumentException("incrementor"); 
    } 
    var nextValue = incrementor(startValue); 
    return values.Contains(nextValue) 
     ? values.CountConsecutive(nextValue, incrementor) + 1 
     : 1; 
}