Une solution plus efficace pour l'imbrication des boucles est requise

Question

J'essaie de comparer deux fichiers. Je vais énumérer le contenu des deux fichiers :

 File 1                           File 2

"d.complex.1"                     "d.complex.1"

  1                                 4
  5                                 5
  48                                47
  65                                21

d.complex.10                    d.complex.10

  46                                5
  21                                46
 109                               121
 192                               192

Il y a totalement 2000 d.complexes dans chaque fichier. J'essaie de comparer les deux fichiers mais le problème est que les valeurs listées sous d.complex.1 dans le premier fichier doivent être vérifiées avec les 2000 entrées d.complex dans le second fichier et si les entrées ne correspondent pas, elles doivent être imprimées. Par exemple, dans les fichiers ci-dessus, le numéro 48 du fichier 1 d.complex.1 n'est pas présent dans le fichier 2 d.complex.1 ; ce numéro doit donc être stocké dans une liste (pour être imprimé plus tard). Ensuite, le même d.complex.1 doit être comparé au d.complex.10 du fichier2 et comme 1, 48 et 65 ne sont pas présents, ils doivent être ajoutés à une liste.

La méthode que j'ai choisie pour y parvenir est d'utiliser des ensembles puis de faire une intersection. Le code que j'ai écrit est le suivant :

first_complex=open( "file1.txt", "r" )
first_complex_lines=first_complex.readlines()
first_complex_lines=map( string.strip, first_complex_lines )
first_complex.close()

second_complex=open( "file2.txt", "r" )
second_complex_lines=second_complex.readlines()
second_complex_lines=map( string.strip, second_complex_lines )
second_complex.close()

list_1=[]
list_2=[]

res_1=[]
for line in first_complex_lines:
    if line.startswith( "d.complex" ):
        res_1.append( [] )
    res_1[-1].append( line )

res_2=[]
for line in second_complex_lines:
    if line.startswith( "d.complex" ):
        res_2.append( [] )
    res_2[-1].append( line )
h=len( res_1 )
k=len( res_2 )
for i in res_1:
   for j in res_2:
       print i[0]
       print j[0]
       target_set=set ( i )
       target_set_1=set( j )
       for s in target_set:
           if s not in target_set_1:
               print s

Le code ci-dessus donne un résultat comme celui-ci (juste un exemple) :

1
48
65
d.complex.1.dssp
d.complex.1.dssp

46
21

109 d.complexe.1.dssp d.complex.1.dssp d.complex.10.dssp

Bien que la réponse ci-dessus soit correcte, je veux un moyen plus efficace de le faire, quelqu'un peut-il m'aider ? De plus, deux d.complex.1.dssp sont imprimés au lieu d'un, ce qui n'est pas bon non plus.

Ce que j'aimerais avoir, c'est :

d.complex.1
d.complex.1 (name from file2)
   1
   48
   65

d.complex.1
d.complex.10 (name from file2)
   1
   48
   65

