बूलियन खोज

Question

मैं लगभग 100 संभावित मान, यानी के साथ कई सरणियों है:

a[0] = (a, b, c, d) 
a[1] = (a, e) 
a[2] = (d, f, g) 

मैं तेजी लौटने के लिए जो सरणियों शामिल करना चाहते हैं (एक || ख) & & (घ || ई)

इस उदाहरण में, 0 और 1

मैं थोड़ा सा ऑपरेशन के बारे में सोच रहा था ... जैसे "1111" द्वारा "abcd" का प्रतिनिधित्व करना; "विज्ञापन" द्वारा "विज्ञापन", और इसी तरह। फिर मैं "या" को थोड़ा सा या तो हल कर सकता हूं, और फिर जांच कर सकता हूं कि दोनों शून्य-शून्य

कोई बेहतर समाधान पर विचार कर सकता है? यह बहुत प्रैक्टिकल नहीं है क्योंकि यह बहुत बढ़िया प्रतीत नहीं होता है

क्या कोई डीबीएमएस है जो जल्दी से कर सकता है? मैंने mongodb के साथ प्रयास किया, लेकिन ऐसा लगता है कि उन्होंने अभी तक "$ और" फ़ंक्शन नहीं जोड़ा है (डॉक्टर कहते हैं कि यह संस्करण 1.9.1 पर है, लेकिन मैं केवल 1.9.0 डाउनलोड कर सकता हूं, और यह स्थिर नहीं है)

I मान लीजिए कि यह एक "बूलियन सर्च" है, जो कि हर समय Google के समान होता है ... इसलिए मुझे लगता है कि

Answer 1

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

Answer 2

किस अर्थ में यह मापनीय नहीं है? डेटा प्रति 16 बिट्स (बिट) सरणी खराब नहीं है! मुझे यकीन नहीं है कि आप इसके लिए डीबीएमएस क्यों चाहते हैं; यदि आपको (उम्मीद है कि सरणी के ब्लॉक) की आवश्यकता है, तो आप वहां बाइनरी डेटा डाल सकते हैं, और क्वेरी के लिए इसे बाहर खींच सकते हैं। जब तक आप अरबों arrays होने की योजना बना रहे हैं।

तत्वों की छोटी संख्या के लिए, बिट तर्क सबसे तेज़ है। लेकिन यदि आप 100 से अधिक मूल्यों से आगे बढ़ना शुरू करते हैं, तो बाइनरी (या यहां तक ​​कि रैखिक!) खोज को व्यवस्थित करने और सरणी रखने के लिए तेज़ होगा। सटीक कटऑफ बिंदु खोजने के लिए आपको अपने सिस्टम पर बेंचमार्क करना होगा, लेकिन यदि आपके सरणी में प्रत्येक 4 ~ तत्व हैं, तो मुझे आम तौर पर रैखिक खोज तेज़ी से मिलती है (उन तत्वों की घटनाओं की गिनती करना जिन्हें आप बूलियन तर्क में ढूंढ रहे हैं आप जाते हैं), और यह कि एक ही बिंदु पर बाइनरी गणित धड़कता है कि द्विआधारी प्रतिनिधित्व भी बड़े हो जाते हैं।

Answer 3

स्टोर एक Trie, जैसे के रूप में अपने सरणियों,

a 
b 
    c 
    d 
e 
d 
f 
    g 

रूप में अच्छी तरह अभिव्यक्ति से एक Trie बनाएँ, जैसे,

a 
b 
    d 
    e 
d 
e 
b 
d 
e 

आप पूर्व के खिलाफ बाद trie मिलान कर सकते हैं (किसी भी अनदेखी वे मान जो अभिव्यक्ति में नहीं हैं, यानी, 'सी', 'एफ', और 'जी') समाधान प्राप्त करने के लिए। मैं आपको त्रिभुज प्रतिनिधित्व और मिलान करने वाले एल्गोरिदम का विवरण छोड़ देता हूं।

Answer 4

जैसा कि आपने कहा था कि संभावित मान लगभग 100 हैं, लेकिन आपके पास बहुत सारे सरणी हैं, मुझे लगता है कि एक हैश तालिका बिट स्तर ऑपरेशन से बेहतर है।
ईजी।
2.

for each array a in arrays  
    for each value v in array 
    sum+= ht[v] 
    if sum == 3 
     print found 
     break 

(ऊपर डुप्लिकेट हालांकि साथ नहीं होगा करने के लिए अभिव्यक्ति में मूल्यों के साथ सेट एक हैश तालिका, यानी एक, 1 और डी के लिए ख सेट, ई सेट है!)
लूप के लिए पहला समानांतर किया जा सकता है, शायद नक्शा-कम ढांचे या यहां तक ​​कि ओपनएमपी के साथ।
(दूसरे के लिए बीटीडब्ल्यू भी समांतर किया जा सकता है!)
यह सरणी में पूरे तत्वों का थोड़ा सा प्रतिनिधित्व करने और AND या OR करने से तेज़ होना चाहिए। आपको मूल रूप से सर्वोत्तम मामले के साथ लाभ होता है (उदाहरण के लिए ए और डी पहले 2 तत्व हैं!) दोनों तरीकों के लिए सबसे खराब मामला समान होता है (यदि प्रत्येक तत्व के लिए किया जा सकता है तो हो सकता है)