एक सेट के सभी जोड़े को कुशलतापूर्वक कैसे प्राप्त करें?

Question

Set की ऑब्जेक्ट को देखते हुए, मैं इसके सभी (अनियंत्रित) जोड़े से घूमना चाहता हूं।

उदाहरण: सेट = {1, 2, 3}, जोड़े: (1, 2), (1, 3), (2, 3)।

जब एक Vector<Integer> के साथ काम कर, एक-एक तत्व के सूचकांक की मदद से इस लक्ष्य को हासिल कर सकते हैं:

for (int i = 0; i < vector.size(); i++) 
    for (int j = i + 1; j < vector.size(); j++) 
    // Do something with vector.get(i) and vector.get(j) 

लेकिन एक Set<Integer> में तत्वों कोई सूचकांक होते हैं।

अब तक का सबसे अच्छा समाधान, Set को Vector में परिवर्तित करना और ऊपर दिए गए समाधान का उपयोग करना है।

क्या कोई और अधिक कुशल/सीधा समाधान है?

Answer 1

List<Integer> list = new ArrayList<Integer>(mySet); 
for (int i = 0; i < list .size(); i++) 
    for (int j = i + 1; j < list .size(); j++) 
     // Do something with vector.get(i) and vector.get(j) 

Answer 2

इस एल्गोरिथ्म = n (n -1)/2 के लिए जटिलता के संदर्भ में, इस प्रकार O (n^2) सबसे अच्छा आप प्राप्त कर सकते हैं (अनुक्रमिक) है।

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

इसके अलावा, आप समानांतरता और थ्रेड/प्रक्रियाओं के बीच काम को विभाजित कर सकते हैं क्योंकि एल्गोरिदम शर्मनाक समानांतर प्रतीत होता है।