क्या कोई मेरे लिए वर्तमान में उपयोग कर रहे एक से अधिक कुशल कार्टेसियन उत्पाद एल्गोरिदम प्रदर्शित कर सकता है (मान लीजिए कि एक है)। मैंने एसओ के चारों ओर देखा है और थोड़ा गुस्से में है लेकिन कुछ भी स्पष्ट नहीं देख सकता है इसलिए मुझे कुछ याद आ रहा है।कुशल कार्टेशियन उत्पाद एल्गोरिदम
foreach (int i in is) {
foreach (int j in js) {
//Pair i and j
}
}
यह मेरे कोड में जो कुछ करता है उसका एक बहुत ही सरल संस्करण है। दो पूर्णांक लुकअप कुंजियां हैं जिनका उपयोग एक/अधिक ऑब्जेक्ट्स को पुनर्प्राप्त करने के लिए किया जाता है और दो लुकअप से सभी ऑब्जेक्ट्स को नई ऑब्जेक्ट्स में जोड़ा जाता है।
एक बहुत बड़ी जटिल प्रणाली में कोड का यह छोटा ब्लॉक एक प्रमुख प्रदर्शन बाधा बन जाता है क्योंकि यह डेटासेट स्केल पर चल रहा है। इनमें से कुछ वस्तुओं और लुकअप को संग्रहीत करने के लिए उपयोग की जाने वाली डेटा संरचनाओं में सुधार करके कम हो सकता है लेकिन मुझे लगता है कि मुख्य मुद्दा अभी भी कार्टेशियन उत्पाद की गणना है।
संपादित
तो एल्गोरिथ्म के अपने विशिष्ट उपयोग पर कुछ अधिक पृष्ठभूमि को देखने के लिए अगर कोई चाल है कि मैं मार्क की टिप्पणी के जवाब में उपयोग कर सकते हैं हो सकता है। समग्र प्रणाली एक SPARQL क्वेरी इंजन है जो ग्राफ़ डेटा के सेट पर SPARQL क्वेरीज को प्रोसेस करता है, SPARQL एक पैटर्न आधारित भाषा है, इसलिए प्रत्येक क्वेरी में पैटर्न की एक श्रृंखला होती है जो ग्राफ़ के विरुद्ध मेल खाती है। ऐसे मामले में जहां दो अनुवर्ती पैटर्नों में कोई सामान्य चर नहीं है (वे अलग हैं) समग्र क्वेरी के संभावित समाधानों का सेट प्राप्त करने के लिए दो पैटर्न द्वारा उत्पादित समाधानों के कार्टेशियन उत्पाद की गणना करना आवश्यक है। पैटर्न की कोई संख्या हो सकती है और मुझे कई बार कार्टेशियन उत्पादों की गणना करना पड़ सकता है जो संभावित समाधानों में काफी घातीय विस्तार कर सकते हैं यदि क्वेरी विवादित पैटर्न की श्रृंखला से बना है।
मौजूदा जवाब मुझे शक है वहाँ क्या किसी भी चाल है कि लागू हो सकते हैं से किसी तरहअद्यतन
तो मैंने सोचा कि मैं क्या मैं आदेश कार्तीय करने की ज़रूरत को कम करने में कार्यान्वित पर एक अपडेट पोस्ट करेंगे उत्पाद और इस प्रकार आम तौर पर क्वेरी इंजन को अनुकूलित करते हैं। ध्यान दें कि उत्पादों की पूरी तरह से पूरी तरह से खत्म करना हमेशा संभव नहीं होता है, लेकिन यह अनुकूलित करना लगभग हमेशा संभव है ताकि दो सेटों का आकार जुड़ना बहुत छोटा हो।
चूंकि प्रत्येक बीजीपी (मूल ग्राफ पैटर्न) जो ट्रिपल पैटर्न का एक सेट है, को ब्लॉक (संक्षेप में) के रूप में निष्पादित किया जाता है, इंजन इष्टतम प्रदर्शन के लिए बीजीपी के भीतर पैटर्न को पुन: व्यवस्थित करने के लिए स्वतंत्र है। उदाहरण के लिए निम्नलिखित BGP पर विचार करें: के रूप में क्वेरी है
?a :someProperty ?b .
?c :anotherProperty ?d .
?b a :Class .
निष्पादित एक कार्तीय उत्पाद के बाद से पहली पैटर्न के परिणामों दूसरा पैटर्न से संबंध तोड़ना हैं की आवश्यकता है ताकि पहले दो पैटर्न के परिणामों के एक कार्तीय उत्पाद है उनके व्यक्तिगत परिणाम इस परिणाम में हमें वास्तव में आवश्यकता होने की तुलना में कहीं अधिक परिणाम होंगे, क्योंकि तीसरा पैटर्न पहले पैटर्न के संभावित परिणामों को प्रतिबंधित करता है लेकिन हम बाद में इस प्रतिबंध को लागू नहीं करते हैं। लेकिन हम तो जैसे को पुन: व्यवस्थित करता है, तो:
?b a :Class .
?a :someProperty ?b .
?c :anotherProperty ?d .
हम अभी भी एक कार्तीय उत्पाद की आवश्यकता होगी अंतिम परिणाम प्राप्त करने के लिए 2 और 3 पैटर्न अभी भी संबंध तोड़ना हैं के बाद से, लेकिन पुन: क्रम देकर हम 2 पैटर्न के परिणामों का आकार प्रतिबंधित जिसका मतलब है कि हमारे कार्टेशियन उत्पाद का आकार बहुत छोटा होगा।
हमारे द्वारा किए गए कुछ अन्य अनुकूलन हैं लेकिन मैं उन्हें यहां पोस्ट नहीं कर रहा हूं क्योंकि यह SPARQL इंजन आंतरिकों की काफी विस्तृत चर्चा में शामिल होना शुरू कर देता है। अगर कोई अधिक जानकारी में रुचि रखता है तो बस एक टिप्पणी छोड़ या मुझे एक ट्वीट @RobVesse
http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx – tugberk