ADN revisité

Mon algorithme est assez simple, genre "pendu": on commence par des cases vides, _ _ _, puis pour chaque fragment on l'insert (et ce fragment à l'envers) à partir des positions où il rentre. Par exemple, si les fragments sont AC et AB, on commencerait par

1
2
3
4

A C _
_ A C
C A _
_ C A

Puis, pour chacun on retente avec AB, ce qui nous donne

A C _ -> rien

_ A C -> B A C

C A _ -> C A B

_ C A -> rien

En gros, je fais un depth-first search. Je l'ai optimisé de la façon suivante: on utilise toujours le même buffer _ _ _ qu'on remplit et qu'on vide progressivement. De plus, j'ai une fonction de hash qui permet de représenter de façon efficace chaque état, et je conserve les états que j'ai déjà visité, donc je ne fait pas plusieurs fois le même travail.

Et pourtant, mon algorithme n'est pas assez rapide. Comment l'améliorer?

C'est aussi l'approche que j'aurais prise Comment tu fais quand tu as inséré tous les fragments ? Imaginons que tu dois inserer juste (AC). Une fois que tu as tes 4 possibilités d'insertion, comment tu comptes combien tu en as sans repetitions ? Parce que tu peux faire _ A C puis inserer C Ou bien C A _ puis inserer C Comment tu fais pour ne pas compter ces deux cas ? Sinon je ne sais pas ce que tu hash et stock exactement, je pense que la bonne approche c'est de stocker tous tes buffers une fois que tu as calculé le nombre de possibilités, genre stocker que _ A C ça fait 4 possibilités

Pour continuer d'optimiser tu pourrais chercher les symetries dans ta table de hashage, ou calculer le nombre de possibilités pour chaque longueur dans l'ordre croissant et te servir des resultats precedents. Genre si tu sais que si il te reste que le brin AB dans une sequence de longueur 4, tu as 16 possibilités.

Mais là encore j'ai peur de te dire des betises: si ça se trouve ça comptera des cas en double. Une autre idée que je lance comme ça: trie tes segments par longueur avant ?

En gros, ma fonction de hash est la suivante: j'ai un mot de longueur n dont les lettres appartiennent à un alphabet de quatre lettres (A C G T), donc chacun de ces mots peut-être vu comme la représentation en base 4 d'un nombre. Il s'agit bien d'une bijection, donc je suis sûr de bien compter exactement une fois tous les mots, et c'est moins gourmand que de conserver les mots en entier (en fait dire "fonction de hash" est un peu un abus, parce que dans un vrai HashSet, on est obligé de conserver aussi l'objet qu'on insert, pour vérifier en cas de collision de hash, donc en fait ce que je fais vraiment c'est sauvegarder dans un HashSet le nombre qui correspond au mot), surtout que je ré-utilise leur emplacement mémoire pour les futurs mots, donc si je voulais les sauvegarder il faudrait en faire une copie, ce ne serait pas très efficace.

De plus, j'ai pensé à faire ça plus efficacement, c'est-à-dire une fois que j'ai consommé tous les fragments et qu'il me reste des emplacements, ne pas générer tous les mots que cela pourrait donner mais, à la place, simplement les dénombrer, et changer la façon dont on transforme les buffurs en nomres: au lieu de compter en base 4, je compte en base 5 en rajoutant _ à l'aphabet. Le problème de cette "amélioration" est que je peux compter plusieurs fois le même mot. Exemple:

j'ai les fragments AC et A, et n=3. Un des mots potentiels que j'ai généré c'est A C _ (en insérant le deuxième fragment en superposition du premier). Je le compte comme 4 mots, et le sauvegarde. Je génère ensuite un autre mot potentiel: A C A (cette fois, j'ai inséré le deuxième fragment à la fin). Je le compte comme 1 mot, et le sauvegarde: il n'entre pas en collision avec A C _, alors qu'il devrait! Donc je suis bien obligé, quand j'arrive au mot A C _ de générer les A C A, A C C, A C G et A C T, de les compter et sauvegarder individuellement. Comme ça, quand j'arriverais par un autre chemin à A C A, je saurais que je l'ai déjà compté.

Par contre je ne vois pas vraiment l'amélioration potentielle de trier les segments (ou même d'exploiter les symétries). Au final, en admettant que l'on réussisse efficacement à garantir que l'on compte bien exactement une seule fois tous les mots, on n'aura que divisé par 2,3,4,... le temps d'execution, mais sa complexité restera la même, et comme mon algo plante parmis les premiers tests, je pense qu'il y a un truc plus fort que juste de l'optimisation brutale de la constante.