दो तत्वों में प्रत्येक तत्व की एक जोड़ी तुलना करें और शीर्ष 3 रैंकलिस्ट

Question

दो सेट दिए गए, मैं प्रत्येक सेट के प्रत्येक तत्व के साथ एक सेट में प्रत्येक तत्व की जोड़ी तुलना कैसे करूं।

मैं प्रारंभिक सेट में प्रत्येक तत्व के लिए शीर्ष 3 परिणाम प्राप्त करना चाहते हैं। \

वहाँ कार्य को हल करने के एक तेज़ तरीका है। मैं कार्य करने का एक और अधिक पागल तरीका ढूंढ रहा हूं।

set1 = set([str(item) for item in range(100)]) # Pls. note originally set contains strings 
set2 = set([str(item) for item in range(50,150)]) # set([str(item) for item in range(50,100)]) 

for item in set1: 
    max = [-1,-1,-1] 
    for stuff in set2: 
    val = magicComp(item,stuff) 
    if val > max[0]: 
     max[2] = max[1] 
     max[1] = max[0] 
     max[0] = val 
    elif val > max[1]: 
     max[2] = max[1] 
     max[1] = val 
    elif val > max[2]: 
     max[2] = val 

Answer 1

आपका जवाब बुरा नहीं है, यह प्रत्येक यात्रा पर सरणी छँटाई की तुलना में बेहतर है, लेकिन यह अभी भी हे है (एन^2)।

चूंकि आप जो सरणी इंडेक्स चाहते हैं उसे जानते हैं, इसलिए आप quickselect एल्गोरिदम का उपयोग कर सकते हैं ताकि 0 (0 लॉग इन) समय में MagicComp फ़ंक्शन पर आधारित इंडेक्स 0,1,2 मिल सके। यह हे के लिए अपने रन-टाइम को कम कर देंगे (एन * लोग इन एन)

कि कड़ी में कोड के आधार पर, अपने कोड कुछ ऐसा दिखाई देगा:

results = {} 
ls2 = list(set2) 
for el in set1: 
    results[el] = [select(ls2, ii) for ii in [0,1,2]] 

Answer 2

हम वास्तव में pythonic होना चाहते हैं,

from functools import partial 

most_valueable = { 
    item1: sorted(set2, key=partial(magicComp, item1), reverse=True)[0:3] 
    for item1 in set1 
} 

जैसे कुछ चाल चलाना चाहिए। यह अभी भी ओ (एन² एलएन एन) है, हालांकि, हमें प्रत्येक आइटम के लिए दूसरे सेट को फिर से क्रमबद्ध करने की आवश्यकता है।

Answer 3

एहम्मम, तेज़ तरीका। आपका मूल संस्करण समय आंतरिक जटिलता O(3n) प्रत्येक आंतरिक पुनरावृत्ति के लिए है।

नीचे समय जटिलता O(nlg3) के साथ तेज़ है।

from queue import PriorityQueue 

q = PriorityQueue(maxsize=3) 
for item in set1: 
    map(q.put, (-1 * magicComp(item,stuff) for stuff in set2)) 
    max = [] 
    while not q.empty(): 
     max.append(-1 * q.get())