Merge danh sách được sắp xếp trong python

Question

tôi có một loạt các danh sách được sắp xếp của các đối tượng, và một hàm so sánh

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), ...] 

những gì hiện magic cái nhìn như thế nào? Triển khai hiện tại của tôi là

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

nhưng điều đó không hiệu quả. Câu trả lời tốt hơn?

Answer 1

Thư viện chuẩn Python cung cấp phương thức cho nó: heapq.merge.
Như tài liệu nói, nó rất giống với việc sử dụng itertools (nhưng có nhiều hạn chế hơn); nếu bạn không thể sống với những hạn chế (hoặc nếu bạn không sử dụng Python 2.6), bạn có thể làm một cái gì đó như thế này:

sorted(itertools.chain(args), cmp) 

Tuy nhiên, tôi nghĩ rằng nó có mức độ phức tạp tương tự như giải pháp của riêng mình, mặc dù sử dụng vòng lặp nên cung cấp một số tối ưu hóa khá tốt và tăng tốc độ.

Answer 2

Tôi không biết liệu nó sẽ là bất kỳ nhanh hơn, nhưng bạn có thể đơn giản hóa nó với:

def GetObjKey(a): 
    return a.points 

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

Bạn cũng có thể, tất nhiên, sử dụng cmp hơn key nếu bạn thích.

Answer 3

Sử dụng mô-đun bisect. Từ tài liệu: "Mô-đun này cung cấp hỗ trợ để duy trì danh sách theo thứ tự được sắp xếp mà không phải sắp xếp danh sách sau mỗi lần chèn".

import bisect 

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

Answer 4

Thay vì sử dụng một danh sách, bạn có thể sử dụng một [đống] (http://en.wikipedia.org/wiki/Heap_(data_structure).

Các chèn là O (log (n)), do sáp nhập a, b và c sẽ được O (n log (n))

Trong Python, bạn có thể sử dụng heapq module

Answer 5

Một giải pháp dòng bằng cách sử dụng sắp xếp:..

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

IMO giải pháp này là rất dễ đọc

Sử dụng mô-đun heapq, nó có thể hiệu quả hơn, nhưng tôi chưa thử nghiệm nó. Bạn không thể chỉ định hàm cmp/key trong heapq, vì vậy bạn phải thực hiện Obj để được sắp xếp hoàn toàn.

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

Answer 6

Ở đây bạn đi: một loại hợp đầy đủ chức năng cho các danh sách (chuyển thể từ loại của tôi here):

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) 

Gọi nó như thế này:

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

Đối với biện pháp tốt, tôi sẽ ném vào một vài thay đổi đối với lớp Obj của bạn:

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 

• Rút ra từ đối tượng
• đèo self-__init__()
• Hãy __cmp__ một hàm thành viên
• Thêm một chức năng str() thành viên để trình bày Obj như chuỗi

Answer 7

Tôi thích câu trả lời Roberto Liffredo của. Tôi không biết về heapq.merge(). Hmmmph.

Dưới đây là những gì các giải pháp hoàn chỉnh trông giống như sử dụng Roberto Đội khách dẫn trước:

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 

Hoặc:

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

Answer 8

Tôi hỏi một câu hỏi tương tự và có một số câu trả lời tuyệt vời:

• Joining a set of ordered-integer yielding Python iterators

Các giải pháp tốt nhất từ ​​câu hỏi đó là biến thể của thuật toán hợp nhất, mà bạn có thể đọc về ở đây:

• Wikipedia: Merge Algorithm

Answer 9

Dưới đây là một ví dụ về một hàm chạy trong thời gian O (n) so sánh .

Bạn có thể thực hiện việc này nhanh hơn bằng cách tạo một trình lặp a và b và tăng chúng.

Tôi đã gọi đơn giản là chức năng hai lần để hợp nhất 3 danh sách:

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 

Tuy nhiên, heapq.merge sử dụng một hỗn hợp của phương pháp này và chất đống các yếu tố hiện tại của tất cả danh sách, vì vậy nên thực hiện tốt hơn nhiều