Modo migliore per concatenare due lista ordinata di interi

Question

lascia supporre che ho una lista e un altro tupla ciascuno di essi sono già ordinati:

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

Cosa avrei bisogno è quello di aggiungere tutti gli elementi da B in A in in modo tale che A rimanga ordinato.

Soluzione ho potuto venire con era:

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

assumendo Una di dimensione m, e B di dimensione n; questa soluzione richiederebbe O (m x n) nel peggiore dei casi, come posso farlo funzionare meglio?

Answer 1

Un modo semplice sarebbe quella heapq.merge:

A = [10, 20, 30, 40] 

B = (20, 60, 81, 90) 

from heapq import merge 

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

uscita:

10 
20 
20 
30 
40 
60 
81 
90 

Alcuni timing utilizzando l'altra O(n) soluzione:

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 

Se si voleva a rotolare il proprio questo è un po 'più veloce di unione:

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 

Alcune timing:

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 modulo "possibilità di mantenere una lista in modo ordinato, senza dover ordinamento dopo ogni inserzione":

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

Questa soluzione non crea una nuova lista.

---

prega di notare che bisect.insort(A, b) equivale a

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

Anche se la ricerca è veloce (O (log n)), l'inserimento è lento (O(n)).

Answer 3

modificati

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

Answer 4

È necessario eseguire una stampa. Ma la fusione "tradizionale" genera una nuova lista; quindi hai bisogno di alcune modifiche per espandere un elenco.

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

Ecco una soluzione in 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

Un sacco di buona discussione in questo post ! Litigare sul tempismo è difficile, così ho scritto alcuni script temporali. È abbastanza rudimentale ma penso che lo farà per ora. Ho allegato anche i risultati.

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() 

questo è il risultato:

E 'chiaro che la modifica della lista è il principale collo di bottiglia, quindi la creazione di una nuova lista è la strada da percorrere.