Python에서 두 개의 정렬 된 목록 결합

Python에서 두 개의 정렬 된 목록 결합

---

두 개의 개체 목록이 있습니다. 각 목록은 이미 datetime 유형 인 개체의 속성에 따라 정렬되어 있습니다. 두 목록을 하나의 정렬 된 목록으로 결합하고 싶습니다. 정렬을 수행하는 가장 좋은 방법입니까 아니면 파이썬에서 이것을 수행하는 더 현명한 방법이 있습니까?

---

사람들이이 문제를 지나치게 복잡하게 만드는 것 같습니다. 두 목록을 결합한 다음 정렬하면됩니다.

>>> l1 = [1, 3, 4, 7]
>>> l2 = [0, 2, 5, 6, 8, 9]
>>> l1.extend(l2)
>>> sorted(l1)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

.. 또는 더 짧음 (수정없이 l1) :

>>> sorted(l1 + l2)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

..쉬운! 또한 두 개의 내장 함수 만 사용하므로 목록의 크기가 합리적이라고 가정하면 루프에서 정렬 / 병합을 구현하는 것보다 빠릅니다. 더 중요한 것은 위의 코드가 훨씬 적고 읽기 쉽다는 것입니다.

목록이 큰 경우 (예 : 수십만 개 이상), 대체 / 사용자 지정 정렬 방법을 사용하는 것이 더 빠를 수 있지만 먼저 수행 할 다른 최적화가있을 수 있습니다 (예 : 수백만 개의 datetime개체를 저장하지 않음 ).

timeit.Timer().repeat()(기능을 1000000 번 반복하는) 사용하여 ghoseb의 솔루션 에 대해 느슨하게 벤치마킹했으며 sorted(l1+l2)훨씬 빠릅니다.

merge_sorted_lists ..

[9.7439379692077637, 9.8844599723815918, 9.552299976348877]

sorted(l1+l2) ..

[2.860386848449707, 2.7589840888977051, 2.7682540416717529]

---

파이썬에서 이것을 수행하는 더 현명한 방법이 있습니까?

이것은 언급되지 않았으므로 계속 진행할 것입니다 . Python 2.6+의 heapq 모듈 에는 병합 stdlib 함수 가 있습니다. 당신이 원하는 것이 일을 끝내는 것이라면 이것이 더 나은 아이디어 일 수 있습니다. 물론 직접 구현하고 싶다면 병합 정렬을 병합하는 것이 좋습니다.

>>> list1 = [1, 5, 8, 10, 50]
>>> list2 = [3, 4, 29, 41, 45, 49]
>>> from heapq import merge
>>> list(merge(list1, list2))
[1, 3, 4, 5, 8, 10, 29, 41, 45, 49, 50]

다음 은 문서 입니다.

---

len(l1 + l2) ~ 1000000사용 하지 않는 한 짧게 이야기하십시오 .

L = l1 + l2
L.sort()

그림 및 소스 코드에 대한 설명은 여기 에서 찾을 수 있습니다 .

그림은 다음 명령으로 생성되었습니다.

$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin

---

이것은 단순히 병합입니다. 각 목록을 스택처럼 취급하고 스택 중 하나가 비어있을 때까지 두 스택 헤드 중 더 작은 항목을 계속해서 결과 목록에 추가합니다. 그런 다음 나머지 모든 항목을 결과 목록에 추가합니다.

---

ghoseb의 솔루션 에는 약간의 결함이 있어 O (n)이 아닌 O (n ** 2)가됩니다.
문제는 이것이 수행되고 있다는 것입니다.

item = l1.pop(0)

연결된 목록 또는 deques를 사용하면 O (1) 작업이므로 복잡성에 영향을 미치지 않지만 파이썬 목록은 벡터로 구현되므로 l1의 나머지 요소를 한 칸 남긴 O (n) 작업을 복사합니다. . 이것은 목록을 통과 할 때마다 수행되므로 O (n) 알고리즘을 O (n ** 2) 알고리즘으로 바꿉니다. 이것은 소스 목록을 변경하지 않고 현재 위치 만 추적하는 방법을 사용하여 수정할 수 있습니다.

수정 된 알고리즘과 dbr이 제안한 간단한 정렬 (l1 + l2) 비교를 벤치마킹 해 보았습니다.

def merge(l1,l2):
    if not l1:  return list(l2)
    if not l2:  return list(l1)

    # l2 will contain last element.
    if l1[-1] > l2[-1]:
        l1,l2 = l2,l1

    it = iter(l2)
    y = it.next()
    result = []

    for x in l1:
        while y < x:
            result.append(y)
            y = it.next()
        result.append(x)
    result.append(y)
    result.extend(it)
    return result

