Comparaisons efficaces de listes de Tuple

Question

Je suis en train de frapper un mur sur ce problème et je me demandais si des cerveaux frais pouvaient m'aider.

J'ai une grande liste de quatre tuples d'éléments dans le format:

(numéro d'identification, type, index, index End)

Précédemment dans le code, je l'ai recherché par des milliers de blocs de texte pour deux types spécifiques de sous-chaînes. Ces tuples stockent dans quel grand morceau de texte la sous-chaîne a été trouvée, lequel des deux types de sous-chaînes elle est, et l'index de début et de fin de cette sous-chaîne.

L'objectif final est de parcourir cette liste pour trouver toutes les instances où une sous-chaîne de type 1 se produit avant une sous-chaîne de type 2 dans un bloc de texte avec le même ID. Ensuite, je voudrais stocker ces objets dans le format (ID, Type 1, Début, Fin, Type2, Début, Fin).

J'ai essayé de jouer avec un tas de choses qui étaient super inefficaces. J'ai la liste triée par ID puis Start Index, et si j'essayais de différentes façons de faire sortir les éléments de la liste pour des comparaisons. Je dois imaginer qu'il existe une solution plus élégante. Des gens brillants veulent aider mon cerveau fatigué ???

Merci à l'avance

Answer 1

Solution:

result = [(l1 + l2[1:]) 
      for l1 in list1 
      for l2 in list2 
      if (l1[0] == l2[0] and l1[3] < l2[2]) 
      ] 

... avec le code de test:

list1 = [(1, 'Type1', 20, 30,), 
     (2, 'Type1', 20, 30,), 
     (3, 'Type1', 20, 30,), 
     (4, 'Type1', 20, 30,), 
     (5, 'Type1', 20, 30,), 
     (6, 'Type1', 20, 30,), # does not have Type2 

     (8, 'Type1', 20, 30,), # multiple 
     (8, 'Type1', 25, 35,), # multiple 
     (8, 'Type1', 50, 55,), # multiple 
     ] 

list2 = [(1, 'Type2', 40, 50,), # after 
     (2, 'Type2', 10, 15,), # before 
     (3, 'Type2', 25, 28,), # inside 
     (4, 'Type2', 25, 35,), # inside-after 
     (4, 'Type2', 15, 25,), # inside-before 
     (7, 'Type2', 20, 30,), # does not have Type1 

     (8, 'Type2', 40, 50,), # multiple 
     (8, 'Type2', 60, 70,), # multiple 
     (8, 'Type2', 80, 90,), # multiple 
     ] 

result = [(l1 + l2[1:]) 
      for l1 in list1 
      for l2 in list2 
      if (l1[0] == l2[0] and l1[3] < l2[2]) 
      ] 

print '\n'.join(str(r) for r in result) 

On ne sait pas quel résultat voulez-vous s'il y a plus de une occurrence de Type1 et Type2 dans le même ID de texte. Veuillez préciser.

Answer 2

Je ne sais pas combien de types vous avez. Mais si nous supposons que vous n'avez que le type 1 et le type 2, cela ressemble à un problème similaire à un tri par fusion. En faisant cela avec un tri de fusion, vous faites un seul passage dans la liste. Prendre deux index, un pour le type 1 et un pour le type 2 (I1, I2). Triez la liste par id, start1. Démarrez I1 comme première instance de type1 et I2 comme zéro. Si I1.id < I2.Id puis incrémenter I1. Si I2.id < I1.id alors incrémenter I2. Si I1.id = I2.id alors vérifiez iStart. I12 ne peut s'arrêter que sur un enregistrement de type 1 et I2 ne peut s'arrêter que sur un enregistrement de type 2. Continuez à incrémenter l'index jusqu'à ce qu'il atterrisse sur un enregistrement approprié.

Vous pouvez faire quelques suppositions pour rendre ceci plus rapide. Lorsque vous trouvez un bloc qui réussit, vous pouvez déplacer I1 au bloc suivant. Chaque fois que I2 < I1, vous pouvez commencer I2 à I1 + 1 (WOOPS ASSUREZ-VOUS DE NE PAS FAIRE CECI, CAR VOUS MANQUERIEZ LE CAS DE PANNE!) Chaque fois que vous détectez un cas d'échec évident, déplacez I1 et I2 vers le bloc suivant (le cas échéant recs bien sûr).

Answer 3

J'ai récemment fait quelque chose comme ça. Je ne comprends peut-être pas votre problème mais ici va.

Je voudrais utiliser un dictionnaire:

from collections import defaultdict: 
masterdictType1=defaultDict(dict) 
masterdictType2=defaultdict(dict) 


for item in myList: 
    if item[1]=Type1 
     if item[0] not in masterdictType1: 
      masterdictType1[item[0]]['begin']=item[2] # start index 
      masterdictType1[item[0]]['end']=item[-1] # end index 
    if item[1]=Type2 
     if item[0] not in masterdictType2: 
      masterdictType2[item[0]]['begin']=item[2] # start index 
      masterdictType2[item[0]]['end']=item[-1] # end index 

joinedDict=defaultdict(dict) 

for id in masterdictType1: 
    if id in masterdictType2: 
     if masterdictType1[id]['begin']<masterdictType2[id]['begin']: 
      joinedDict[id]['Type1Begin']=masterdictType1[id]['begin'] 
      joinedDict[id]['Type1End']=masterdictType1[id]['end'] 
      joinedDict[id]['Type2Begin']=masterdictType2[id]['begin'] 
      joinedDict[id]['Type2End']=masterdictType2[id]['end'] 

Cela vous donne explicitation et vous donne quelque chose qui est durable, puisque vous pouvez décaper le dictionnaire facilement.

Answer 4

Si l'on suppose qu'il ya beaucoup d'entrées pour chaque ID, je voudrais (pseudo-code)

 
    for each ID: 
     for each type2 substring of that ID: 
      store it in an ordered list, sorted by start point 
     for each type1 substring of that ID: 
      calculate the end point (or whatever) 
      look it up in the ordered list 
      if there's anything to the right, you have a hit 

Donc, si vous avez le contrôle du tri initial, puis au lieu de (ID, début), vous voulez les triés par ID, puis par type (2 avant 1). Ensuite, dans le type, trier par point de départ pour type2, et le décalage que vous allez comparer pour type1. Je ne suis pas sûr si par "A avant B" vous voulez dire "A commence avant que B commence" ou "A se termine avant que B commence", mais faites ce qui est approprié.

Ensuite, vous pouvez effectuer toute l'opération en parcourant la liste une fois. Vous n'avez pas besoin de construire un index de type2s, car ils sont déjà en ordre. Comme les types1 sont également triés, vous pouvez effectuer chaque recherche avec une recherche linéaire ou binaire à partir du résultat de la recherche précédente. Utilisez une recherche linéaire s'il y a beaucoup de type1s par rapport à type2s (donc les résultats sont proches), et une recherche binaire s'il y a beaucoup de type2s par rapport à type1s (donc les résultats sont clairsemés). Ou restez simplement avec la recherche linéaire car c'est plus simple - cette recherche est la boucle interne, mais ses performances peuvent ne pas être critiques.

Si vous n'avez pas le contrôle du tri, alors je ne sais pas s'il est plus rapide de construire la liste des sous-chaînes de type2 pour chaque ID au fur et à mesure; ou pour trier la liste entière avant de commencer dans l'ordre requis; ou juste pour travailler avec ce que vous avez, en écrivant une "recherche" qui ignore les entrées de type1 lors de la recherche à travers les types2 (qui sont déjà triés selon les besoins). Testez-le, ou faites simplement tout ce qui résulte en un code plus clair. Même sans re-tri, vous pouvez toujours utiliser l'optimisation du style de fusion à moins que "trié par l'index de démarrage" ne soit pas la bonne chose pour le type1s.

Answer 5

ce que je pourrais vérifier, par avant, voulez-vous dire immédiatement avant (ie. t1_a, t2_b, t2_c, t2_d doit juste donner la paire (t1_a, t2_b), ou voulez-vous que toutes les paires où une valeur de type 1 se produit partout devant un type2 un dans le même bloc. (c.-à-(t1_a, t2_b), (t1_a, t2_c), (t1_a, t2_d) pour l'exemple précédent).

Dans les deux cas, vous devriez être en mesure de le faire avec une seule passe sur votre liste (en présumant triée par identifiant, puis l'indice de départ).

Voici une solution supposer ing la seconde option (chaque paire):

import itertools, operator 

def find_t1_t2(seq): 
    """Find every pair of type1, type2 values where the type1 occurs 
    before the type2 within a block with the same id. 

    Assumes sequence is ordered by id, then start location. 
    Generates a sequence of tuples of the type1,type2 entries. 
    """ 
    for group, items in itertools.groupby(seq, operator.itemgetter(0)): 
     type1s=[] 
     for item in items: 
      if item[1] == TYPE1: 
       type1s.append(item) 
      elif item[1] == TYPE2: 
       for t1 in type1s: 
        yield t1 + item[1:] 

Si c'est juste immédiatement avant, il est encore plus simple: il suffit de garder une trace de l'élément précédent et donner le tuple chaque fois qu'il est type1 et l'actuel est type2.

Voici un exemple d'utilisation, et les résultats retournés:

l=[[1, TYPE1, 10, 15], 
    [1, TYPE2, 20, 25], # match with first 
    [1, TYPE2, 30, 35], # match with first (2 total matches) 

    [2, TYPE2, 10, 15], # No match 
    [2, TYPE1, 20, 25], 
    [2, TYPE1, 30, 35], 
    [2, TYPE2, 40, 45], # Match with previous 2 type1s. 
    [2, TYPE1, 50, 55], 
    [2, TYPE2, 60, 65], # Match with 3 previous type1 entries (5 total) 
    ] 

for x in find_t1_t2(l): 
    print x 

Ce retour:

[1, 'type1', 10, 15, 'type2', 20, 25] 
[1, 'type1', 10, 15, 'type2', 30, 35] 
[2, 'type1', 20, 25, 'type2', 40, 45] 
[2, 'type1', 30, 35, 'type2', 40, 45] 
[2, 'type1', 20, 25, 'type2', 60, 65] 
[2, 'type1', 30, 35, 'type2', 60, 65] 
[2, 'type1', 50, 55, 'type2', 60, 65]