Supongamos que tengo dos listas list_1 y list_2
list_1 = [1, 5, 10] list_2 = [3, 4, 15]
Quiero obtener una lista de tuplas que contengan elementos de list_1 y list_2 de modo que la diferencia entre los números en una tupla esté bajo una constante c.
Por ejemplo, supongamos que c es 2, entonces las tuplas que tendría serían: [(1, 3), (5, 3), (5, 4)]
Por supuesto, uno puede iterar sobre ambas listas y verificar que la diferencia entre 2 elementos sea menor que c, pero eso tiene una complejidad de n ^ 2 y preferiría reducir esa complejidad.
Aquí hay una implementación de la idea de Marat de los comentarios:
import bisect def close_pairs(list1,list2,c): #assumes that list2 is sorted for x in list1: i = bisect.bisect_left(list2,xc) j = bisect.bisect_right(list2,x+c) yield from ((x,y) for y in list2[i:j]) list_1 = [1, 5, 10] list_2 = [3, 4, 15] print(list(close_pairs(list_1,list_2,2))) #prints [(1, 3), (5, 3), (5, 4)] Para demostrar la mejora potencial de esta estrategia sobre lo que podría considerarse como el enfoque "ingenuo", tomemos el timeit .
import timeit setup_naive = ''' import numpy list_a = numpy.random.randint(0, 2500, 500).tolist() list_b = numpy.random.randint(0, 2500, 500).tolist() c = 2 def close_pairs(list_a, list_b, c): yield from ((x,y) for x in list_a for y in list_b if abs(xy) <= c) ''' setup_john_coleman = ''' import bisect import numpy list_a = numpy.random.randint(0, 2500, 500).tolist() list_b = numpy.random.randint(0, 2500, 500).tolist() c = 2 def close_pairs(list_a, list_b, c): list_a = sorted(list_a) list_b = sorted(list_b) for x in list_a: i = bisect.bisect_left(list_b,xc) j = bisect.bisect_right(list_b,x+c) yield from ((x,y) for y in list_b[i:j]) ''' print(f"john_coleman: {timeit.timeit('list(close_pairs(list_a, list_b, c))', setup=setup_john_coleman, number=1000):.2f}") print(f"naive: {timeit.timeit('list(close_pairs(list_a, list_b, c))', setup=setup_naive, number=1000):.2f}")En una computadora portátil práctica que da resultados como:
john_coleman: 0.50 naive: 18.35Si las listas están ordenadas como sugiere su ejemplo, elimine la clasificación y luego esto tiene una complejidad de tiempo de ejecución O (M + N + P) donde M y N son los tamaños de lista y P es el número de pares cercanos. Mantiene un índice i para que ys[i] sea el valor de y más pequeño, no demasiado pequeño, y luego recorre ys[i:...] siempre que no sean demasiado grandes, produciendo cada par.
def close_pairs(xs, ys, c): xs = sorted(xs) ys = sorted(ys) + [float('inf')] i = 0 for x in xs: while x - ys[i] > c: i += 1 j = i while ys[j] - x <= c: yield x, ys[j] j += 1Compara los resultados con listas/rangos 1000 veces más grandes que tu ejemplo:
904.4 ms close_pairs_naive 4.9 ms close_pairs_John_Coleman 1.8 ms close_pairs_Kelly_BundyCódigo de referencia:
from timeit import timeit import random import bisect from collections import deque def close_pairs_naive(list_a, list_b, c): yield from ((x,y) for x in list_a for y in list_b if abs(xy) <= c) def close_pairs_John_Coleman(list_a, list_b, c): list_a = sorted(list_a) list_b = sorted(list_b) for x in list_a: i = bisect.bisect_left(list_b,xc) j = bisect.bisect_right(list_b,x+c) yield from ((x,y) for y in list_b[i:j]) def close_pairs_Kelly_Bundy(xs, ys, c): xs = sorted(xs) ys = sorted(ys) + [float('inf')] i = 0 for x in xs: while x - ys[i] > c: i += 1 j = i while ys[j] - x <= c: yield x, ys[j] j += 1 funcs = [ close_pairs_naive, close_pairs_John_Coleman, close_pairs_Kelly_Bundy, ] xs = random.choices(range(15000), k=3000) ys = random.choices(range(15000), k=3000) c = 2 args = xs, ys, c expect = sorted(funcs[0](*args)) for func in funcs: result = sorted(func(*args)) print(result == expect, func.__name__, len(result)) print() for _ in range(3): for func in funcs: t = timeit(lambda: deque(func(*args), 0), number=1) print('%6.1f ms ' % (t * 1e3), func.__name__) print()