Lepszy sposób na łączenie dwóch posortowaną listę liczb całkowitych

Question

Załóżmy mam jedną listę i kolejny krotki oboje są już klasyfikowane:

A = [10, 20, 30, 40] 
B = (20, 60, 81, 90) 

Co będzie mi potrzebne, aby dodać wszystkie elementy z B do A w taki sposób, że A pozostaje posortowany.

Rozwiązanie mogę wyposażone były:

for item in B: 
    for i in range(0, len(A)): 
     if item > A[i]: 
      i += 1 
     else: 
      A.insert(i, item) 

przy założeniu formatu m i B o rozmiarze n; to rozwiązanie w najgorszym przypadku zająłby O (m x n), jak mogę go poprawić?

Answer 1

Prostym sposobem byłoby heapq.merge:

A = [10, 20, 30, 40] 

B = (20, 60, 81, 90) 

from heapq import merge 

for ele in merge(A,B): 
    print(ele) 

wyjściowa:

10 
20 
20 
30 
40 
60 
81 
90 

Niektóre czasy wykorzystujące inne rozwiązanie: O(n)

In [53]: A = list(range(10000)) 

In [54]: B = list(range(1,20000,10)) 

In [55]: timeit list(merge(A,B)) 
100 loops, best of 3: 2.52 ms per loop 

In [56]: %%timeit 
C = [] 
i = j = 0 
while i < len(A) and j < len(B): 
    if A[i] < B[j]: 
     C.append(A[i]) 
     i += 1 
    else: 
     C.append(B[j]) 
     j += 1 
C += A[i:] + B[j:] 
    ....: 
100 loops, best of 3: 4.29 ms per loop 
In [58]: m =list(merge(A,B)) 
In [59]: m == C 
Out[59]: True 

Jeśli chciał toczyć własną rękę jest to nieco szybciej niż Merge:

def merger_try(a, b): 
    if not a or not b: 
     yield chain(a, b) 
    iter_a, iter_b = iter(a), iter(b) 
    prev_a, prev_b = next(iter_a), next(iter_b) 
    while True: 
     if prev_a >= prev_b: 
      yield prev_b 
      try: 
       prev_b = next(iter_b) 
      except StopIteration: 
       yield prev_a 
       break 
     else: 
      yield prev_a 
      try: 
       prev_a = next(iter_a) 
      except StopIteration: 
       yield prev_b 
       break 
    for ele in chain(iter_b, iter_a): 
     yield ele 

Niektóre taktowania:

In [128]: timeit list(merge(A,B)) 
1 loops, best of 3: 771 ms per loop 

In [129]: timeit list(merger_try(A,B)) 
1 loops, best of 3: 581 ms per loop 

In [130]: list(merger_try(A,B)) == list(merge(A,B)) 
Out[130]: True 

In [131]: %%timeit         
C = [] 
i = j = 0 
while i < len(A) and j < len(B): 
    if A[i] < B[j]: 
     C.append(A[i]) 
     i += 1 
    else: 
     C.append(B[j]) 
     j += 1 
C += A[i:] + B[j:] 
    .....: 
1 loops, best of 3: 919 ms per loop 

Answer 2

bisect moduł „zapewnia wsparcie dla prowadzenia listy posortowanych bez konieczności posortować po każdym włożeniu”:

import bisect 
for b in B: 
    bisect.insort(A, b) 

To rozwiązanie nie tworzy nową listę.

---

Uwaga bisect.insort(A, b) jest równoważna

A.insert(bisect.bisect_right(A, b), b) 

Choć wyszukiwania jest szybki (O (log n)), wkładanie jest powolny (O(n)).

Answer 3

edytowany

l1 = [10,20,30,40] 
l2 = (10,20,30,40) 
l2 = list(l2) 
l1 = sorted(l1+l2) 

Answer 4

Trzeba przeprowadzić scalenie. Ale "tradycyjne" scalenie generuje nową listę; więc potrzebujesz trochę modyfikacji, aby rozwinąć jedną listę.

ia = ib = 0 
while ib < len(B): 
    if ia < len(A) and A[ia] < B[ib]: 
     if ia < len(A): 
      ia += 1 
    else: 
     A.insert(ia + 1, B[ib]) 
     ib += 1 

Answer 5

Oto rozwiązanie w O(n):

A = [10, 20, 30, 40] 
B = [20, 60, 81, 90] 
C = [] 
i = j = 0 
while i < len(A) and j < len(B): 
    if A[i] < B[j]: 
     C.append(A[i]) 
     i += 1 
    else: 
     C.append(B[j]) 
     j += 1 
C += A[i:] + B[j:] 

Answer 6

Wiele dobrych dyskusji w tym poście ! Twierdzenie o taktowaniu jest trudne, dlatego napisałem skrypt czasowy. To dość elementarne, ale myślę, że na razie to zrobi. Dołączyłem też wyniki.

import timeit 
import math 
import matplotlib.pyplot as plt 
from collections import defaultdict 


setup = """ 
import bisect 
import heapq 
from random import randint 


A = sorted((randint(1, 10000) for _ in range({}))) 
B = sorted((randint(1, 10000) for _ in range({}))) 


def bisect_sol(A, B): 
    for b in B: 
     bisect.insort(A, b) 


def merge_sol(A, B): 
    ia = ib = 0 
    while ib < len(B): 
     if ia < len(A) and A[ia] < B[ib]: 
      if ia < len(A): 
       ia += 1 
     else: 
      A.insert(ia + 1, B[ib]) 
      ib += 1 


def heap_sol(A, B): 
    return heapq.merge(A, B) 


def sorted_sol(A, B): 
    return sorted(A + B) 
""" 


sols = ["bisect", "merge", "heap", "sorted"] 
times = defaultdict(list) 
iters = [100, 1000, 2000, 5000, 10000, 20000, 50000, 100000] 

for n in iters: 
    for sol in sols: 
     t = min(timeit.repeat(stmt="{}_sol(A, B)".format(sol), setup=setup.format(n, n), number=1, repeat=5)) 
     print("({}, {}) done".format(n, sol)) 
     times[sol].append(math.log(t)) 

for sol in sols: 
    plt.plot(iters, times[sol]) 
plt.xlabel("iterations") 
plt.ylabel("log time") 
plt.legend(sols) 
plt.show() 

Jest to wynikiem:

To jasne, że modyfikowanie listy jest głównym wąskim gardłem, więc tworzenie nowa lista jest droga.