एक टुपल मिलान एल्गोरिदम

Question

की तलाश में मुझे सी में एक मेमोरी टुपल-ऑफ-स्ट्रिंग मिलान सुविधा को कार्यान्वित करने की आवश्यकता है। विभिन्न कार्यों से जुड़े टुपल्स की बड़ी सूची और सूची के विरुद्ध मिलान की जाने वाली घटनाओं की एक बड़ी मात्रा होगी ।

tuples की सूची:

("one", "four") 
("one") 
("three") 
("four", "five") 
("six")  

घटना ("एक", "दो", "तीन", "चार") सूची आइटम से मेल खाना चाहिए ("एक", "चार") और ("एक ") और (" तीन ") नहीं (" चार "," पांच ") और नहीं (" छः ")

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

क्या ऐसा करने का कोई सही या क्लासिक तरीका है?

Answer 1

यदि आपके पास केवल कुछ छोटे टुपल मान हैं तो इसे कुछ प्रकार के हैशिंग फ़ंक्शन लिखने का अर्थ होगा जो उन्हें त्वरित खोज के लिए पूर्णांक अनुक्रमणिका में बदल सकता है।

अगर वहाँ < 32 मूल्यों आप bitmasks साथ कुछ कर सकते हैं:

unsigned int hash(char *value){...} 

typedef struct _tuple { 
    unsigned int bitvalues; 
    void * data 
} tuple; 

tuple a,b,c,d; 
a.bitvalues = hash("one"); 
a.bitvalues |= hash("four"); 
//a.data = something; 

unsigned int event = 0; 
//foreach value in event; 
event |= hash(string_val); 

// foreach tuple 
if(x->bitvalues & test == test) 
{ 
    //matches 
} 

अगर वहाँ एक बिटमास्क समाधान आप लिंक सूचियों की एक सरणी हो सकता करने के लिए बहुत अधिक मान रहे हैं। घटना में प्रत्येक आइटम के माध्यम से जाओ। आइटम key_one मेल खाता है, कि पहली कुंजी के साथ tuples के माध्यम से चलना और दूसरी चाबी के लिए घटना की जाँच करें:

typedef struct _tuple { 
    unsigned int key_one; 
    unsigned int key_two; 
    _tuple *next; 
    void * data; 
} tuple; 

tuple a,b,c,d; 
a.key_one = hash("one"); 
a.key_two = hash("four"); 

tuple * list = malloc(/*big enough for all hash indexes*/ 
memset(/*clear list*/); 

//foreach touple item 
if(list[item->key_one]) 
    put item on the end of the list; 
else 
    list[item->key_one] = item; 


//foreach event 
    //foreach key 
     if(item_ptr = list[key]) 
     while(item_ptr.next) 
      if(!item_ptr.key_two || /*item has key_two*/) 
       //match 
      item_ptr = item_ptr.next; 

इस कोड को कोई रास्ता नहीं परीक्षण किया है और शायद कई छोटे त्रुटियाँ हैं, लेकिन आप विचार प्राप्त करना चाहिए। (एक त्रुटि है कि ठीक किया गया था टपल मैच के लिए परीक्षण हालत था)

---

घटना प्रसंस्करण गति अत्यंत महत्व यह मतलब होगा आपका निर्मित tuples के सभी के माध्यम से पुनरावृति करने की है, तो घटनाओं की संख्या की गिनती और के माध्यम से जाना संभावित रूप से प्रत्येक टुपल की कुंजी एक/कुंजी दो को फिर से ऑर्डर करना ताकि सबसे अनोखा मान पहले सूचीबद्ध हो।

Answer 2

मैं यह करने के लिए किसी भी शास्त्रीय या सही तरीके से पता नहीं है, इसलिए यहाँ मैं क्या कर सकता है: पी

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

उदाहरण के लिए, आप बी का पहला मान लेते हैं, और जब तक आप ए में डुप्लिकेट नहीं पाते हैं तब तक ए चलते हैं। फिर आप बी का दूसरा मान लेते हैं, और जहां से आपने पहले छोड़ा था वहां से चलना शुरू करें। यदि आप मैच के बिना ए के अंत तक पहुंच जाते हैं, तो ए बी का सुपरसेट नहीं है, और आप झूठी वापसी करते हैं।

यदि इन tuples क्रमबद्ध रह सकते हैं, तो सॉर्टिंग लागत केवल एक बार किया जाता है।

Answer 3

यदि आपके पास संभावित तारों की एक छोटी संख्या है, तो आप प्रत्येक को एक इंडेक्स असाइन कर सकते हैं और बिटमैप्स का उपयोग कर सकते हैं। इस तरह एक साधारण bitwise और आपको बताएगा कि ओवरलैप है या नहीं।

यदि यह व्यावहारिक नहीं है, तो आपके उलटा इंडेक्स सेटअप शायद गति के लिए मिलान करना कठिन होगा, खासकर यदि आपको केवल इसे एक बार बनाना है।(क्या टुपल्स की सूची रनटाइम पर बदलती है?)

Answer 4

public static void Main() 
    { 
     List<List<string>> tuples = new List<List<string>>(); 

     string [] tuple = {"one", "four"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string [] {"one"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string [] {"three"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string[]{"four", "five"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string[]{"six"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string[] {"one", "two", "three", "four"}; 

     List<string> checkTuple = new List<string>(tuple); 

     List<List<string>> result = new List<List<string>>(); 

     foreach (List<string> ls in tuples) 
     { 
      bool ok = true; 
      foreach(string s in ls) 
       if(!checkTuple.Contains(s)) 
       { 
        ok = false; 
        break; 
       } 
      if (ok) 
       result.Add(ls); 
     } 
    } 

Answer 5

एक संभावित समाधान प्रत्येक शब्द को एक अद्वितीय प्राइम नंबर असाइन करना होगा।

फिर यदि आप प्रत्येक टुपल में शब्दों को एक साथ गुणा करते हैं, तो आपके पास एक संख्या है जो सूची में शब्दों का प्रतिनिधित्व करती है।

एक सूची को दूसरे द्वारा विभाजित करें, और यदि आप एक पूर्णांक शेष प्राप्त करते हैं, तो एक सूची दूसरे में निहित है।