लुकअप

Question

के बिना तेजी से अद्वितीय संयोजन (डुप्लिकेट के साथ सूची से) मुझे लगता है कि इस तथ्य के बावजूद कि अद्वितीय वस्तुओं की सूची से किसी भी आकार के अद्वितीय संयोजन उत्पन्न करने के लिए ऑनलाइन बहुत सारे एल्गोरिदम और फ़ंक्शंस हैं, इसमें कोई भी उपलब्ध नहीं है गैर-अद्वितीय मदों की एक सूची के मामले (यानी सूची एक ही मूल्य की पुनरावृत्ति से युक्त।)

सवाल एक गैर-अद्वितीय से सभी अद्वितीय संयोजन एक जनरेटर समारोह में पर-THE-फ्लाई उत्पन्न करने के लिए कैसे है बिना डुप्लीकेट को फ़िल्टर करने की कम्प्यूटेशनल महंगी आवश्यकता?

अब

सवाल यह आसान है मैं क्या हासिल करने की उम्मीद के बारे में अधिक स्पष्टता प्रदान करने के लिए एक इनाम प्रेरित जवाब नहीं है के रूप में:

पहले के कोड कैसे करता है, तो एक संयोजन comboB माना जाता है की जाँच करने के illustrating प्रदान करते हैं

comboA = [1,2,2] 
comboB = [2,1,2] 
print("B is a duplicate of A:", comboA.sort()==comboB.sort()) 

बी के दिए गए उदाहरण में एक का डुप्लिकेट और प्रिंट() है सच प्रिंट: एक और एक (comboA) का डुप्लिकेट हो।

एक जनरेटर समारोह ऑन-द-मक्खी गैर-अद्वितीय सूची के मामले में अद्वितीय संयोजन प्रदान करने में सक्षम होने का समस्या यहाँ हल किया जाता है: Getting unique combinations from a non-unique list of items, FASTER?, लेकिन उपलब्ध कराई गई जनरेटर समारोह लुकअप की जरूरत है और आवश्यकता है स्मृति क्या के मामले में समस्याओं का कारण बनता संयोजन की एक बड़ी राशि।

उत्तर प्रदान समारोह के वर्तमान संस्करण में किसी भी खोज के बिना काम करता है और यहाँ सही जवाब प्रतीत होता है, लेकिन ...

पीछे लुकअप से छुटकारा पाने के लक्ष्य पीढ़ी तेजी लाने के लिए है डुप्लीकेट के साथ सूची के मामले में अद्वितीय संयोजनों का।

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

----------------- 
k: 6 len(ls): 48 
Combos Used Code        Time 
--------------------------------------------------------- 
12271512 len(list(combinations(ls,k)))  : 2.036 seconds 
12271512 len(list(subbags(ls,k)))   : 50.540 seconds 
12271512 len(list(uniqueCombinations(ls,k))) : 8.174 seconds 
12271512 len(set(combinations(sorted(ls),k))): 7.233 seconds 
--------------------------------------------------------- 
12271512 len(list(combinations(ls,k)))  : 2.030 seconds 
     1 len(list(subbags(ls,k)))   : 0.001 seconds 
     1 len(list(uniqueCombinations(ls,k))) : 3.619 seconds 
     1 len(set(combinations(sorted(ls),k))): 2.592 seconds 

समय से ऊपर दो चरम सीमाओं के उदाहरण देकर स्पष्ट करना: कोई डुप्लिकेट और केवल डुप्लिकेट

यहाँ कुछ समय वर्तमान स्थिति को वर्णन करने। अन्य सभी समय इन दोनों के बीच हैं।

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

Answer 1

आपके आउटपुट को पोस्ट-प्रोसेसिंग/फ़िल्टर करने के बजाय, आप अपनी इनपुट सूची को प्री-प्रोसेस कर सकते हैं। इस तरह, आप पहली जगह डुप्लिकेट उत्पन्न करने से बच सकते हैं। प्री-प्रोसेसिंग में या तो सॉर्टिंग (या collections.Counter का उपयोग करके) इनपुट शामिल है।एक संभव पुनरावर्ती अहसास है:

def subbags(bag, k): 
    a = sorted(bag) 
    n = len(a) 
    sub = [] 

    def index_of_next_unique_item(i): 
     j = i + 1 

     while j < n and a[j] == a[i]: 
      j += 1 

     return j 

    def combinate(i): 
     if len(sub) == k: 
      yield tuple(sub) 
     elif n - i >= k - len(sub): 
      sub.append(a[i]) 
      yield from combinate(i + 1) 
      sub.pop() 
      yield from combinate(index_of_next_unique_item(i)) 

    yield from combinate(0) 

bag = [1, 2, 3, 1, 2, 1] 
k = 3 
i = -1 

print(sorted(bag), k) 
print('---') 

for i, subbag in enumerate(subbags(bag, k)): 
    print(subbag) 

print('---') 
print(i + 1) 

आउटपुट:

[1, 1, 1, 2, 2, 3] 3 
--- 
(1, 1, 1) 
(1, 1, 2) 
(1, 1, 3) 
(1, 2, 2) 
(1, 2, 3) 
(2, 2, 3) 
--- 
6 