나는 다음과 같이 생성 된 목록으로 이것을 테스트했다.

l1 = sorted([random.random() for i in range(NITEMS)])
l2 = sorted([random.random() for i in range(NITEMS)])

다양한 크기의 목록에 대해 다음 타이밍을 얻습니다 (100 회 반복).

# items:  1000   10000 100000 1000000
merge  :  0.079  0.798 9.763  109.044 
sort   :  0.020  0.217 5.948  106.882

따라서 실제로 dbr이 옳은 것처럼 보입니다. 매우 큰 목록을 예상하지 않는 한 sorted ()를 사용하는 것이 좋지만 알고리즘 복잡성이 더 나쁩니다. 손익분기 점은 각 소스 목록에서 약 백만 개의 항목 (총 200 만 개)에 있습니다.

병합 접근 방식의 한 가지 장점은 생성기로 다시 작성하는 것이 사소하다는 것입니다. 이는 상당히 적은 메모리를 사용합니다 (중간 목록이 필요 없음).

[편집] 나는 datedatetime 객체 인 " " 필드를 포함하는 객체 목록을 사용하여 질문에 더 가까운 상황으로 이것을 재 시도했습니다 . 위의 알고리즘은 비교를 위해 변경되었으며 .date정렬 방법은 다음과 같이 변경되었습니다.

return sorted(l1 + l2, key=operator.attrgetter('date'))

이것은 상황을 약간 변경합니다. 비교 비용이 더 비싸다는 것은 구현의 일정한 시간 속도에 비해 수행하는 숫자가 더 중요하다는 것을 의미합니다. 즉, 병합은 잃어버린 영역을 보완하여 대신 100,000 개의 항목에서 sort () 메서드를 능가합니다. 훨씬 더 복잡한 객체 (예 : 큰 문자열 또는 목록)를 기반으로 비교하면이 균형이 훨씬 더 이동 될 수 있습니다.

# items:  1000   10000 100000  1000000[1]
merge  :  0.161  2.034 23.370  253.68
sort   :  0.111  1.523 25.223  313.20

[1] : 참고 : 실제로 1,000,000 개 항목에 대해 10 번만 반복했고 그에 따라 상당히 느려서 확장했습니다.

---

이것은 두 개의 정렬 된 목록을 간단히 병합하는 것입니다. 두 개의 정렬 된 정수 목록을 병합하는 아래의 샘플 코드를 살펴보십시오.

#!/usr/bin/env python
## merge.py -- Merge two sorted lists -*- Python -*-
## Time-stamp: "2009-01-21 14:02:57 ghoseb"

l1 = [1, 3, 4, 7]
l2 = [0, 2, 5, 6, 8, 9]

def merge_sorted_lists(l1, l2):
    """Merge sort two sorted lists

    Arguments:
    - `l1`: First sorted list
    - `l2`: Second sorted list
    """
    sorted_list = []

    # Copy both the args to make sure the original lists are not
    # modified
    l1 = l1[:]
    l2 = l2[:]

    while (l1 and l2):
        if (l1[0] <= l2[0]): # Compare both heads
            item = l1.pop(0) # Pop from the head
            sorted_list.append(item)
        else:
            item = l2.pop(0)
            sorted_list.append(item)

    # Add the remaining of the lists
    sorted_list.extend(l1 if l1 else l2)

    return sorted_list

if __name__ == '__main__':
    print merge_sorted_lists(l1, l2)

이것은 datetime 객체에서 잘 작동합니다. 도움이 되었기를 바랍니다.

---

from datetime import datetime
from itertools import chain
from operator import attrgetter

class DT:
    def __init__(self, dt):
        self.dt = dt

list1 = [DT(datetime(2008, 12, 5, 2)),
         DT(datetime(2009, 1, 1, 13)),
         DT(datetime(2009, 1, 3, 5))]

list2 = [DT(datetime(2008, 12, 31, 23)),
         DT(datetime(2009, 1, 2, 12)),
         DT(datetime(2009, 1, 4, 15))]

list3 = sorted(chain(list1, list2), key=attrgetter('dt'))
for item in list3:
    print item.dt

출력 :

2008-12-05 02:00:00
2008-12-31 23:00:00
2009-01-01 13:00:00
2009-01-02 12:00:00
2009-01-03 05:00:00
2009-01-04 15:00:00

