2011-01-11 34 views
5

उदाहरण के लिए: मैं सरणीयह निर्धारित करने के लिए कि एक सरणी किसी अन्य का हिस्सा है?

var src = new byte[] {1, 2, 3, 4, 5}; 
var tag = new byte[] {3, 4}; 

कौन टैग की सरणी के सूचकांक को खोजने के लिए तेजी से विधि पता है? के रूप में निम्नलिखित मैं कुछ की जरूरत है:

int FindIndexOfSeq(byte[] src, byte[] sequence); 

एक दृश्य src में एक से अधिक समय में हो सकता है।

समाधान: How to find index of sublist in list?

+1

संभव नकल http://stackoverflow.com/questions/3529727/how-to-find-index-of-sublist-in-list – nan

+2

यह कुशलता से हल करने के लिए एक आसान समस्या नहीं है। भद्दा, आसान-कार्यान्वित-खोज 'ओ (एनएम)' सबसे खराब मामला है। आप उस पर काफी सुधार कर सकते हैं (जैसे बॉयर-मूर), लेकिन यह आसान नहीं है। http://en.wikipedia.org/wiki/String_searching_algorithm#Single_pattern_algorithms – Ani

+0

केवल पहली घटना का सूचकांक? –

उत्तर

1
int FindIndexOfSeq<T>(byte[] src, byte[] tag) 
{ 
    Int32 tagCount = tag.Count();    

    // If `tag` is not empty and `src` contains `tag` 
    if (tagCount > 0 && src.Intersect(tag).Count() == tagCount) 
    { 
     // Find index of first element in `tag` 
     Int32 tagStartIndex = Array.IndexOf(src, tag.First()); 

     // Get the matching slice of `tag` from `src` 
     var newSrc = src.Skip(tagStartIndex).Take(tag.Count()).ToList(); 

     // Zip them together using their difference 
     var sum = Enumerable.Zip(tag, newSrc, (i1, i2) => Convert.ToInt32(i2 - i1)).Sum(); 

     // If total of their differences is zero, both sequences match 
     if (sum == 0) 
     { 
      // return starting index of `tag` in `src` 
      return tagStartIndex; 
     } 
    } 

    // return `Not Found` 
    return -1; 
} 
+0

क्या यह गलत नहीं होगा अगर src {1, 2, 3, 3, 4, 5} है और टैग {3, 4} है? –

2

यहाँ करने के लिए एक ही रास्ता है सूचकांक

for (int i = 0; i < (src.Length - tag.Length); i++) 
{ 
    if (tag.SequenceEqual(src.Skip(i).Take(tag.Length))) 
     Console.WriteLine("It's at position " + i); 
} 

दुर्भाग्य से यह बहुत धीमी है मिलता है।

तुम सिर्फ tag में आइटम के सभी src में पाया जा सकता है, तो (किसी भी क्रम में)

var src = new byte[] { 1, 2, 3, 4, 5 }; 
var tag = new byte[] { 4, 3 }; 

if (src.Intersect(tag).Count() == tag.Length) 
    Console.WriteLine("tag can be found in src!"); 
+0

नहीं, मुझे इंडेक्स को जानने की आवश्यकता है जहां अनुक्रम शुरू होता है। –

+0

पर्याप्त स्मार्ट। +1 – deadlock

+0

जोनास, आपके नमूने में आपके पास टैग की सरणी में बाइट्स का गलत क्रम है। –

2

सबसे अच्छा आप प्राप्त कर सकते हैं पता करने के लिए तो चाहते हैं हे (एम) है, लेकिन है कि मैं थोड़ा जटिल कार्यान्वयन। यदि आप ऐसे समाधान से संतुष्ट हैं जिसमें ओ (एम * एन) सबसे खराब मामला है तो आप नीचे दिए गए समाधान के साथ जा सकते हैं। यदि आपके अनुक्रमों का आदेश दिया गया है और tag सरणी में प्रारंभिक आइटम src में केवल एक बार मौजूद है तो इसके परिणामस्वरूप ओ (एम) भी होगा।

class Program 
{ 
    static void Main(string[] args) 
    { 
     var src = new byte[] { 1, 2, 3, 4, 5 }; 
     var tag = new byte[] { 3, 4 }; 
     var index = FindIndexOfSeq(src, tag); 
     Console.WriteLine(index); 
     Console.ReadLine(); 
    } 
    static int FindIndexOfSeq<T>(T[] src, T[] seq) 
    { 
     int index = -1; 
     for (int i = 0; i < src.Length - seq.Length + 1; i++) 
     { 
      bool foundSeq = true; 
      for (int j = 0; j < seq.Length; j++) 
      { 
       foundSeq = foundSeq && src[i + j].Equals(seq[j]); 
      } 
      if (foundSeq) 
      { 
       index = i; 
       break; 
      } 
     } 
     return index; 
    } 
} 

मैं अनुक्रम मान लिया है कि क्रम में होना है और मैं केवल इतना यकीन नहीं करता है, तो यह काम करता है :) फ़ायरफ़ॉक्स में यह तैयार की है,। इसके अलावा, मैंने इसे सामान्य बना दिया है, इसलिए यह किसी भी प्रकार के सरणी को बाइट नहीं करता है।

अद्यतन: अद्यतन कोड संकलित और काम ... या मेरा सरल परीक्षण काम किया।

+0

आप * ओ (एनएम) 'पर * सुधार कर सकते हैं, वास्तव में यह' ओ (एन) 'में करना संभव है। उदाहरण: बॉयर-मूर। http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm – Ani

+0

आप सही हैं ... मैंने उस भाग को अपडेट किया और एक सरल कार्यक्रम भी शामिल किया। इसके अलावा, आप ओ (एन) के साथ सही हैं, लेकिन यह एक बहुत अधिक जटिल एल्गोरिदम की तरह लगता है? क्या यह छोटे सेट पर तेज़ है? मुझे लगता है कि वहाँ एक छोटा सा व्यापार है। यदि उसका अनुक्रम उसके द्वारा प्रदान किए गए जैसा दिखता है जिसके परिणामस्वरूप ओ (एन + एम) होगा। –

+0

हां, मैं उन लोगों में से किसी एक को कार्यान्वित करने के लिए सहमत हूं जो संभवतः सबसे आम उपयोगों के लिए अधिक है। लेकिन मैं अभी भी छुटकारा पाउंगा "आप जो भी प्राप्त कर सकते हैं वह है ओ (एम * एन)"; यह थोड़ा भ्रामक है। – Ani

0

समाधान पाया: इसके लिए आपको बेहतर प्रदर्शन के लिए किसी भी KMP एल्गोरिथ्म का उपयोग कर सकते हैं।

How to find index of sublist in list?

+0

उस प्रश्न के पास एक स्वीकार्य उत्तर नहीं है। आप किसने पसंद किया? –

संबंधित मुद्दे

 संबंधित मुद्दे