J'essaie de déterminer comment implémenter efficacement un générateur sur un itérable qui donne toutes les paires d'anticipation ou de réflexion dans une fenêtre définie.
Par exemple
> [(0, 1, 2, 3), (1, 2, 3, 4), (2, 3, 4, 5), (3, 4, 5, 6), (4, 5, 6, 7), (5, 6, 7, 8), (6, 7, 8,9), (7, 8, 9, None), (8, 9, None, None), (9, None, None, None)]
Devrait produire quelque chose de similaire à
def lookforward(seq, behind, forward, empty=None):
itr = iter(seq)
lst = [empty]*behind + [next(itr)]
# Prime the needed lookforward values:
for x in range(forward):
try:
lst.append(next(itr))
except StopIteration:
lst.append(empty)
forward -= 1
# Yield the current tuple, then shift the list and generate a new item:
for item in itr:
yield tuple(lst)
lst = lst[1:] + [item]
# Yield the last full tuple, then continue with None for each lookforward
# position:
for x in range(forward + 1):
yield tuple(lst)
lst = lst[1:] + [empty]
print(list(lookforward(range(10), 0, 3)))
Lorsqu'un élément n'existe pas lors de la recherche anticipée ou look-behind, il doit être rempli avec une valeur vide définie.
Voici ce que j'ai jusqu'à présent pour un générateur de lookahead
[((1, 2), (1, 3), (1, 4)), ((2, 3), (2, 4), (2, 5)), ...]
L'exécution de l'implémentation ci-dessus donne:
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] pairs_lookahead(seq, behind=0, forward=3, empty=None)
4 Réponses :
Vous pouvez essayer quelque chose comme le code suivant que j'ai écrit:
Explication:
Si derrière / forward code > vaut 0, nous définissons la variable behind_counter / forward_counter sur 1 pour que les boucles suivantes soient au moins une fois en boucle.
Boucles de boucle externe sur la plage de seq , les deux boucles internes sur la plage de behind_counter (décompté) et forward_counter (compté), respectivement. À l'intérieur de la boucle la plus interne, nous définissons les indices lookahead / -behind respectifs, puis vérifions à l'aide des trois instructions if si les indices sont hors limite afin de définir les valeurs respectives sur la valeur hors limite ( 'null' ) si nécessaire. La quatrième instruction if est choisie si les indices ne sont pas hors limites. Dans chaque instruction if , il y a des instructions if-elif-elif-else qui modifient le tuple ajouté en fonction des valeurs lookahead / -behind stockées dans behind code > et avant . Si les deux sont à 0, ajoutez uniquement seq [i] , si derrière est à 0, ajoutez uniquement un tuple composé de seq [i] et de la valeur de recherche actuelle , et ainsi de suite.
Une fois le travail terminé, nous imprimons la valeur de res afin de visualiser le résultat.
Code source:
[((1, 'null'), (1, 'null'), (1, 2), (1, 3), (1, 4)), ((2, 'null'), (2, 1), (2, 3), (2, 4), (2, 5)), ((3, 1), (3, 2), (3, 4), (3, 5), (3, 6)), ((4, 2), (4, 3), (4, 5), (4, 6), (4, 7)), ((5, 3), (5, 4), (5, 6), (5, 7), (5, 8)), ((6, 4), (6, 5), (6, 7), (6, 8), (6, 9)), ((7, 5), (7, 6), (7, 8), (7, 9), (7, 10)), ((8, 6), (8, 7), (8, 9), (8, 10), (8, 'null')), ((9, 7), (9, 8), (9, 10), (9, 'null'), (9, 'null')), ((10, 8), (10, 9), (10, 'null'), (10, 'null'), (10, 'null'))]
Selon un nouveau commentaire, vous voulez une sortie différente lorsque les deux lookbehind / -forward sont spécifiés, j'ai donc modifié mon programme pour maintenant, espérons-le, répondre à vos besoins: Explication supplémentaire pour le programme mis à jour: Dans chaque itération de la boucle externe, les paires de recherche sont d'abord ajoutées dans une boucle, puis les paires de recherche sont ajoutées, également dans une boucle. Comme auparavant, nous vérifions les hors limites et définissons la valeur de la valeur lookbehind / forward en conséquence. Code source mis à jour: Nouveau résultat: [quand chercher et lookbehind sont spécifiés] Au cas où vous voudriez une liste contenant des tuples de tuples comme résultat vous pouvez faire quelque chose comme ceci [J'ai légèrement modifié le code de ma première mise à jour majeure]: Explication supplémentaire: Au début de chaque boucle externe itération, nous ajoutons une liste vide à Sortie: [ liste contenant des tuples de tuples em>] seq = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
behind = 2
forward = 3
res = []
behind_counter = behind
forward_counter = forward
if behind == 0:
behind_counter = 1
if forward == 0:
forward_counter = 1
for i in range(len(seq)):
res.append(list())
for j in range(behind_counter,0,-1):
index_behind = i - j
if behind == 0:
#res.append(tuple((seq[i])))
continue
else:
if index_behind < 0:
index_behind = 'null'
res[i].append((seq[i],index_behind))
continue
else:
res[i].append((seq[i], seq[index_behind]))
for k in range(forward_counter):
index_forward = i + k + 1
if forward == 0:
#res.append(tuple((seq[i])))
continue
else:
if index_forward >= len(seq):
index_forward = 'null'
res[i].append((seq[i],index_forward))
continue
else:
res[i].append((seq[i],seq[index_forward]))
res[i] = tuple(res[i])
print (res)
Première mise à jour majeure:
[(1, 'null'), (1, 'null'), (1, 2), (1, 3), (1, 4), (2, 'null'), (2, 1), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (4, 2), (4, 3), (4, 5), (4, 6), (4, 7), (5, 3), (5, 4), (5, 6), (5, 7), (5, 8), (6, 4), (6, 5), (6, 7), (6, 8), (6, 9), (7, 5), (7, 6), (7, 8), (7, 9), (7, 10), (8, 6), (8, 7), (8, 9), (8, 10), (8, 'null'), (9, 7), (9, 8), (9, 10), (9, 'null'), (9, 'null'), (10, 8), (10, 9), (10, 'null'), (10, 'null'), (10, 'null')]
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
behind = 2
forward = 3
res = []
behind_counter = behind
forward_counter = forward
if behind == 0:
behind_counter = 1
if forward == 0:
forward_counter = 1
for i in range(len(seq)):
for j in range(behind_counter,0,-1):
index_behind = i - j
if behind == 0:
#res.append(tuple((seq[i])))
continue
else:
if index_behind < 0:
index_behind = 'null'
res.append(tuple((seq[i],index_behind)))
continue
else:
res.append(tuple((seq[i], seq[index_behind])))
for k in range(forward_counter):
index_forward = i + k + 1
if forward == 0:
#res.append(tuple((seq[i])))
continue
else:
if index_forward >= len(seq):
index_forward = 'null'
res.append(tuple((seq[i],index_forward)))
continue
else:
res.append(tuple((seq[i],seq[index_forward])))
print (res)
Deuxième mise à jour majeure:
res . À cette liste, nous ajoutons les valeurs correspondantes des paires à rechercher d'abord, puis des paires à rechercher. À la fin de chaque itération de boucle externe, nous convertissons ensuite cette liste nouvellement créée en un tuple. [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (4, 7), (5, 6), (5, 7), (5, 8), (6, 7), (6, 8), (6, 9), (7, 8), (7, 9), (7, 10), (8, 9), (8, 10), (8, 'null'), (9, 10), (9, 'null'), (9, 'null'), (10, 'null'), (10, 'null'), (10, 'null')]
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
behind = 0
forward = 3
res = []
behind_counter = behind
forward_counter = forward
if behind == 0:
behind_counter = 1
if forward == 0:
forward_counter = 1
for i in range(len(seq)):
for j in range(behind_counter,0,-1):
for k in range(forward_counter):
index_behind = i - j
index_forward = i + k + 1
if index_behind < 0 and index_forward > len(seq):
index_behind = 'null'
index_forward = 'null'
if behind == 0 and forward == 0:
res.append(tuple((seq[i])))
elif behind == 0:
res.append(tuple((seq[i],index_forward)))
elif forward == 0:
res.append(tuple((index_behind,seq[i])))
else:
res.append(tuple((index_behind,seq[i],index_forward)))
continue
if index_behind < 0:
index_behind = 'null'
if behind == 0 and forward == 0:
res.append(tuple((seq[i])))
elif behind == 0:
res.append(tuple((seq[i],seq[index_forward])))
elif forward == 0:
res.append(tuple((index_behind,seq[i])))
else:
res.append(tuple((index_behind,seq[i],seq[index_forward])))
continue
if index_forward >= len(seq):
index_forward = 'null'
if behind == 0 and forward == 0:
res.append(tuple((seq[i])))
elif behind == 0:
res.append(tuple((seq[i],index_forward)))
elif forward == 0:
res.append(tuple((seq[index_behind],seq[i])))
else:
res.append(tuple((seq[index_behind],seq[i],index_forward)))
continue
if index_forward < len(seq) and index_behind >= 0:
if behind == 0 and forward == 0:
res.append(tuple((seq[i])))
elif behind == 0:
res.append(tuple((seq[i],seq[index_forward])))
elif forward == 0:
res.append(tuple((seq[index_behind],seq[i])))
else:
res.append(tuple((seq[index_behind],seq[i],seq[index_forward])))
print (res)
Je pense que la meilleure solution est d'utiliser autant d'outils disponibles que possible. En particulier, quelque chose de très intéressant dans ce cas est d'utiliser zip (et son alterego zip_longest ):
[((1, 'Z'), (1, 'Z'), (1, 2)), ((2, 'Z'), (2, 1), (2, 3)), ((3, 1), (3, 2), (3, 4)), ((4, 2), (4, 3), (4, 'Z'))] [((1, 'Y'), (1, 'Y')), ((2, 'Y'), (2, 1)), ((3, 1), (3, 2)), ((4, 2), (4, 3))] [((1, 2),), ((2, 3),), ((3, 4),), ((4, 'X'),)]
Ce qui produit:
seq = [1, 2, 3, 4] result = pairs_lookahead(seq, behind=2, forward=1, empty="Z") print(list(result)) result = pairs_lookahead(seq, behind=2, forward=0, empty="Y") print(list(result)) result = pairs_lookahead(seq, behind=0, forward=1, empty="X") print(list(result))
Notez également que zip peut être utilisé pour "décompresser":
from itertools import zip_longest, islice
def fill_with(iterator, value, times):
"""Add `value` `times` times in front of the iterator."""
for _ in range(times):
yield value
yield from iterator
def pairs(seq, distance, reverse=False, empty=None):
"""Build lookup pairs from a list, for example:
list(pairs([1,2,3], 1)) => [(1, 2), (2, 3), (3, None)]
and reverse make backward lookups:
list(pairs([1,2,3], 1, reverse=True)) => [(1, None), (2, 1), (3, 2)]
"""
if reverse:
return zip(seq, fill_with(seq, empty, distance))
else:
return zip_longest(seq, islice(seq, distance, None), fillvalue=empty)
def look_backward(seq, distance, empty=None):
"""Build look backward tuples, for example calling
list(look_backward([1,2,3], 2)) will produce:
[((1, None), (1, None)), ((2, None), (2, 1)), ((3, 2), (3, 1))]
"""
return zip(*(pairs(seq, i, empty=empty, reverse=True) for i in range(distance,0, -1)))
def look_forward(seq, distance, empty=None):
"""Build look forward tuples, for example calling
list(look_forward([1,2,3], 2)) will produce:
[((1, 2), (1, 3)), ((2, 3), (2, None)), ((3, None), (3, None))]
"""
return zip(*(pairs(seq, i+1, empty=empty) for i in range(distance)))
def pairs_lookahead(seq, behind=0, forward=3, empty=None):
"""Produce the results expected by https://stackoverflow.com/q/54847423/1720199"""
backward_result = look_backward(seq, behind, empty=empty)
forward_result = look_forward(seq, forward, empty=empty)
if behind < 1 and forward > 0:
return forward_result
if behind > 0 and forward < 1:
return backward_result
return [a+b for a, b in zip(backward_result, forward_result)]
Sorties:
def pairs_generator():
for x in range(2):
yield zip_longest(seq, seq[x:])
pairs = pairs_generator()
La première étape est de comprendre ce morceau de code qui construit le cas forward = 2 :
[((1, 2), (1, 3)), ((2, 3), (2, 4)), ((3, 4), (3, None)), ((4, None), (4, None))]
Ceci imprime:
from itertools import zip_longest seq = [1, 2, 3, 4] pairs = [] for x in range(2): x_step_ahead = zip_longest(seq, seq[x:]) pairs.append(x_step_ahead) merged = zip(*pairs) print(list(merged))
C'est très proche d'être modulable, la seule chose que nous supposons ici est que nous n'avons que deux objets zip à fusionner, où dans le cas réel nous aurons un nombre inconnu, donc nous devons être capable de traduire merged = zip (one_step_ahead, two_steps_ahead) dans un cas où la liste a une taille inconnue. Pour ce faire, nous allons simplement ajouter tous les "x_steps_ahead" dans une liste, appelons-le paires , puis nous fusionnerons toutes ces paires en utilisant l'opération de propagation * paires . À la fin, cela ressemblera à ceci:
[((1, 2), (1, 3)), ((2, 3), (2, 4)), ((3, 4), (3, None)), ((4, None), (4, None))]
Ce qui produit le même résultat qu'auparavant:
from itertools import zip_longest seq = [1, 2, 3, 4] one_step_ahead = zip_longest(seq, seq[1:]) two_steps_ahead = zip_longest(seq, seq[2:]) # print(list(one_step_ahead)) # => [(1, 2), (2, 3), (3, 4), (4, None)] # print(list(two_steps_ahead)) # => [(1, 3), (2, 4), (3, None), (4, None)] merged = zip(one_step_ahead, two_steps_ahead) print(list(merged))
C'est fondamentalement le toute l'idée du code que je propose. Le cas de regarder en arrière est un peu plus inhabituel mais je vais vous laisser comprendre comment cela fonctionne comme un exercice. Une légère différence dans le code final est également que j'essaie d'éviter autant que possible d'instancier des listes. Les itérateurs / générateurs sont préférés, ce qui rend le code un peu plus difficile à lire, mais beaucoup plus efficace en termes d'utilisation de la mémoire.
En gros, des choses comme la construction de paires se transformeront en:
[(1, 2, 3), (2, 3, 4)]
Cela fait exactement la même chose que le code précédent, cela évite juste d'avoir une liste de taille x en mémoire pour se souvenir de tous les zips que nous créons.
Pour la même raison, dans le code suivant, j'utilise également itertools.islice au lieu du slicing classique car c'est une version plus légère (contrairement à slice , il n'instancie pas une copie de la liste d'entrée).
print(list(zip(*[(1, 2), (2, 3), (3, 4)])))
Vous pouvez l'appeler comme vous l'avez suggéré:
[(1, 2), (2, 3), (3, 4)] [(1, 2), (2, 3), (3, 4), (4, None)]
Ceci génère:
from itertools import zip_longest seq = [1, 2, 3, 4] print(list(zip(seq, seq[1:]))) print(list(zip_longest(seq, seq[1:])))
C'est exactement le genre de solution que je recherchais. J'apprécie également la profondeur avec laquelle vous avez expliqué votre raisonnement. Cependant, j'ai une question sur la façon dont je pourrais utiliser une telle implémentation pour des séquences d'objets: comment pourrais-je effectuer un traitement sur des objets individuels non vides pour produire une sorte de vue pour les objets de la séquence? Je m'excuse si cette question ajoute beaucoup plus de complexité au problème. Votre solution actuelle est plus que suffisante pour le problème d'origine.
Je ne suis pas sûr de bien comprendre ce que vous entendez ici. Vous voulez que seq soit une séquence de n'importe quel objet au lieu d'une séquence de nombres? Je ne comprends pas non plus ce que vous entendez par "vue des objets".
Je m'excuse de ne pas avoir expliqué très clairement ce que j'avais à l'esprit dans mon commentaire précédent. Ce que je me demandais, c'était en quoi une telle implémentation pourrait différer s'il était souhaitable d'effectuer des calculs sur des éléments de la séquence d'origine qui apparaîtraient dans les paires - qu'il s'agisse d'objets ou non. Un cas d'utilisation potentiel est celui où l'on souhaite construire des paires de données significatives calculées à partir d'objets plutôt que des objets eux-mêmes. Cela a-t-il plus de sens? Je soupçonne que imap ou map peut être utile pour cela, mais je ne connais pas leur utilisation.
Une étape intermédiaire utile pour résoudre votre problème consiste à produire des séquences de valeurs adjacentes. Donc, si l'entrée était [1, 2, 3, 4, 5, ...] , vous itéreriez et obtiendriez (1, 2, 3, 4) puis (2, 3, 4, 5) et ainsi de suite.
Il existe un moyen astucieux de le faire en utilisant itertools.tee:
def lookaround_with_empties(iterable, behind, ahead, empty=None):
padded_iterable = itertools.chain([empty]*behind, iterable, [empty]*ahead)
return lookaround(padded_iterable, behind, ahead)
Maintenant, nous pouvons assez facilement faire regarder et regarder derrière (j'ignore les valeurs vides pour le moment):
def lookaround(iterable, behind, ahead):
for values in n_wise(iterable, 1 + behind + ahead):
behind_values = values[:behind]
current_value = values[behind]
ahead_values = values[behind+1:]
for b in behind_values:
yield current_value, b
for a in ahead_values:
yield current_value, a
Le moyen le plus simple d'adapter cela pour prendre en charge les valeurs vides serait simplement de remplir l'itérable. Il vous faut derrière des valeurs vides supplémentaires au début et avant des valeurs supplémentaires à la fin.
import itertools
def n_wise(iterable, n):
iterators = itertools.tee(iterable, n)
for i, iterator in enumerate(iterators):
next(itertools.islice(iterator, i, i), None) # discard i values from the iterator
return zip(*iterators)
Maintenant, ceci se comporte un peu bizarrement quand il regarde en arrière ou en avant dans plusieurs valeurs vides d'affilée (car il répète la même sortie pour chaque valeur manquante), mais je ne suis pas sûr de ce que vous attendez dans ces situations. Il existe probablement un moyen simple de filtrer la sortie pour éviter les doublons, si vous le souhaitez.
Ajouter du vide à la fin est une bonne idée, cela évite de l'avoir partout et évite également de construire des trucs inutiles: p. Au fait, vous passez le paramètre vide à lookaround et vous avez également enumerate (it) au lieu de enumerate (iterators) . Les paires de recherche ne sont pas regroupées par tuple dans la sortie comme cela a été demandé.
Dans un premier temps, écrivez une fonction qui, à partir d'un index pivot , renvoie la liste des paires d'anticipation et d'anticipation centrées sur le pivot .
Utilisation listes de compréhensions :
def all_pairs(seq, behind=2, forward=3):
return (((seq[p], seq[p+i] if p+i < len(seq) and p+i >= 0 else None)
for i in range(-behind, forward+1) if i != 0) for p in range(len(seq)))
Oublions pour quelque temps l'efficience. Quel est le résultat de votre implémentation actuelle? Je ne l'ai pas exécuté moi-même mais je vois qu'il génère des tuples - alors pourquoi est-ce différent de "le modifier pour produire les séquences de paires"? S'il vous plaît, expliquez
J'ai mis à jour ma question pour avoir un exemple de sortie. Ce que je veux faire est de modifier cette implémentation pour générer des séquences de paires lookahead dans une fenêtre plutôt que simplement des tuples lookahead dans une fenêtre. Est-ce que cela clarifie les choses?
Je doute sérieusement que ce soit votre code de test. D'une part, la fonction est nommée
lookaheadet nonlookforward, et une autre est que lorsque cela est corrigé, `` lookahead, comme écrit, provoque unRuntimeError: le générateur a déclenché StopIteration`.@martineau Je viens de corriger quelques fautes de frappe avec l'implémentation ci-dessus. L'exécution du code sur mon système via le shell avec Python 3.6.7 donne la sortie correcte sans erreur.
Eh bien, c'est une amélioration, mais quand je l'exécute avec Python 3.7.2 (pas que je pense que la différence compte), j'obtiens toujours un
RuntimeError: générateur déclenché StopIteration. Êtes-vous sûr que le code que vous exécutez a cetteaugmenter StopIterationà la fin? Quelle est la ligne sur laquelle il se produit pour moi (et n'est pas nécessaire).Quelle devrait être la sortie lorsque les deux
behindetforwardsont spécifiés? Quelque chose comme[..., ((2, None), (2, 1), (2, 3), (2, 4), ...]s'ils sont tous deux égaux à 2 ?@martineau Je peux confirmer que mon code avait la ligne élevant le StopIteration; cependant, sa suppression ne semble pas affecter son comportement. Je supprimerai l'exception de la question initiale.
@cglacet Votre exemple semble correct pour ce que j'avais en tête. J'ajouterai un exemple d'un tel cas au problème initial pour les autres afin d'éviter toute confusion.