Je suis très novice en matière de python et mon concept ci-dessus est peut-être imparfait. De plus, je n'ai jamais utilisé d'ensembles auparavant :(. Quelqu'un peut-il me donner un coup de main ?

Answer 1

Pointeurs :

• Utilisez des compréhensions de listes ou des expressions génératrices pour simplifier le traitement des données. Plus facile à lire
• Il suffit de générer les ensembles une fois.
• Utilisez des fonctions pour ne pas vous répéter, notamment en effectuant deux fois la même tâche.

J'ai fait quelques hypothèses sur vos données d'entrée, vous pourriez essayer quelque chose comme ceci.

def parsefile(filename):
  ret = {}
  cur = None
  for line in ( x.strip() for x in open(filename,'r')):
    if line.startswith('d.complex'):
      cur = set()
      ret[line] = cur
    if not cur or not line.isdigit():
      continue
    cur.add(int(line))
  return ret

def compareStructures(first,second):
  # Iterate through key,value pairs in first
  for firstcmplx, firstmembers in first.iteritems():
    # Iterate through key,value pairs in second
    for secondcmplx, secondmembers in second.iteritems():
      notinsecond = firstmembers- secondmembers
      if notinsecond:
        # There are items in first that aren't in second
        print firstcmplx
        print secondcmplx
        print "\n".join([ str(x) for x in notinsecond])

first = parsefile("myFirstFile.txt")
second = parsefile("mySecondFile.txt")

compareStructures(first,second)

Modifié pour les corrections cela montre à quel point je compte sur l'exécution du code pour le tester :) Merci Alex

Answer 2

Il y a déjà une bonne réponse, par @MattH, qui se concentre sur les détails Python de votre problème, et bien qu'il puisse être amélioré dans plusieurs détails, les améliorations ne vous feraient gagner que quelques points de pourcentage en efficacité -- intéressant mais pas génial.

Le seul espoir pour un énorme L'augmentation de l'efficacité (par opposition à l'amélioration incrémentale "kai-zen") est un changement radical de l'algorithme - qui peut ou non être possible en fonction des caractéristiques de vos données que vous ne révélez pas, et de certains détails concernant vos exigences précises.

La partie cruciale est la suivante : en gros, quelle gamme de numéros sera présente dans le fichier, et en gros, combien de numéros par strophe "d.complex.N" ? Vous nous avez déjà dit qu'il y aura environ 2000 strophes par fichier (et c'est aussi crucial bien sûr) et l'impression est que dans chaque fichier elles seront classées par N croissant contigu -- 1, 2, 3, et ainsi de suite (est-ce bien le cas ?).

Votre algorithme construit deux cartes stanza->numbers (pas avec une efficacité maximale, mais c'est ce que la réponse de @MattH se concentre sur l'amélioration), il a donc inévitablement besoin de N squared vérifications d'une strophe à l'autre - comme N est 2 000, il faut 4 millions de vérifications de ce type.

Envisagez de construire inversé cartes, nombre->stanzas -- si la gamme de nombres et la taille typique d'une strophe (quantité de nombres dans) sont toutes deux raisonnablement limitées, elles seront plus compactes. Par exemple, si les nombres sont compris entre 1 et 200, et qu'il y a environ 4 nombres par strophe, cela implique qu'un nombre sera typiquement en (2000 * 4) / 200 -> 40 strophes, de sorte que de telles correspondances auraient 200 entrées d'environ 40 strophes chacune. Il ne faut que 200 contrôles au carré (40 000), au lieu de 4 millions, pour obtenir les informations conjointes pour chaque numéro (ensuite, selon le besoin exact du format de sortie, le formatage de ces informations peut nécessiter à nouveau un effort très important -- si vous avez absolument besoin comme résultat final de 4 millions de sections "paires de strophes" en sortie, alors bien sûr il n'y a aucun moyen d'éviter 4 millions d'"opérations de sortie", qui seront inévitablement très coûteuses).

Mais tout cela dépend de ces chiffres que vous ne nous dites pas -- la population moyenne des stanza, et la gamme des nombres dans les fichiers, ainsi que les détails sur les contraintes que vous devez absolument respecter pour le format de sortie (si les chiffres sont raisonnables, les contraintes du format de sortie vont être la contrainte clé sur la performance big-O que vous pouvez obtenir de cualquier ).

N'oubliez pas, pour citer Fred Brooks :

Montrez-moi vos organigrammes et cachez vos tableaux, et je continuerai à à être mystifié. Montrez-moi vos tableaux, et je n'aurai généralement pas besoin de vos organigrammes ; ils seront évidents.

Brooks écrivait dans les années 60 (bien que son recueil d'essais, "The Mythical Man-Month", ait été publié plus tard, dans les années 70), d'où l'utilisation pittoresque d'"organigrammes" (là où nous dirions code ou algorithmes) et de "tableaux" (là où nous dirions données ou structures de données) -- mais le concept général reste parfaitement valable : l'organisation et la nature de vos données, dans toutes sortes de programmes axés sur le traitement des données (comme le vôtre), peut être encore plus importante que l'organisation du code, d'autant plus qu'elle contraint ce dernier;-).