मर्ज अनुसार क्रमबद्ध सूचियों अजगर

Question

में मैं वस्तुओं की क्रमबद्ध सूचियों का एक समूह है, और एक तुलना समारोह

class Obj : 
    def __init__(p) : 
     self.points = p 
def cmp(a, b) : 
    return a.points < b.points 

a = [Obj(1), Obj(3), Obj(8), ...] 
b = [Obj(1), Obj(2), Obj(3), ...] 
c = [Obj(100), Obj(300), Obj(800), ...] 

result = magic(a, b, c) 
assert result == [Obj(1), Obj(1), Obj(2), Obj(3), Obj(3), Obj(8), ...] 

कैसा magic नज़र करता है? मेरा वर्तमान कार्यान्वयन

def magic(*args) : 
    r = [] 
    for a in args : r += a 
    return sorted(r, cmp) 

लेकिन यह काफी अक्षम है। बेहतर जवाब?

Answer 1

अजगर मानक पुस्तकालय इसके लिए एक विधि प्रदान करता है: heapq.merge।
दस्तावेज़ीकरण के अनुसार, यह itertools (लेकिन अधिक सीमाओं के साथ) का उपयोग करने के समान है; अगर आप उन सीमाओं के साथ नहीं रह सकते (या यदि आप अजगर 2.6 का उपयोग नहीं करते) आप कुछ इस तरह कर सकते हैं:

sorted(itertools.chain(args), cmp) 

हालांकि, मुझे लगता है कि अपनी खुद की समाधान के रूप में एक ही जटिलता है, हालांकि iterators का उपयोग कर देना चाहिए कुछ काफी अच्छा अनुकूलन और गति में वृद्धि। एक सूची का उपयोग करने का

Answer 2

मैं चाहे वह किसी भी तेज किया जाएगा पता नहीं है, लेकिन आप के साथ इसे आसान बनाने सकता है:

def GetObjKey(a): 
    return a.points 

return sorted(a + b + c, key=GetObjKey) 

तुम भी, बेशक, cmp बजाय key इस्तेमाल कर सकते हैं यदि आप पसंद करते हैं।

Answer 3

bisect मॉड्यूल का उपयोग करें। प्रलेखन से: "यह मॉड्यूल प्रत्येक सम्मिलन के बाद सूची को सॉर्ट किए बिना सॉर्ट किए गए क्रम में सूची बनाए रखने के लिए समर्थन प्रदान करता है।"

import bisect 

def magic(*args): 
    r = [] 
    for a in args: 
     for i in a: 
      bisect.insort(r, i) 
    return r 

Answer 4

इसके बजाय, आप उपयोग कर सकते हैं एक [ढेर] (http://en.wikipedia.org/wiki/Heap_(data_structure)।

प्रविष्टि हे (लॉग (एन)) है, इसलिए विलय एक, बी और सी ओ हो जाएगा (एन (एन लॉग इन करें))

अजगर में, आप उपयोग कर सकते हैं heapq module

Answer 5

एक पंक्ति समाधान हल कर का उपयोग करते हुए:।।

def magic(*args): 
    return sorted(sum(args,[]), key: lambda x: x.points) 

IMO इस समाधान बहुत पठनीय है

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

import heapq 
def magic(*args): 
    h = [] 
    for a in args: 
    heapq.heappush(h,a) 
    return [i for i in heapq.heappop(h) 

Answer 6

ये रहा:

def merge(*args): 
    import copy 
    def merge_lists(left, right): 
     result = [] 
     while left and right: 
      which_list = (left if left[0] <= right[0] else right) 
      result.append(which_list.pop(0)) 
     return result + left + right 
    lists = list(args) 
    while len(lists) > 1: 
     left, right = copy.copy(lists.pop(0)), copy.copy(lists.pop(0)) 
     result = merge_lists(left, right) 
     lists.append(result) 
    return lists.pop(0) 

इसे इस तरह कॉल::

merged_list = merge(a, b, c) 
for item in merged_list: 
    print item 

अच्छा उपाय के लिए, मैं सूचियों के लिए एक पूरी तरह से कामकाज मर्ज प्रकार (मेरी तरह here से रूपांतरित) आपके ओब्जे वर्ग में कुछ बदलावों में फेंक देगा:

class Obj(object): 
    def __init__(self, p) : 
     self.points = p 
    def __cmp__(self, b) : 
     return cmp(self.points, b.points) 
    def __str__(self): 
     return "%d" % self.points 

• __init__()
• करने के लिए वस्तु
• पास self से निकाले जाते हैं __cmp__ बनाओ एक सदस्य समारोह
• एक str() सदस्य समारोह स्ट्रिंग

Answer 7

मैं रॉबर्टो Liffredo का जवाब चाहते रूप Obj पेश करने के लिए जोड़ें। मुझे heapq.merge() के बारे में पता नहीं था। Hmmmph।

class Obj(object): 
    def __init__(self, p) : 
     self.points = p 
    def __cmp__(self, b) : 
     return cmp(self.points, b.points) 
    def __str__(self): 
     return "%d" % self.points 

a = [Obj(1), Obj(3), Obj(8)] 
b = [Obj(1), Obj(2), Obj(3)] 
c = [Obj(100), Obj(300), Obj(800)] 

import heapq 

sorted = [item for item in heapq.merge(a,b,c)] 
for item in sorted: 
    print item 

या::

यहाँ पूर्ण समाधान रॉबर्टो के नेतृत्व का उपयोग कर कैसा दिखता है

for item in heapq.merge(a,b,c): 
    print item 

Answer 8

मैं एक ऐसी ही प्रश्न पूछा और कुछ उत्कृष्ट जवाब मिला:

• Joining a set of ordered-integer yielding Python iterators

उस सवाल से सबसे अच्छा समाधान मर्ज एल्गोरिथ्म, जो तुम यहाँ के बारे में पढ़ सकते हैं के वेरिएंट हैं:

• Wikipedia: Merge Algorithm

Answer 9

नीचे एक समारोह है कि हे (एन) की तुलना में चलाता है का एक उदाहरण है ।

आप इसे और बी इटरेटर बनाने और उन्हें बढ़ाने के द्वारा इसे तेज़ी से बना सकते हैं।

मैं बस दो बार 3 सूचियों विलय करने के लिए समारोह कहा जाता है:

def zip_sorted(a, b): 
    ''' 
    zips two iterables, assuming they are already sorted 
    ''' 
    i = 0 
    j = 0 
    result = [] 
    while i < len(a) and j < len(b): 
     if a[i] < b[j]: 
      result.append(a[i]) 
      i += 1 
     else: 
      result.append(b[j]) 
      j += 1 
    if i < len(a): 
     result.extend(a[i:]) 
    else: 
     result.extend(b[j:]) 
    return result 

def genSortedList(num,seed): 
    result = [] 
    for i in range(num): 
     result.append(i*seed) 
    return result 

if __name__ == '__main__': 
    a = genSortedList(10000,2.0) 
    b = genSortedList(6666,3.0) 
    c = genSortedList(5000,4.0) 
    d = zip_sorted(zip_sorted(a,b),c) 
    print d 

हालांकि, heapq.merge इस पद्धति का एक मिश्रण का उपयोग करता है और सभी सूचियों की वर्तमान तत्वों ढेर लगाना है, तो ज्यादा बेहतर प्रदर्शन करना चाहिए