प्रत्यावर्तन के लिए कुछ ढेर स्थान आवश्यक है, लेकिन यह इनपुट छँटाई पैदा करने और दोहराता की निकालने की तुलना में काफी कम समय + स्मृति का उपयोग करना चाहिए +।

Answer 2

वर्तमान राज्य के अत्याधुनिक की तुलना में एक 50 से शुरू में प्रेरित एक 100 प्रतिनिधि bounties से (एक अजगर विस्तार मॉड्यूल सी में पूरी तरह से लिखा के बजाय) इस समय है:

एक कुशल एल्गोरिथ्म और कार्यान्वयन जो सर्वोत्तम (और औसत) मामले में स्पष्ट (set + combinations) दृष्टिकोण से बेहतर है, और सबसे खराब मामले में इसके साथ प्रतिस्पर्धी है।

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

def iterFastUniqueCombos(lstList, comboSize, percUniqueThresh=60): 

    lstListSorted = sorted(lstList) 
    lenListSorted = len(lstListSorted) 

    percUnique = 100.0 - 100.0*(lenListSorted-len(set(lstListSorted)))/lenListSorted 

    lstComboCandidate = [] 
    setUniqueCombos = set() 

    def idxNextUnique(idxItemOfList): 
     idxNextUniqueCandidate = idxItemOfList + 1 
     while (
       idxNextUniqueCandidate < lenListSorted 
        and 
       lstListSorted[idxNextUniqueCandidate] == lstListSorted[idxItemOfList] 
     ): # while 
      idxNextUniqueCandidate += 1 
     idxNextUnique = idxNextUniqueCandidate 
     return idxNextUnique 

    def combinate(idxItemOfList): 
     if len(lstComboCandidate) == sizeOfCombo: 
      yield tuple(lstComboCandidate) 
     elif lenListSorted - idxItemOfList >= sizeOfCombo - len(lstComboCandidate): 
      lstComboCandidate.append(lstListSorted[idxItemOfList]) 
      yield from combinate(idxItemOfList + 1) 
      lstComboCandidate.pop() 
      yield from combinate(idxNextUnique(idxItemOfList)) 

    if percUnique > percUniqueThresh: 
     from itertools import combinations 
     allCombos = combinations(lstListSorted, comboSize) 
     for comboCandidate in allCombos: 
      if comboCandidate in setUniqueCombos: 
       continue 
      yield comboCandidate 
      setUniqueCombos.add(comboCandidate) 
    else: 
     yield from combinate(0) 
    #:if/else  
#:def iterFastUniqueCombos() 

नीचे प्रदान की समय दिखाने के ऊपर iterFastUniqueCombos() जनरेटर समारोह uniqueCombinations() संस्करण मामले में सूची अद्वितीय तत्व के कम से कम 60 प्रतिशत है और आधारित uniqueCombinations() जनरेटर (set + combinations) पर के रूप में बदतर नहीं है पर एक स्पष्ट लाभ प्रावधान है कि विपरीत स्थिति में समारोह जहां यह बहुत एक ( के बीच (set + combinations) और (no lookups) सूची में अद्वितीय तत्वों की राशि के लिए 60% दहलीज पर संस्करण स्विचन के कारण) iterUniqueCombos() तुलना में तेजी से हो जाता है:

=========== sizeOfCombo: 6 sizeOfList: 48 noOfUniqueInList 1 percUnique 2 
Combos: 12271512 print(len(list(combinations(lst,k))))   : 2.04968 seconds. 
Combos:  1 print(len(list(  iterUniqueCombos(lst,k)))) : 0.00011 seconds. 
Combos:  1 print(len(list( iterFastUniqueCombos(lst,k)))) : 0.00008 seconds. 
Combos:  1 print(len(list( uniqueCombinations(lst,k)))) : 3.61812 seconds. 

========== sizeOfCombo: 6 sizeOfList: 48 noOfUniqueInList 48 percUnique 100 
Combos: 12271512 print(len(list(combinations(lst,k))))   : 1.99383 seconds. 
Combos: 12271512 print(len(list(  iterUniqueCombos(lst,k)))) : 49.72461 seconds. 
Combos: 12271512 print(len(list( iterFastUniqueCombos(lst,k)))) : 8.07997 seconds. 
Combos: 12271512 print(len(list( uniqueCombinations(lst,k)))) : 8.11974 seconds. 

========== sizeOfCombo: 6 sizeOfList: 48 noOfUniqueInList 27 percUnique 56 
Combos: 12271512 print(len(list(combinations(lst,k))))   : 2.02774 seconds. 
Combos: 534704 print(len(list(  iterUniqueCombos(lst,k)))) : 1.60052 seconds. 
Combos: 534704 print(len(list( iterFastUniqueCombos(lst,k)))) : 1.62002 seconds. 
Combos: 534704 print(len(list( uniqueCombinations(lst,k)))) : 3.41156 seconds. 

========== sizeOfCombo: 6 sizeOfList: 48 noOfUniqueInList 31 percUnique 64 
Combos: 12271512 print(len(list(combinations(lst,k))))   : 2.03539 seconds. 
Combos: 1114062 print(len(list(  iterUniqueCombos(lst,k)))) : 3.49330 seconds. 
Combos: 1114062 print(len(list( iterFastUniqueCombos(lst,k)))) : 3.64474 seconds. 
Combos: 1114062 print(len(list( uniqueCombinations(lst,k)))) : 3.61857 seconds.