Je fais un stagiaire écrit un programme pour faire correspondre des gènes.
Par exemple: Le fichier "A" contient des chaînes de type génique. (Les données d'origine n'est pas triée) rs17760268 rs10439884 rs4911642 Rs157640 RS1958589 RS10886159 RS424232 .... p>
et fichier "B" contient 900 milliers de chiffres de RS comme ci-dessus (non pas triés) p>
Mon programme peut maintenant obtenir des résultats corrects, mais je voudrais faire il est plus efficace. P>
Y a-t-il un algorithme qui peut être appliqué à ce programme? P>
BTW, je vais essayer de rendre mon programme multi-traitement et de voir s'il obtient une meilleure performance. P>
pseudocode:
read File "A" by string, append to A[]
A[] = rs numbers from File "A"
read File "B" by string
for gene_B in file_B_reader:
for gene_A in A:
if gene_A == gene_B:
#append to result[]
3 Réponses :
Dans la description, il apparaît que vous souhaitez Votre algorithme est résultat [] pour contenir rs cordes qui sont dans les deux a et b (aka Intersection ).
o (n * m) , mais vous pouvez facilement l'améliorer en triant les deux fichiers ( O (n * logn) pour les sortes de comparaison) , puis lisez à la fois en même temps, augmentant la position d'une position dans une personne qui a un numéro de courant inférieur RS et d'ajouter des correspondances à résultat [] en même temps.
Vous voulez probablement dire o (nm)?
Bien que vos explications ne soient pas claires, je suppose que vous aimez les valeurs d'une liste. Utilisez un dictionnaire à la place et vous pouvez rechercher beaucoup plus efficacement.
Je ne pense pas qu'il y ait un besoin de trier tout d'abord.
Total: O (N + M)
Et si ni la liste ne convient à la mémoire?
Bonne question. L'OP aurait besoin de résoudre un problème légèrement différent. En supposant que le codage des caractères de 2 octets et 11 caractères pour chaque "gène", puis je pense que l'espace requis pour le stockage est de 2 * 11 * 1e6 (heurté jusqu'à 1 million de gènes) = 2.2E7B ou 22 Mo. Je pense qu'il est prudent de supposer que la plupart des appareils auront suffisamment de mémoire disponible. Si OP a des restrictions, ils devraient mentionner cela dans leur demande.
Dictionnaire serait-il meilleur que HASHMAP dans ce cas?
Je crois que le dictionnaire est le terme générique. HashMap / Set est généralement une implémentation. Python Dictionnaires, cartes, HASHMAP, ... tous semblent se référer à une structure similaire.
Qu'est-ce que vous appuyez exactement pour résulter? le gène qui était commun dans les deux fichiers?
Tout ce qui a été posté est une description de programme. Cependant, nous avons besoin de vous pour poser une question . Nous ne pouvons pas être sûrs de ce que vous voulez de nous. S'il vous plaît Modifier Votre message pour inclure une question valide que nous pouvons répondre. Rappel: assurez-vous de savoir Qu'est-ce qui est sur le sujet ici ; Nous nous demandons d'écrire le programme pour vous, des suggestions et des liens externes sont hors succes.
Veuillez lire Comment poser des questions sans aucun exemples reproductibles Nous ne pouvons pas faire beaucoup pour vous.
Fichiers de lecture et d'écriture et Ensemble ou FROZENSETS devrait vous aider à faire votre pseudocode dans un Exemple reproductible minimal