none
Gérer une string trop longue : OutOfMemoryException RRS feed

  • Question

  • Bonjour,

     

    Voici mon problème, je dois générer une string de plus d'1 milliard de caractères.

    Pour cela j'ai une boucle qui se rapproche de la suite de Fibonacci : 

    string a ="A";
    string b = "B";
    
    while (a.Length < 1000000000)
    {
      string c = a;
      a = b;
      b = c + b;
    }
    
    

    Le soucis vient du fait qu'à partir du moment où la chaîne de caractère b dépasse une certaine longueur, le programme lève une exception OutOfMemoryException.

    J'ai pensé à utiliser un fichier texte et un buffer mais je n'arrive pas vraiment à implémenter cette solution. Y'a t-il une manière plus simple de le faire?

    dimanche 27 mars 2011 10:34

Réponses

  • > J'essaie de réalise cela pour épreuve de programmation d'un site de
    > challenges. Le but est de trouver le milliardième caractère de la chaîne et
    > de savoir combien il y a de A et de B.
    >
    > J'ai essayé de retourner le problème dans plusieurs sens mais là j'avoue
    > bloquer. Il y a apparemment un moyen de le faire sans utiliser plus d'1Go
    > de mémoire vive.
    >
    > Je vais essayer de creuser en cherchant une résolution mathématique mais je
    > doute qu'il y en ait un.
    >
    > Si quelqu'un a une autre idée pour faire tenir cette chaîne de caractères
    > elle reste la bienvenue.
     
    Challenge amusant. Je pense qu'il ne faut pas calculer explicitement la
    chaîne. Du moins pas jusqu'au bout.
     
    Pour ce qui est du nombre de "A" et de "B", la réponse est assez simple
    à trouver.
    On constate que pour la chaîne générée au niveau n, de longueur L(n), le
    nombre de "A" est L(n-2) et le nombre de "B" est L(n-1).
    Cela doit pouvoir se démontrer par récurrence (c'est vrai pour les 3
    premières B, AB et BAB.)
    Pour ce qui est du milliardième caractère. Partons du principe que les
    premiers caractères générés se retrouvent en bout de chaîne et que la
    longueur des chaînes est une suite de Fibonacci (si mes souvenirs sont
    bons 1, 2, 3 ,5, 8, 13 ...).
    Alors il est simple de calculer la longueur de la première chaîne qui
    dépasse 1M de caractères. De là on en déduit la longueur de la chaîne
    qui suit ce milliardième caractère. Cela nous donne la longueur de la
    chaîne qu'il faut effectivement conserver lors des itérations. Le
    milliardième caractère s'y trouve.
    Je pense qu'il y a sans doute mieux, mais c'est un premier examen rapide.
     --
    Fred
    foleide@free.fr
     
    lundi 28 mars 2011 12:01
  • Désolé pour ma réponse un peu tardive, je n'ai pu tester tout ça qu'il y a quelques heures.

    Effectivement la réponse de Foleide m'a mis sur la bonne voix. J'ai pu réussir l'épreuve de manière mathématique.  

    D'après les propriété de la suite de Fibonacci, le rapport des termes n et n+1 tend vers le nombre d'or.

     

    Il faut donc résoudre l'équation 

    n+1/n = (1+racine(5))/2

    n+n1 = 1000000000 

     

    Il y a également une autre méthode que je n'ai pas testé mais qui j'en suis certain marche. 

    C'est de passer par un fichier qui va contenir la chaine. 

    Lorsque l'on veut écrire la chaîne de caractères qui dépasse la capacité de mémoire, on passe par un buffer en se basant sur la précédente chaîne qui est dans le fichier. 

    Ensuite il suffit de relire caractère par caractère la chaine en comtant le nombre de A et B. 

    C'est grâce à cette méthode qu'on peut trouver le milliardième caractère. 

     

    Merci encore,

    Yohan

    • Marqué comme réponse Yohan D lundi 4 avril 2011 14:11
    lundi 4 avril 2011 14:10