나는 이것이 큰 데이터의 경우에도 멋진 순수 Python 병합 알고리즘보다 빠르다고 확신합니다. Python 2.6 heapq.merge은 완전히 다른 이야기입니다.

---

Python의 정렬 구현 "timsort"는 특히 정렬 된 섹션을 포함하는 목록에 최적화되어 있습니다. 또한 C로 작성되었습니다.

http://bugs.python.org/file4451/timsort.txt
http://en.wikipedia.org/wiki/Timsort

사람들이 언급했듯이, 일정한 인자로 비교 함수를 더 많이 호출 할 수 있습니다 (그러나 많은 경우 더 짧은 기간에 더 많이 호출 할 수 있습니다!).

그러나 나는 이것에 의존하지 않을 것입니다. – 다니엘 나 다시

저는 파이썬 개발자들이 팀 정렬을 유지하거나 적어도이 경우 O (n) 인 정렬을 유지하기 위해 최선을 다하고 있다고 믿습니다.

일반화 된 정렬 (즉, 제한된 값 도메인에서 기수 정렬을 분리)
은 직렬 시스템에서 O (n log n) 미만으로 수행 할 수 없습니다. – 배리 켈리

맞습니다. 일반적인 경우 정렬은 그보다 빠를 수 없습니다. 그러나 O ()가 상한이기 때문에, 임의의 입력에서 timsort가 O (n log n) 인 것은 sorted (L1) + sorted (L2)가 주어지면 O (n) 인 것과 모순되지 않습니다.

---

재귀 구현은 다음과 같습니다. 평균 성능은 O (n)입니다.

def merge_sorted_lists(A, B, sorted_list = None):
    if sorted_list == None:
        sorted_list = []

    slice_index = 0
    for element in A:
        if element <= B[0]:
            sorted_list.append(element)
            slice_index += 1
        else:
            return merge_sorted_lists(B, A[slice_index:], sorted_list)

    return sorted_list + B

또는 공간 복잡성이 개선 된 생성기 :

def merge_sorted_lists_as_generator(A, B):
    slice_index = 0
    for element in A:
        if element <= B[0]:
            slice_index += 1
            yield element       
        else:
            for sorted_element in merge_sorted_lists_as_generator(B, A[slice_index:]):
                yield sorted_element
            return        

    for element in B:
        yield element

---

def merge_sort(a,b):

    pa = 0
    pb = 0
    result = []

    while pa < len(a) and pb < len(b):
        if a[pa] <= b[pb]:
            result.append(a[pa])
            pa += 1
        else:
            result.append(b[pb])
            pb += 1

    remained = a[pa:] + b[pb:]
    result.extend(remained)


return result

---

두 목록을 반복하는 병합 정렬의 병합 단계 구현 :

def merge_lists(L1, L2):
    """
    L1, L2: sorted lists of numbers, one of them could be empty.

    returns a merged and sorted list of L1 and L2.
    """

    # When one of them is an empty list, returns the other list
    if not L1:
        return L2
    elif not L2:
        return L1

    result = []
    i = 0
    j = 0

    for k in range(len(L1) + len(L2)):
        if L1[i] <= L2[j]:
            result.append(L1[i])
            if i < len(L1) - 1:
                i += 1
            else:
                result += L2[j:]  # When the last element in L1 is reached,
                break             # append the rest of L2 to result.
        else:
            result.append(L2[j])
            if j < len(L2) - 1:
                j += 1
            else:
                result += L1[i:]  # When the last element in L2 is reached,
                break             # append the rest of L1 to result.

    return result

L1 = [1, 3, 5]
L2 = [2, 4, 6, 8]
merge_lists(L1, L2)               # Should return [1, 2, 3, 4, 5, 6, 8]
merge_lists([], L1)               # Should return [1, 3, 5]

아직 알고리즘에 대해 배우는 중입니다. 코드가 어떤면에서나 개선 될 수 있는지 알려주세요. 피드백에 감사드립니다. 감사합니다!

---

글쎄, 순진한 접근 방식 (2 개의 목록을 큰 목록으로 결합하고 정렬)은 O (N * log (N)) 복잡성입니다. 반면에 수동으로 병합을 구현하면 (파이썬 라이브러리의 준비된 코드에 대해 알지 못하지만 전문가는 아닙니다) 복잡성은 O (N)이 될 것입니다. 이 아이디어는 Barry Kelly의 게시물에 잘 설명되어 있습니다.

---

병합 정렬의 '병합'단계를 사용하면 O (n) 시간에 실행됩니다.

