एक गतिशील रेंज पर स्थानीय मैक्सिमा ढूंढना

Question

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

public List<double> FindPeaks(List<double> values, double rangeOfPeaks) 

जहां अगर 'rangeOfPeaks' 5 था, 'वर्तमान' मूल्य यह के प्रत्येक पक्ष पर 2 मूल्यों की तुलना में किया जाएगा निर्धारित करने के लिए अगर यह एक था चोटी या नहीं। यदि 'rangeOfPeaks' 11 वर्ष का था, तो वर्तमान मान की तुलना प्रत्येक पक्ष पर 5 मानों से की जाएगी। मुझे लगता है कि यह एक सुंदर मूल एल्गोरिदम था, हालांकि, मैं इस तरह की चोटी का पता लगाने के लिए किसी भी अच्छे तरीके खोजने में असफल रहा हूं। क्या किसी ने कभी यह पहले किया है? किसी भी मदद के लिए आभारी होंगे। अग्रिम में धन्यवाद!

Answer 1

शायद और अधिक कुशल तरीके हैं लेकिन LINQ इस बिल्कुल स्पष्ट

static IList<double> FindPeaks(IList<double> values, int rangeOfPeaks) 
    { 
     List<double> peaks = new List<double>(); 

     int checksOnEachSide = rangeOfPeaks/2; 
     for (int i = 0; i < values.Count; i++) 
     { 
      double current = values[i]; 
      IEnumerable<double> range = values; 
      if(i > checksOnEachSide) 
       range = range.Skip(i - checksOnEachSide); 
      range = range.Take(rangeOfPeaks); 
      if (current == range.Max()) 
       peaks.Add(current); 
     } 
     return peaks; 
    } 

Answer 2

इस समारोह हे (एन) है बनाता है। यह परिणाम देता है क्योंकि यह जाता है इसलिए इसमें बहुत कम स्मृति ओवरहेड भी होगा।

public static IEnumerable<double> FindPeaks(IEnumerable<double> values, int rangeOfPeaks) 
    { 
     double peak = 0; 
     int decay = 0; 

     foreach (var value in values) 
     { 
      if (value > peak || decay > rangeOfPeaks/2) 
      { 
       peak = value; 
       decay = 0; 
      } 
      else 
      { 
       decay++; 
      } 

      if (decay == rangeOfPeaks/2) 
       yield return peak; 
     } 
    } 

Answer 3

मैं लेवी की पोस्ट में कुछ परिवर्तन ...

1) लेवी के कोड एक अपवाद फेंक दिया जब निर्दिष्ट मानों IList एक लगभग सीधी रेखा था सुझाव देते हैं।

2) मुझे लगता है कि सरणी में चोटियों की अनुक्रमणिका वांछित परिणाम है। उदाहरण के लिए विचार करें कि क्या होगा यदि हमारे समान युगल के साथ दो चोटियां हों? ऑप्स। निर्दिष्ट IList में चोटियों की वापसी सूचकांक में बदल गया।

public static IList<int> FindPeaks(IList<double> values, int rangeOfPeaks) 
    { 
     List<int> peaks = new List<int>(); 
     double current; 
     IEnumerable<double> range; 

     int checksOnEachSide = rangeOfPeaks/2; 
     for (int i = 0; i < values.Count; i++) 
     { 
      current = values[i]; 
      range = values; 

      if (i > checksOnEachSide) 
      { 
       range = range.Skip(i - checksOnEachSide); 
      } 

      range = range.Take(rangeOfPeaks); 
      if ((range.Count() > 0) && (current == range.Max())) 
      { 
       peaks.Add(i); 
      } 
     } 

     return peaks; 
    } 

Answer 4

पुराना प्रश्न है कि पहले से ही एक स्वीकार्य उत्तर है, लेकिन मैं ओ (एन^2) से कुछ बेहतर चाहता था। यह फ़ंक्शन ओ (एन * एम) है जहां मीटर विंडो का आकार है, और वास्तव में भी काम करने का लाभ है। विधि स्थानीय अधिकतमता और उनके संबंधित मूल्य के सूचकांक के tuples देता है।

Enumerable.Repeat() पर कॉल सुनिश्चित करें कि सेट की शुरुआत और अंत में अधिकतमता भी मिलती है।

after कतार के साथ तुलना >= का उपयोग करती है ताकि स्थानीय अधिकतम मूल्यों के पठार की शुरुआत में पाए जाएंगे। एक साइड इफेक्ट यह है कि सेट 0 के मान बराबर हैं, यदि सेट में सभी मान बराबर हैं, जो वांछित हो सकते हैं या नहीं भी हो सकते हैं।

public static IEnumerable<Tuple<int, double>> LocalMaxima(IEnumerable<double> source, int windowSize) 
{ 
    // Round up to nearest odd value 
    windowSize = windowSize - windowSize % 2 + 1; 
    int halfWindow = windowSize/2; 

    int index = 0; 
    var before = new Queue<double>(Enumerable.Repeat(double.NegativeInfinity, halfWindow)); 
    var after = new Queue<double>(source.Take(halfWindow + 1)); 

    foreach(double d in source.Skip(halfWindow + 1).Concat(Enumerable.Repeat(double.NegativeInfinity, halfWindow + 1))) 
    { 
     double curVal = after.Dequeue(); 
     if(before.All(x => curVal > x) && after.All(x => curVal >= x)) 
     { 
      yield return Tuple.Create(index, curVal); 
     } 

     before.Dequeue(); 
     before.Enqueue(curVal); 
     after.Enqueue(d); 
     index++; 
    } 
} 

Answer 5

आरएक्स टीम से Interactive Extensions package उपयोग करके, आप काफी बड़े करीने से इस समस्या का समाधान कर सकते हैं। विभिन्न बफरिंग/विंडोिंग परिदृश्यों के साथ पैकेज में बहुत सारे फ़ंक्शन हैं।

IEnumerable<double> FindPeaks(IEnumerable<double> numbers, int windowSize) 
{ 
    // Pad numbers to the left of <numbers> so that the first window of <windowSize> is centred on the first item in <numbers> 
    // Eg if numbers = { 1, 2, 3, 4 }, windowSize = 3, the first window should be { MinValue, 1, 2 }, not { 1, 2, 3 } 
    var paddedNumbers = Enumerable.Repeat(double.MinValue, windowSize/2) 
            .Concat(numbers); 

    // Take buffers of size <windowSize>, stepping forward by one element each time 
    var peaks = paddedNumbers.Buffer(windowSize, 1) 
          .Select(range => range.Max()) 
          .DistinctUntilChanged(); 

    return peaks; 
}