विशिष्ट रूप से 2 सूचियों को कैसे जोड़ना है

Question

मैं बहुत लंबी सूचियों के साथ काम कर रहा हूं और एक अद्वितीय तरीके से 2 सूचियों को संयोजित करने के लिए एक पुनरावृत्त समाधान के साथ आने की कोशिश कर रहा हूं।

उदाहरण के लिए, मेरे पास है सूचियों

a = [TF1,Tar1] 
b = [Tar1, TF1] 

मैं निम्नलिखित इटरेटर (यदि संभव हो) युक्त tuples हैं:

(TF1,Tar1)  
(TF1,TF1) 
(Tar1,Tar1) 

यह शामिल नहीं (Tar1, TF1) क्योंकि विपरीत आदेश पहले से ही है जोड़ा गया है।

मेरा वर्तमान दृष्टिकोण प्रत्येक सूची के माध्यम से लूप है और जो जोड़ा गया है उसका ट्रैक रखने के लिए एक शब्दकोश का उपयोग करें। यह रैम की एक बड़ी मात्रा ले रहा है क्योंकि सूची 12,000 लंबी है और सूची बी 15000 लंबी है। परिणामी शब्दकोश बनाने में * बी/2 प्रविष्टियां होती हैं जो इस मामले में 90 एम प्रविष्टियां होती हैं।

किसी भी सुझाव की सराहना की जाती है। धन्यवाद

Answer 1

असल में, समस्या दो सूचियों के बीच सामान्य तत्वों के साथ उत्पन्न होती है। आप आम और अद्वितीय तत्वों के संयोजन के मामलों को अलग कर सकते हैं, आप अपनी समस्या

का समाधान होगा यानी आप कार्तीय उत्पादों निम्नलिखित बनाने के लिए

a_unique X b_unique 
a_unique X b_common 
a_common X b_unique 
a_common X b_common 

चार मामलों में से

, पिछले एक एक समस्या पैदा होगा की जरूरत है क्योंकि यह गैर-अद्वितीय जोड़े बनाएगा। एक दूसरे विचार पर, अद्वितीय जोड़े के साथ अंतिम कार्टेशियन acommon से 2 तत्वों का एक साधारण चयन है।

अंत में, अलग-अलग रखने तत्वों एक सेट बनाने के द्वारा और दोनों सूचियों की और फिर बार-बार दोहराना किया जा सकता है, जबकि

>>> #Sample Lists 
>>> a = ['C0','C1','C2','A0','A1','A2'] 
>>> b = ['C0','C1','C2','B0','B1','B2'] 
>>> from itertools import product, combinations, chain 
>>> # Create sets for O(1) lookup 
>>> a_key = set(a) 
>>> b_key = set(b) 
>>> # Segerate elements to unique and common for both lists 
>>> a = {'common':a_key & b_key, 
     'unique':a_key - common} 
>>> b = {'common':a_key & b_key, 
     'unique':b_key - common} 
>>> # Create cartesian products forall the cases 
>>> list(chain.from_iterable([product(a['unique'], b['unique']), 
         product(a['unique'], b['common']), 
         product(a['common'], b['unique']), 
         combinations(a['common'], 2)])) 
[('A0', 'B0'), ('A0', 'B1'), ('A0', 'B2'), ('A1', 'B0'), ('A1', 'B1'), ('A1', 'B2'), ('A2', 'B0'), ('A2', 'B1'), ('A2', 'B2'), ('A0', 'C0'), ('A0', 'C1'), ('A0', 'C2'), ('A1', 'C0'), ('A1', 'C1'), ('A1', 'C2'), ('A2', 'C0'), ('A2', 'C1'), ('A2', 'C2'), ('C0', 'B0'), ('C0', 'B1'), ('C0', 'B2'), ('C1', 'B0'), ('C1', 'B1'), ('C1', 'B2'), ('C2', 'B0'), ('C2', 'B1'), ('C2', 'B2'), ('C0', 'C1'), ('C0', 'C2'), ('C1', 'C2')] 

Answer 2

की तुलना iteratively जोड़े उत्पन्न करने के लिए, आप itertools.product समारोह को देखने के लिए चाहता हूँ:

>>> l1 = [1, 2, 3] 
>>> l2 = [1, 3, 7] 
>>> import itertools 
>>> list(itertools.product(l1, l2)) 
[(1, 1), (1, 3), (1, 7), (2, 1), (2, 3), (2, 7), (3, 1), (3, 3), (3, 7)] 

हालांकि, मुझे नहीं लगता कि डुप्लिकेट जोड़े को पहले से देखे गए ट्रैक को ट्रैक किए बिना हटा देना संभव है।

में स्मृति डुप्लीकेट निकालने के लिए, मैं tuples सॉर्ट और यह एक सेट बनाना होगा:

>>> pairs = list(itertools.product(l1, l2)) 
>>> set(map(tuple, map(sorted, pairs))) 
set([(1, 2), (2, 7), (1, 3), (3, 3), (2, 3), (1, 7), (3, 7), (1, 1)]) 

आप स्मृति कम रखना चाहते हैं और आप डिस्क का उपयोग कर सकते हैं, तो मेरा सुझाव है कि किसी मर्ज प्रकार का उपयोग कर के समान डिस्क फ़ाइलों द्वारा समर्थित। itertools.product के परिणामस्वरूप पुनरावृत्ति करते समय, जोड़ी को सॉर्ट करें और इसे डिस्क पर लिखें। फिर विलय सॉर्ट का उपयोग करें और क्रमबद्ध सूची को पढ़ें, डुप्लिकेट को हटाएं (क्योंकि वे आसन्न होंगे)।

Answer 3

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

import itertools 

def product_without_reversed_duplicates(a, b): 
    a_set = set(a) 
    b_set = set(b) 
    dupes = set() 

    for x, y in itertools.product(a, b): 
     if (x, y) not in dupes: # take (x, y) only if it is not a dupe of a previous item 
      yield x, y 
      if x in b_set and y in a_set: # test if (y, x) will be generated later 
       dupes.add((y, x))   # if so, add it to the set to be skipped 

नोट इस मानता है कि कि a और b किसी भी आंतरिक डुप्लिकेट की जरूरत नहीं है, और है कि आप के रूप में ज्यादा संभव के रूप में (उत्पाद के आदेश सुरक्षित रखना चाहते हैं:

यहाँ कैसे मैं यह कर करेंगे केवल उलटा जोड़े को छोड़ना)। यदि a या b के भीतर डुप्लिकेट संभव है, तो आप ऊपर दिए गए के बजाय itertools.product(a_set, b_set) पर पुन: प्रयास करना चाहेंगे। हालांकि यह आपको मनमाना क्रम में परिणाम देगा। आप अपने आदेश को रखते हुए a और b को समर्पित करने के लिए अतिरिक्त चरणों के साथ उस पर काम कर सकते हैं, लेकिन अगर आपको इसकी आवश्यकता हो, तो मैं इसके लिए कोड को समझने के लिए इसे छोड़ दूंगा।

Answer 4

बल्कि मुश्किल है लेकिन O(n) अतिरिक्त मेमोरी के साथ ऐसा करने का एक तरीका है।

xs = ['a', 'b', 'd'] 
ys = ['b', 'a', 'c'] 

def unique(seq): 
    seen = set() 
    seen_add = seen.add 
    return [ x for x in seq if not (x in seen or seen_add(x))] 

xs = unique(xs) 
ys = unique(ys) 

x_added = set() 
for x in xs: 
    for y in ys: 
     if y in x_added and x in set(ys): 
      continue 
     print(x, y) 
    x_added.add(x) 

आउटपुट:

a b 
a a 
a c 
b b 
b c 
d b 
d a 
d c 

असल में, हम जानते हैं कि एक जोड़ी पहले से ही सामने आए है, अगर y पहले से ही है x रों में से एक अब तक सामने आए है, और x, ys में से एक है क्योंकि हम पिछले एस के लिए पहले से ही सभी y एस को फिर से सक्रिय कर दिया है। अनूठी आवश्यकता सिर्फ विशेष मामलों को आसान बनाती है।