Toutes les réponses

  • Bonjour,

    Ne serait il pas mieux d'utiliser un StringBuilder et sa méthode Append() pour construire votre chaine de caractère.

    Et comme cela vous manipuler qu'une seul instance.

    Voila une explication que l'on peut trouvé sur msdn :

    Une concaténation d'objet String crée toujours un nouvel objet à partir de la chaîne existante et des nouvelles données. Un objet StringBuilder gère une mémoire tampon qui contient la concaténation des nouvelles données. Les nouvelles données sont ajoutées à la fin de la mémoire tampon, si l'espace nécessaire est disponible ; sinon, une nouvelle mémoire tampon, plus grande, est allouée, les données de la mémoire tampon d'origine sont copiées dans la nouvelle mémoire tampon, et les nouvelles données sont ajoutées à la nouvelle mémoire tampon.


    Pascal.
    dimanche 27 mars 2011 11:22
  • J'ai essayé de cette manière : 

     

     

    
    
    string h ="A";
    string f = "B";
    
       
    StringBuilder sb = new StringBuilder();
    
    sb.Append(h);
    sb.Append(f);
    
    int i = 0;
    
    int a = 0;
    int b = 1;
    int c;
    
    while (sb.Length < 1000000000)
    {
     sb.Append(sb.ToString(), a, sb.Length - a);
     //Console.WriteLine(sb.ToString());
          
     c = a + b + 1;
     a = b; 
     b = c;
          
    }
    

     

    Mais apparemment l'objet StringBuilder est trop grand pour être stocké en mémoire.  Peut-être est-ce une limitation du 32-bits ? 

    Mon soucis vient également  du fait qu'ensuite je voudrais faire des opérations sur cette chaîne. Comme compter le nombre de A et B ou encore de savoir à quelle lettre correspond tel index.


    dimanche 27 mars 2011 12:29
  • Je pense que c'est normal tu essayes d'avoir 1 Milliard de caractères dans ta chaîne :

    Sachant qu'un caractère unicode prend une place de 2 octets.

    Cela fait environ 1,862 GO ce qui est énorme, sur ma machine une appli qui atteint un peu plus de 1 GO me lance une exception Out of Memory exception.

    Par contre je ne connais pas ton projet, quel est l'intérêt de stocker 1 milliard de caractères dans une chaine ?

    Et quel en est le but ?

    Il y a peut-être d'autres solutions.

    Par exemple tu peux stocker tes infos dans un fichier texte de cette façon :

    using (StreamWriter sw = new StreamWriter(@"C:\Users\Pascal\Documents\Mes fichiers reçus\text.txt"))//création du fichier 
          {
            for (int i = 0; i < 500000000; i++)
            {
              sw.Write("AB");//enregistrement du message dans le fichier 
            }
            sw.Close();
          }
    

    Attention sur ma machine cela tourne, mais j'ai un core I7 et 8GO de Ram.

    Et de plus après pour ouvrir ce fichier dan le bloc note il te faut 1 à 2 minutes ^^.

    Voila on pourra peut-être t'aider si on en sait un peu plus sur la finalité de ton code, car stocker 1 000 000 000 de caractères dans une chaine, je n'en vois pas trop l'intérêt pour le moment.


    Cordialement, Pascal.
    dimanche 27 mars 2011 14:57
  • J'essaie de réalise cela pour épreuve de programmation d'un site de challenges. Le but est de trouver le milliardième caractère de la chaîne et de savoir combien il y a de A et de B.

    J'ai essayé de retourner le problème dans plusieurs sens mais là j'avoue bloquer. Il y a apparemment un moyen de le faire sans utiliser plus d'1Go de mémoire vive.

    Je vais essayer de creuser en cherchant une résolution mathématique mais je doute qu'il y en ait un. 

     

    Si quelqu'un a une autre idée pour faire tenir cette chaîne de caractères elle reste la bienvenue. 

     


    Cordialement, Yohan

    dimanche 27 mars 2011 15:10
  • En tous cas je te souhaite bon courage car d'après ton problème je ne vois pas de solution.

    Mais bon si c'est un challenge, je te conseille de bien lire l'ennoncé.

    Car que cela soit un String de 1000 000 000 de caractères ou un tableau de caractères de 1 000 000 000 de caractères j'ai un Out Memory exception.

    Bon courage.


    Cordialement, Pascal.
    dimanche 27 mars 2011 15:39
  • > J'essaie de réalise cela pour épreuve de programmation d'un site de
    > challenges. Le but est de trouver le milliardième caractère de la chaîne et
    > de savoir combien il y a de A et de B.
    >
    > J'ai essayé de retourner le problème dans plusieurs sens mais là j'avoue
    > bloquer. Il y a apparemment un moyen de le faire sans utiliser plus d'1Go
    > de mémoire vive.
    >
    > Je vais essayer de creuser en cherchant une résolution mathématique mais je
    > doute qu'il y en ait un.
    >
    > Si quelqu'un a une autre idée pour faire tenir cette chaîne de caractères
    > elle reste la bienvenue.
     
    Challenge amusant. Je pense qu'il ne faut pas calculer explicitement la
    chaîne. Du moins pas jusqu'au bout.
     
    Pour ce qui est du nombre de "A" et de "B", la réponse est assez simple
    à trouver.
    On constate que pour la chaîne générée au niveau n, de longueur L(n), le
    nombre de "A" est L(n-2) et le nombre de "B" est L(n-1).
    Cela doit pouvoir se démontrer par récurrence (c'est vrai pour les 3
    premières B, AB et BAB.)
    Pour ce qui est du milliardième caractère. Partons du principe que les
    premiers caractères générés se retrouvent en bout de chaîne et que la
    longueur des chaînes est une suite de Fibonacci (si mes souvenirs sont
    bons 1, 2, 3 ,5, 8, 13 ...).
    Alors il est simple de calculer la longueur de la première chaîne qui
    dépasse 1M de caractères. De là on en déduit la longueur de la chaîne
    qui suit ce milliardième caractère. Cela nous donne la longueur de la
    chaîne qu'il faut effectivement conserver lors des itérations. Le
    milliardième caractère s'y trouve.
    Je pense qu'il y a sans doute mieux, mais c'est un premier examen rapide.
     --
    Fred
    foleide@free.fr
     
    lundi 28 mars 2011 12:01
  •       Bonjour,

     

    Foleide._  a raison. Il ne faut pas calculer explicitement la chaine. Au contraire, un simple calcul nous montre que le nombre des A et B dans les variables a et b peuvent être déterminés par la suite de Fibonnaci.

     

    Bonne journée,

     

    Cipri



    Ciprian DUDUIALA, MSFT  
    •Nous vous prions de considérer que dans le cadre de ce forum on n’offre pas de support technique et aucune garantie de la part de Microsoft ne peut être offerte.

    lundi 4 avril 2011 13:53
  • Désolé pour ma réponse un peu tardive, je n'ai pu tester tout ça qu'il y a quelques heures.

    Effectivement la réponse de Foleide m'a mis sur la bonne voix. J'ai pu réussir l'épreuve de manière mathématique.  

    D'après les propriété de la suite de Fibonacci, le rapport des termes n et n+1 tend vers le nombre d'or.

     

    Il faut donc résoudre l'équation 

    n+1/n = (1+racine(5))/2

    n+n1 = 1000000000 

     

    Il y a également une autre méthode que je n'ai pas testé mais qui j'en suis certain marche. 

    C'est de passer par un fichier qui va contenir la chaine. 

    Lorsque l'on veut écrire la chaîne de caractères qui dépasse la capacité de mémoire, on passe par un buffer en se basant sur la précédente chaîne qui est dans le fichier. 

    Ensuite il suffit de relire caractère par caractère la chaine en comtant le nombre de A et B. 

    C'est grâce à cette méthode qu'on peut trouver le milliardième caractère. 

     

    Merci encore,

    Yohan

    • Marqué comme réponse Yohan D lundi 4 avril 2011 14:11
    lundi 4 avril 2011 14:10