Représentation d'un fragment d'ADN (String ou StringBuffer ?)

Résolu/Fermé
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019 - Modifié par KX le 23/10/2016 à 14:59
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019 - 23 oct. 2016 à 16:50
Bonjour tout le monde,

Je travaille sur un projet qui consiste à aligner correctement (selon l'alignement semi-global) deux fragments d'ADN (dans mon fichier, j'ai 130 fragments à comparer).

Dans mon projet, je considère un fragment d'ADN comme un string (il a en moyenne une taille de 500)..

En gros dans mon programme, je vais parcourir ces fragments et y insérer (si les conditions sont satisfaites) des "-" (gaps)..
Je manipule donc l'objet String en comparant les caractères à une position donnée des deux fragments, puis j'insère des "-".

Le truc c'est que je dois faire ça un bon nombre de fois :

- je compare le fragment 1 avec le 2, 3, 4, ..., 131
- je compare le fragment 2 avec le 3, 4, 5, ..., 131
.... et ainsi de suite pour arriver au dernier ...
- je compare le fragment 130 avec le 131

Je me suis donc renseigné sur la classe qui permet d'avoir des performances rapides pour ces manipulations et sur internet on dit bien que les StringBuffer sont beaucoup plus rapides que les String.. Or, dans mes résultats je n'obtiens pas cela du tout

Je fais les comparaisons de tous les fragments en 53 secondes avec des Strings et en 141 secondes avec des StringsBuffer..

Quel est votre avis à vous ? String ou StringBuffer ? Je met également le code pour que vous voyez comment j'utilise le StringBuffer :

for(int i = 0; i < f1.substring(ligne).length(); i++) {
   f2.append("_");
  } 
  
while(colonne > 0 && ligne > 0) {
   if(m[ligne][colonne] == m[ligne - 1][colonne - 1] + match(f1.charAt(ligne - 1), f2.charAt(colonne - 1))) { 
    score += match(f1.charAt(ligne - 1), f2.charAt(colonne - 1));
    ligne--;
   } else if(m[ligne][colonne] == m[ligne][colonne - 1] + GAP) { 
    f1.insert(ligne, "-");
    score += GAP;
   } else if(m[ligne][colonne] == m[ligne - 1][colonne] + GAP) { 
    f2.insert(colonne, "-");
    score += GAP;
    ligne--;
    colonne++;
   }
   
   colonne--;
  }
   
  if(ligne == 0 && colonne != 0) {
   for(int i = 0; i < colonne; i++) {
    f1.insert(0, "_");
   }
  }
  
  if(colonne == 0 && ligne != 0) { 
   for(int i = 0; i < ligne; i++) {
    f2.insert(0, "_");
   }
  } 
 


(Où f1 et f2 sont deux variables globales déclarées en StringBuffer)

Merci pour vos réponses,

Mikis

4 réponses

KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
22 oct. 2016 à 17:50
Bonjour,

La différence :

String est immuable, une fois que tu lui as donné une valeur tu ne peux plus le modifier, car le tableau de caractères utilisé en interne est de taille fixe, égal à la taille du String. Pour ajouter des caractères Java est obligé de créer un nouveau tableau de taille égale au nouveau String résultat, copier le contenu du String précédent ainsi que le contenu du String ajouté.

StringBuffer repose aussi sur un tableau de caractères mais avec une capacité dynamique, ce qui signifie que si ton StringBuffer a une taille de 5 caractères avec une capacité de 10 caractères, tu peux lui ajouter jusqu'à 5 caractères sans problème, en revanche au delà, le tableau devra être redimensionné on se retrouve donc avec le même problème de recopie des caractères, mais cela arrive moins souvent, surtout si tu sais à peu près combien de caractères va contenir le StringBuffer final, dans ce cas on peut le préciser dans le constructeur afin d'avoir tout de suite un tableau de caractères suffisamment grand pour ne jamais avoir à faire de recopie.

Il y a également StringBuilder, qui est encore plus rapide.
En effet StringBuffer est synchronisé, donc dans un contexte multithread il supportera des modifications concurrentes sans problème, mais au prix d'un mécanisme relativement lourd. StringBuilder n'ayant pas ce mécanisme il ne pourra être utilisé que dans un contexte monothread mais sera plus rapide.

Par contre, ce qui est rapide, c'est l'ajout à la fin (méthode append), mais toi tu fais des insert, c'est à dire que tu veux mettre les caractères au début, et pour faire ça on est obligé à chaque insertion de décaler tous les caractères dans le tableau, même s'il est suffisamment grand.

Le mieux pour toi serait d'une part d'utiliser un StringBuilder vu que tu n'es pas dans un contexte multithread, lui donner une taille initiale suffisante (tu parles de 500 caractères "en moyenne", est-ce que tu as la taille maximale ?) et t'assurer de toujours faire des append, pas des insert, quitte à faire un reverse() de ton résultat final pour avoir les caractères dans le bon ordre.

Remarque : f1.substring(ligne).length() c'est inutilement coûteux, tu construis un nouveau String (donc un nouveau tableau avec des recopies de caractères etc.) juste pour en connaître sa taille.
À +/- 1 près (à vérifier) cette valeur vaut f1.length() - ligne.length(), donc tu as directement le résultat par le calcul.
2
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
22 oct. 2016 à 18:10
Bonjour, déjà merci pour ta réponse !

Je connaissais un peu la différence entre les deux .. néanmoins je ne comprend toujours pas pourquoi j'ai des meilleurs résultats avec la classe String (c'est le même code mais au lieu des inserts ou append je fais f1 = f1 + "_")

Aussi je ne connais pas la taille maximum des fragments car il y a plusieurs fichiers et ca peut varier !

En ce qui concerne l utilisation du stringBuffer tu penses qu'en manipulant la chaîne de caractère à l envers et en faisant des append puis je fais un reverse, je serais plus rapide ?

Pour le stringbuilder, je ne peux pas l utiliser car dans la suite de mon programme je vais devoir utiliser la notion de multi-thread pour essayer d améliorer la performance du programme ..

Pour ta remarque, tu as totalement raison, je peux simplement faire un f1.length() - ligne pour avoir la taille ! Merci d'avoir remarqué..
0
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
22 oct. 2016 à 18:29
"je ne comprend toujours pas pourquoi j'ai des meilleurs résultats avec la classe String"
Parce que tu as les inconvénients du StringBuffer (il est synchronisé) sans en avoir les avantages (puisque tu n'utilises pas append) donc tu te retrouves dans le pire cas.

en manipulant la chaîne de caractère à l envers et en faisant des append puis je fais un reverse, je serais plus rapide ?
Oui, car il n'y a que des ajouts à la fin, donc pas de déplacements de caractères à chaque fois, la seule opération qui modifie tous les caractères c'est le reverse, mais pour autant il n'a pas besoin de créer de nouveaux tableau pour ça.

"je ne connais pas la taille maximum des fragments car il y a plusieurs fichiers et ca peut varier"
Ce n'est pas obligé d'être une constante, si je comprends bien ton code on devrait être plus ou moins sur quelque chose comme ligne*colonne, non ?

Même si tu ne sais pas quelle taille exacte fera le StringBuilder avoir un ordre de grandeur permettra de diminuer le nombre de redimensionnement.
La règle est la suivante : par défaut un StringBuilder a une capacité de 16 caractères à chaque fois que la capacité est dépassée on créé un nouveau tableau 2 fois plus grand (donc 32, 64, 128, 256, 512) soit 5 redimensionnements si tu atteints 500 caractères.
Alors que si tu estimes que en moyenne tu as 500 caractères, tu peux mettre 1000 au départ, ce qui couvrira la plupart des cas, et au pire ça redimensionnera une fois à 2000.
C'est toujours mieux que les 2000 redimensionnements que tu fais actuellement.

je vais devoir utiliser la notion de multi-thread pour essayer d améliorer la performance du programme
Ce n'est pas incompatible. Le problème c'est d'essayer de modifier un même StringBuilder par deux Thread différents. Mais si chaque thread a son propre StringBuilder dédié il n'y aura aucun problème.
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
22 oct. 2016 à 21:32
Je ne sais pas encore comment sera implémenté la partie multi thread.. je sais juste qu'il faudra utiliser cette notion pour être performant !

Tu pense donc que ca vaut le coup que je passe un peu de temps pour essayer le stringBuilder ?
Je vais essayer d optimiser en plaçant aux bons endroits les reverse() et faire des appends à la place !

Non pour ligne*colonne, le pire que je puisse avoir c'est ligne + colonne normalement ! Je vais faire le même code adapté pour le stringBuilder alors !
0
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
22 oct. 2016 à 21:41
Je ne connais pas ton problème exact, alors l'explication ci-dessous est à adapter.

Par exemple si (mais ce n'est peut-être pas ton cas) le résultat final est une concaténation des résultats pour chaque ligne, alors tu peux exécuter en parallèle (sur des threads différents) le calcul de chaque ligne pour obtenir les résultats partiels. Et à la fin utiliser chaque résultat intermédiaire obtenu pour reconstituer ton résultat final.

Bien qu'il y ait plusieurs threads en parallèle, il y aurait autant de StringBuilder que de threads, et surtout un seul thread qui écrirait dans le StringBuilder.

Le StringBuffer n'est utile que si au moins deux threads différents doivent écrire en même temps dedans. Cela évite d'avoir des mélanges du genre "1234"+"abcd"="ab12cd34" alors que l'on s'attendrait à avoir "1234abcd" ou "abcd1234"
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019 > KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024
22 oct. 2016 à 21:46
Pour être franc je ne sais pas comment va se passer le multi thread car je ne suis qu'au début de mon projet..
Je pense que je devrais plutôt utiliser deux threads sur un stringBuffer.

Le soucis que j avais (mais auquel tu as répondu) c'est que le programme est plus rapide avec les string += plutôt qu'avec les string buffer !

Du coup maintenant je vais adapter avec les reverses et les append en espérant que ca devienne beaucoup plus rapide... :)

Car en fait je dois traiter une assez grande quantité de donnée !
0
Utilisateur anonyme
22 oct. 2016 à 18:15
Si tu veux de la performance tu peux aussi passer par un langage plus bas niveau (C, C++)
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
22 oct. 2016 à 18:17
Malheureusement, java à été imposé par le professeur ! :(
0
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
22 oct. 2016 à 21:29
De toute façon la problématique reste la même dans n'importe quel langage, c'est avant tout une question de complexité algorithmique. Quand il y a plusieurs manière de faire, il y en a toujours une qui est meilleure que l'autre, peu importe le langage. Rien que sur le papier, la théorie montre que certains choix sont plus pertinent que d'autres.

Alors oui, pour deux algorithmes équivalents exécutés sur la même machine, celui en C ira plus vite que celui en Java. Mais pour autant, changer de langage, ou prendre une machine plus puissante, ne sera jamais une meilleure solution que choisir le bon algorithme à l'écriture du code.

Un programme mal écrit en C sera moins bon qu'un programme bien écrit en Java.
0
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
Modifié par KX le 22/10/2016 à 21:03
Ci-dessous un petit programme de test pour comparer les différentes méthodes de concaténation.

Dans le détail, je compte le temps qu'il faut pour ajouter 2000 caractères dans différents cas de figures. Et je recommence 1000 fois pour avoir une moyenne des temps calculé (plus précis qu'un seul lancé).

Comme indiqué ci-dessus avec les explications théoriques, les meilleurs temps sont ceux obtenus avec StringBuilder, sous réserve de l’initialiser à la bonne taille et d'utiliser append.
J'ai cependant ajouté un reverse à la fin, pour obtenir le même résultat que celui obtenu avec des insert, mais même avec ça c'est 3 ou 4 fois mieux.

Quant aux += de String ils sont très loin derrière, 25 fois plus lent.

import java.util.function.*;

public class Test {

    private static final int NB_CHARS = 2000, NB_LOOP = 1000;

    public static <E> void test(String s, Supplier<E> init,
BiFunction<E, Character, E> appender, Function<E, E> finish) {
        long time = 0;
        for (int retry = 0; retry < NB_LOOP; retry++) {
            E chars = init.get();
            time -= System.nanoTime();
            for (char c = 0; c < NB_CHARS; c++) {
                chars = appender.apply(chars, c);
            }
            chars = finish.apply(chars);
            time += System.nanoTime();
        }
        System.out.printf("%s\n\t%.0f µs\n", s, time * 1e-3 / NB_LOOP);
    }

    public static void main(String[] args) {
        test("String +=", () -> "", (s, c) -> s += c, s -> s);

        test("StringBuffer().insert",
() -> new StringBuffer(), (s, c) -> s.insert(0, c), s -> s);
        test("StringBuffer(size).insert",
() -> new StringBuffer(NB_CHARS), (s, c) -> s.insert(0, c), s -> s);
        test("StringBuffer().append+reverse",
() -> new StringBuffer(), (s, c) -> s.append(c), s -> s.reverse());
        test("StringBuffer(size).append+reverse",
() -> new StringBuffer(NB_CHARS), (s, c) -> s.append(c), s -> s.reverse());

        test("StringBuilder().insert",
() -> new StringBuilder(), (s, c) -> s.insert(0, c), s -> s);
        test("StringBuilder(size).insert",
() -> new StringBuilder(NB_CHARS), (s, c) -> s.insert(0, c), s -> s);
        test("StringBuilder.append+reverse",
() -> new StringBuilder(), (s, c) -> s.append(c), s -> s.reverse());
        test("StringBuilder(size).append+reverse",
() -> new StringBuilder(NB_CHARS), (s, c) -> s.append(c), s -> s.reverse());
    }
}

Exemple de résultats :

String +=
1149 µs
StringBuffer().insert
233 µs
StringBuffer(size).insert
224 µs
StringBuffer().append+reverse
86 µs
StringBuffer(size).append+reverse
78 µs
StringBuilder().insert
211 µs
StringBuilder(size).insert
192 µs
StringBuilder.append+reverse
47 µs
StringBuilder(size).append+reverse
44 µs
La confiance n'exclut pas le contrôle
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
22 oct. 2016 à 21:34
Je te remercie pour cette exemple ! Je vais essayer d adapter le code pour le stringBuilder mais sans être certain de l utiliser car après je vais devoir faire du multithreading..
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
22 oct. 2016 à 22:09
Euuuuh.. En vrai un fragment d adn est représenté par un string et comme j'ai plusieurs fragments j'utilise une list de string..
Pour représenter un fragment utiliser une liste de char reviendrai à utiliser un string non ?
0
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
22 oct. 2016 à 22:21
Si on revient à la structure interne de la classe String celle ci est peu souple avec son tableau de caractères. Alors qu'une liste permet plus de souplesse dans sa manipulation... et qu'il existe des listes spécialisées dans le traitement parallèle.
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
22 oct. 2016 à 22:40
Je suis tout ouïe .. peux tu m en dire plus ?
Crois tu que si j utilise une liste de caractère pour représenter un fragment constituer d une suite de A/T/G/C j'aurais de meilleures performances qu'avec un simple string ?
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
22 oct. 2016 à 22:41
(Un fragment d adn concrètement c'est ca : AAGCTCTAAG mais avec une taille de 500)
0
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
23 oct. 2016 à 01:24
Comme je l'ai dit plus haut, un String t'obliges, à chaque changement, de créer un nouveau String, ajout, suppression ou modification de caractère, nouveau String, tu fais 500 opérations sur les String, ça te fait 500 String différents. C'est un gouffre en terme de performances.

En revanche les collections sont conçues pour faire ce genre d'opérations, elles ont donc des algorithmes optimisés pour l'ajout, la suppression et/ou la modification, sans avoir à créer de nouveaux objets à chaque fois, donc gain de temps (et gain en mémoire aussi).

Remarque : on pourrait également remettre en cause l'utilisation des caractères pour représenter ton ADN, en terme de conception objet avoir une classe dédiée à la représentation de tes valeurs serait plus pertinent.
Là tu travailles avec des caractères car tu penses avec des String, mais si tu t'abstrais des String tu peux envisager d'autre type de données. Dans ton cas un type énuméré serait pertinent puisque les valeurs possibles sont figées.

Exemple :

import java.util.*;

public enum Nucleobase {
    ADENINE, CYTOSINE, GUANINE, THYMINE;

    public char toChar() {
        switch (this) {
        case ADENINE:
            return 'A';
        case CYTOSINE:
            return 'C';
        case GUANINE:
            return 'G';
        case THYMINE:
            return 'T';
        default:
            throw new EnumConstantNotPresentException(Nucleobase.class, name());
        }
    }

    @Override
    public String toString() {
        return String.valueOf(toChar());
    }

    public static void main(String[] args) {
        List<Nucleobase> adn = Arrays.asList(ADENINE, THYMINE, CYTOSINE, GUANINE);
        System.out.println(adn); // [A, T, C, G]
    }
}
0
mikis69 Messages postés 168 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 11 février 2019
23 oct. 2016 à 02:15
C'est une très bonne idée. Je n avais pas pensé à ce type d objet ! Pour moi, c'était un nucléotide = un char .. ici je me rend compte qu'en utilisant une énumération, on pourrait juste utiliser une liste de nucléotides pour représenter un fragment. Et plusieurs fragments seraient représenter par une liste de liste de nucléotides ..

Je te donnerai les résultats en terme de performance des demain !
0