पूर्णांक सेट के सेट के लिए एक सरल सी लाइब्रेरी क्या है?

Question

मुझे एक सी प्रोग्राम को संशोधित करना होगा और मुझे बिना हस्ताक्षरित पूर्णांक सेट का एक सेट शामिल करना होगा। यही है, मेरे पास पूर्णांक के लाखों सेट हैं (इनमें से प्रत्येक पूर्णांक सेट में 3 से 100 पूर्णांक होते हैं), और मुझे इन्हें कुछ संरचना में स्टोर करने की आवश्यकता है, इसे निर्देशिका को कॉल करने दें, जो कि लॉगरिदमिक समय में मुझे बता सकता है कि दिया गया है या नहीं निर्देशिका में पूर्णांक सेट पहले से मौजूद है। निर्देशिका पर परिभाषित करने के लिए केवल एक ही ऑपरेशन लुकअप और डालने है।

उपयोगी डेटा संरचनाओं के लिए अंतर्निहित समर्थन वाले भाषाओं में यह आसान होगा, लेकिन मैं सी के लिए एक विदेशी हूं और Google पर देखकर (आश्चर्यजनक रूप से) मेरे प्रश्न को संतोषजनक ढंग से जवाब नहीं देता हूं। इस परियोजना के अधिकार के बारे में लग रहा है:

http://uthash.sourceforge.net/

लेकिन मैं अपने हैश कुंजी जनरेटर के साथ आने की आवश्यकता होगी।

यह एक मानक, सरल समस्या है, इसलिए मुझे आशा है कि एक मानक और सरल समाधान होगा।

Answer 1

यह इस बात पर निर्भर करता है कि आप डेटा के साथ क्या करने जा रहे हैं। लेकिन शायद tsearch जो भी आप चाहते हैं वह पहले से ही करता है। आप प्रत्येक सेट के लिए एक क्रमबद्ध सरणी भी बना सकते हैं और bsearch के साथ मानों को देख सकते हैं, हालांकि प्रदर्शन सम्मिलन के दौरान हो सकता है।

संपादित करें: यदि आप एक (बाहरी) लाइब्रेरी की तलाश में हैं, तो आपको कुछ सी और सी ++ हैश टेबल कार्यान्वयन here की तुलना मिलेगी। लेख के लेखक ने khash नामक एक सामान्य हेडर कार्यान्वयन लिखा है। तो आप बाइनरी संकलित हैं कोई अतिरिक्त निर्भरता नहीं है।

Answer 2

अपने आप को एक सरल हैश तालिका लागू करें। यह आपको एक बेहतर प्रोग्रामर बना देगा, जब आप जानते हैं कि अपने आप को कैसे कार्यान्वित किया जाए।

http://en.wikipedia.org/wiki/Hash_table

Answer 3

संपादित करें: माफ करना, मैं जवाब देने शुरू कर दिया के रूप में यह सी है ++ और नहीं सी हाँ तो आप अपने हैश फंक्शन और यह कोड अपने आप से जब से तुम पहले से ही एक सेट का औसत आयाम पता खोजना चाहिए .. यह इतना मुश्किल नहीं है, बस एक अच्छा हैश फ़ंक्शन चुनें! लेकिन अगर आप यह जांचना चाहते हैं कि कोई निर्देशिका पहले से मौजूद है या नहीं, तो आपको एक ही सेट में एक पूरे सेट को कोडोड करने की आवश्यकता होगी। एक तरह से

int hashcode = initvalue 
for (int i = 0; i < 0; ++i) 
    hashcode = calc_code(hashcode, number_set[i], i); 

कि hashfunction पिछला मान, वर्तमान संख्या और वर्तमान सूचकांक पर निर्भर करता है:

आप iteratively सेट के एकल संख्या hashing द्वारा की कोशिश कर सकते हैं।

एसटीएल सेट के बारे में क्या?

#include <set> 

int nums[6] = {1,6,34,2,67,41}; 
set<int> numbers; 

for(int i = 0; i < 6; ++i) numbers.insert(nums[i]); 

for(set<int>::const_iterator iter = numbers.begin(); iter != numbers.end(); ++iter) 
    cout << *iter << ' '; 

का उपयोग करते हुए इस डेटा संरचना आप आसानी से अपने सभी सेट स्टोर कर सकते हैं, लेकिन आप यह भी कोई तरीका होना चाहिए अगर एक सेट पहले से ही निर्देशिका में शामिल किया गया है की जाँच करने के। यह स्पष्ट नहीं है: क्या आप जानना चाहते हैं कि एक सेट जिसमें सभी समान तत्व निर्देशिका में पहले से मौजूद हैं?

आप सभी तत्वों की जाँच करके मैन्युअल रूप से ऐसा कर सकते हैं लेकिन जब से तुम तुम एक अद्वितीय संख्या में सेट के तत्वों हैश और सेट के नक्शे का उपयोग करने के लिए एक रास्ता खोजने चाहिए उनमें से लाखों लोगों की ..

Answer 4

तो है मैं आपको सही ढंग से समझता हूं, आप पूर्णांक के सेट के सेट का प्रतिनिधित्व करना चाहते हैं जो मुझे नहीं लगता कि यह विशेष रूप से मामूली है।

पहला बिंदु पूर्णांक के एक सेट का प्रतिनिधित्व करना है।

intset *newset(int size) 
{ 
    intset *set; 
    set = malloc(sizeof(intset) + sizeof(int)*(size-1)); 
    if (set) set->size = size; 
    return set; 
} 

साथ की तुलना में आप एक नया सेट (तत्वों की एक निश्चित संख्या के साथ) बना सकते हैं

typedef struct { 
    int size; 
    int elems[1]; 
} intset; 

और set->elems[0]=i1; ... साथ तत्वों की दुकान: सबसे आसान तरीका है इस तरह एक चर आकार सरणी का उपयोग किया जाएगा।

एक और विकल्प बिट सरणी का उपयोग करना होगा, लेकिन कार्यान्वयन स्टोर करने के लिए पूर्णांक की प्रकृति पर निर्भर करेगा (उदाहरण के लिए वे एक निश्चित सीमा के भीतर हैं? क्या वे आमतौर पर सेट में समूहों में दिखाई देते हैं?)।

एक बार जब आप अपने पूर्णांक सेट करते हैं तो आपको एक तुलना फ़ंक्शन की आवश्यकता होगी (यह निर्धारित करने के लिए कि दो सेटों में एक ही तत्व हैं)। यदि आपने किसी सेट का प्रतिनिधित्व करने के लिए सरणी का चयन किया है और आप उस सरणी को सॉर्ट करते हैं, तो यह जांचना बहुत आसान है कि दो सेट समान हैं या नहीं; यदि यह बिटमैप है, तो यह इस बात पर निर्भर करेगा कि आपने इसे कैसे कार्यान्वित किया है।

अब, सेट के सेट के लिए आप एक (सॉर्टेड) ​​वेक्टर चुन सकते हैं, ताकि तत्वों को डालने के दौरान आपको समय-समय पर आकार बदलने की आवश्यकता हो या एक हैश तालिका हो। बाद के मामले में आपको पूर्णांक के सेट के लिए हैश फ़ंक्शन लिखना होगा (संभवतः मौजूदा फ़ंक्शंस का उपयोग करना!)।

जैसा कि मैंने कहा, यह मेरे लिए तुच्छ नहीं लगता है, मुझे आश्चर्य नहीं है कि Google ने मदद नहीं की है।

यह बेहद जटिल नहीं है, हालांकि, आपको आगे बढ़ने से पहले कुछ निर्णय लेना होगा।