에서 위키 피 디아 (의사 코드) :

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    end while
    while length(left) > 0 
        append left to result
    while length(right) > 0 
        append right to result
    return result

---

반복에서 일어나는 일을 배우는 것과 더 일관된 방식으로하고 싶다면 이것을 시도하십시오

def merge_arrays(a, b):
    l= []

    while len(a) > 0 and len(b)>0:
        if a[0] < b[0]: l.append(a.pop(0))    
        else:l.append(b.pop(0))

    l.extend(a+b)
    print( l )

---

import random

    n=int(input("Enter size of table 1")); #size of list 1
    m=int(input("Enter size of table 2")); # size of list 2
    tb1=[random.randrange(1,101,1) for _ in range(n)] # filling the list with random
    tb2=[random.randrange(1,101,1) for _ in range(m)] # numbers between 1 and 100
    tb1.sort(); #sort the list 1 
    tb2.sort(); # sort the list 2
    fus=[]; # creat an empty list
    print(tb1); # print the list 1
    print('------------------------------------');
    print(tb2); # print the list 2
    print('------------------------------------');
    i=0;j=0;  # varialbles to cross the list
    while(i<n and j<m):
        if(tb1[i]<tb2[j]):
            fus.append(tb1[i]); 
            i+=1;
        else:
            fus.append(tb2[j]);
            j+=1;

    if(i<n):
        fus+=tb1[i:n];
    if(j<m):
        fus+=tb2[j:m];

    print(fus);

  # this code is used to merge two sorted lists in one sorted list (FUS) without
  #sorting the (FUS)

---

병합 정렬의 병합 단계를 사용했습니다. 그러나 나는 발전기를 사용했다 . 시간 복잡도 O (n)

def merge(lst1,lst2):
    len1=len(lst1)
    len2=len(lst2)
    i,j=0,0
    while(i<len1 and j<len2):
        if(lst1[i]<lst2[j]):
                yield lst1[i]
                i+=1
        else:
                yield lst2[j]
                j+=1
    if(i==len1):
        while(j<len2):
                yield lst2[j]
                j+=1
    elif(j==len2):
        while(i<len1):
                yield lst1[i]
                i+=1
l1=[1,3,5,7]
l2=[2,4,6,8,9]
mergelst=(val for val in merge(l1,l2))
print(*mergelst)

---

def compareDate(obj1, obj2):
    if obj1.getDate() < obj2.getDate():
        return -1
    elif obj1.getDate() > obj2.getDate():
        return 1
    else:
        return 0



list = list1 + list2
list.sort(compareDate)

목록을 제자리에 정렬합니다. 두 개체를 비교하기위한 고유 한 함수를 정의하고 해당 함수를 기본 정렬 함수에 전달합니다.

버블 정렬을 사용하지 마십시오. 성능이 끔찍합니다.

---

이것은 l1 및 l2를 편집하지 않고 선형 시간의 내 솔루션입니다 .

def merge(l1, l2):
  m, m2 = len(l1), len(l2)
  newList = []
  l, r = 0, 0
  while l < m and r < m2:
    if l1[l] < l2[r]:
      newList.append(l1[l])
      l += 1
    else:
      newList.append(l2[r])
      r += 1
  return newList + l1[l:] + l2[r:]

---

이 코드는 시간 복잡도가 O (n)이고 정량화 함수가 매개 변수로 주어지면 모든 데이터 유형의 목록을 병합 할 수 있습니다 func. 병합 된 새 목록을 생성하고 인수로 전달 된 목록을 수정하지 않습니다.

def merge_sorted_lists(listA,listB,func):
    merged = list()
    iA = 0
    iB = 0
    while True:
        hasA = iA < len(listA)
        hasB = iB < len(listB)
        if not hasA and not hasB:
            break
        valA = None if not hasA else listA[iA]
        valB = None if not hasB else listB[iB]
        a = None if not hasA else func(valA)
        b = None if not hasB else func(valB)
        if (not hasB or a<b) and hasA:
            merged.append(valA)
            iA += 1
        elif hasB:
            merged.append(valB)
            iB += 1
    return merged

---

도움이 되었기를 바랍니다. 매우 간단하고 간단합니다.

l1 = [1, 3, 4, 7]

l2 = [0, 2, 5, 6, 8, 9]

l3 = l1 + l2

l3.sort ()

인쇄 (l3)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

참고 URL : https://stackoverflow.com/questions/464342/combining-two-sorted-lists-in-python