Étant donné 2 listes d'entiers, comment trouver les plages qui ne se chevauchent pas ?

Question

Étant donné que

x = [5, 30, 58, 72]
y = [8, 35, 53, 60, 66, 67, 68, 73]

Le but est d'itérer à travers x_i et trouver la valeur de y qui est plus grande que x_i mais pas plus que x_i+1

Supposons que les deux listes soient triées et que tous les éléments soient uniques, la sortie souhaitée étant donnée par l'option x y y est :

[(5, 8), (30, 35), (58, 60), (72, 73)]

J'ai essayé :

def per_window(sequence, n=1):
    """
    From http://stackoverflow.com/q/42220614/610569
        >>> list(per_window([1,2,3,4], n=2))
        [(1, 2), (2, 3), (3, 4)]
        >>> list(per_window([1,2,3,4], n=3))
        [(1, 2, 3), (2, 3, 4)]
    """
    start, stop = 0, n
    seq = list(sequence)
    while stop <= len(seq):
        yield tuple(seq[start:stop])
        start += 1
        stop += 1

x = [5, 30, 58, 72]
y = [8, 35, 53, 60, 66, 67, 68, 73]

r = []

for xi, xiplus1 in per_window(x, 2):
    for j, yj in enumerate(y):
        if yj > xi and yj < xiplus1:
            r.append((xi, yj))
            break

# For the last x value.
# For the last x value.
for j, yj in enumerate(y):
    if yj > xiplus1:
        r.append((xiplus1, yj))
        break

Mais existe-t-il un moyen plus simple de réaliser la même chose avec numpy , pandas ou autre chose ?

Answer 1

Vous pouvez utiliser numpy.searchsorted con side='right' pour trouver l'indice de la première valeur dans y qui est plus grande que x et ensuite extraire les éléments avec l'index ; Une version simple qui assume il y a toujours une valeur dans y plus grand que tout élément dans x pourrait être :

x = np.array([5, 30, 58, 72])
y = np.array([8, 35, 53, 60, 66, 67, 68, 73])

np.column_stack((x, y[np.searchsorted(y, x, side='right')]))
#array([[ 5,  8],
#       [30, 35],
#       [58, 60],
#       [72, 73]])

---

Étant donné que y est trié :

np.searchsorted(y, x, side='right')
# array([0, 1, 3, 7])

renvoie l'indice de la première valeur dans y qui est plus grande que la valeur correspondante dans x .

Answer 2

Nous pouvons utiliser pd.DataFrame sur la liste avec merge_asof con direction = forward i.e

new = pd.merge_asof(pd.DataFrame(x,index=x), pd.DataFrame(y,index=y),on=0,left_index=True,direction='forward')
out = list(zip(new[0],new.index))

Si vous n'avez pas besoin de correspondances exactes, il vous faut passer allow_exact_matches=False à fusionner_asof

Sortie :

[(5, 8), (30, 35), (58, 60), (72, 73)]

Answer 3

Vous pouvez construire une nouvelle liste en itérant sur x zippé avec lui-même -- décalé de 1 index et annexé avec le dernier élément de y -- puis en itérant sur y, vérifier la condition à chaque passage et rompre la boucle la plus interne.

out = []
for x_low, x_high in zip(x, x[1:]+y[-1:]):
    for yy in y:
        if (yy>x_low) and (yy<=x_high):
            out.append((x_low,yy))
            break

out
# returns:
[(5, 8), (30, 35), (58, 60), (72, 73)]

Answer 4

def find(list1,list2):
    final = []
    for i in range(len(list1)):
        pos=0
        try:
            while True:
                if i+1==len(list1) and list1[i]<list2[pos]:
                    final.append((list1[i],list2[pos]))
                    raise Exception
                if list1[i]<list2[pos] and list1[i+1]>list2[pos]:
                    final.append((list1[i],list2[pos]))
                    raise Exception
                pos+=1
        except: pass
    return final