Discussion :

[marc92]

Bonjour à tous,
J'ai un fichier texte (segments.txt) qui contient des nombres triés par taille croissante.
La taille du fichier est supérieure à la mémoire RAM.
Je recherche les couples de nombres tel que : segment_2 (ligne j) / segment_1 (ligne i) = 2
J'ai le message d'erreur bad_alloc car mauvaise gestion de la mémoire.
Comment faire une allocation judicieuse de la RAM ?
Merci d'avance.
Mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
 
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
 
struct Data1 
{
         double seg_{};
};
 
// -------------------------------------------------------------------------
 
int main() 
{											
 
    std::ifstream file("segments.txt");
    if(!file) 
    {
          std::cerr << "file not found" << std::endl;
          return 1;
    }
 
    std::vector<Data1> datas1;
    Data1 data1;
 
    while(file >> data1.seg_)
    {
            datas1.push_back(data1);
    }
 
// ------------------------------------------------
 
int i,j;
double delta,precision;
 
precision = 0.0000001;
 
i = 0;
j = 1;
 
ici_1:   delta = (2*datas1[i].seg_) - datas1[j].seg_;
 
if ((delta >= 0 && delta <= precision) || (delta <= 0 && delta > -precision))
{											
           printf("%4.15f   %4.15f  \n",datas1[i].seg_,datas1[j].seg_);						
}											
 
if (delta > -precision)
{
         j = j + 1;
         if (j > datas1.size()) break;
         {
                     goto ici_2_init;
          }
          goto ici_1;
}
else
{
         i = i + 1;
         if (i > datas1.size()) break;
}
 
ici_2_init:       ;	 
 
 
}

[dalfab]

Bonjour,

"goto" est une erreur de syntaxe commise il y à 37 ans en rédigeant la norme C++. Et jamais personne ne l'utilisa...
Es-tu sûr que ton fichier ne tiens pas en mémoire, on devrait pouvoir charger 200 000 000 de double en mémoire?

Attention if ( j > datas1.size() ) n'est pas le bon test s'assurer que j est utilisable, il faut plutôt if ( j >= datas1.size() ).

[marc92]

Bonjour Dalfab,

Mon fichier comprends 160 millions de segments ... soit 19,5 GB !

Mon calcul fait un rapport entre 2 segments qui doit être égale à 2 (seg_j / seg_i = 2) mais les 2 segments se trouvent sur des lignes non contigus qui peuvent être très distantes.
Les segments soient trillés par taille croissante.

Merci.
Marc

[dalfab]

160 millions de doubles, ça fait 160 millions * 8 = 1,3GigaOctets
Et si tu les mettais dans des float, cela devrait suffire pour une comparaison "normale" et ferait 600M qui devrait passer. Mais une precision de 0.0000001 ne fonctionnera peut-être les données par paquets de 100000 et re-parcourir le fichier pour les comparer à tous les autres. En utilisant le fait que les données sont triées, il y des possibilités de ne pas y passer trop de temps.
Un détail, penser à compiler en mode release plutôt que debug, il peut y avoir un gain de place (surement faible) et surtout un gain de CPU.

[marc92]

En réalité mon fichier contient d'autres champs dont j'ai besoin. Le fichier fait en tout 19,5 GB.
Je vais passer les long en float dans mon programme, cela devrait diminuer sensiblement la taille.
Idem pour Debug > Release ...
Merci.

[ternel]

A tout hasard, tu ne pourrais pas modifier la génération du dit fichier pour mettre en évidence ces couples?

Autre possibilité peut-être intéressante.

Soient quatre nombres a1, a2, b1, b2, tels que a1/b1 = 2 et a2/b2 = 2.
alors si a1 < a2, b2 < b1.

Voyons l'ensemble des nombres comme une séquence.
Le premier a est son début, le premier b sa fin.

si a/b < 2, il faut augmenter a donc avancer dans la liste. Sinon, il faut augmenter b (donc reculer dans la liste)

Donc si tu parcours les a dans l'ordre croissant, et les b dans l'ordre décroissant, tu n'as pas besoin de tout le fichier (et donc, pas besoin de le stocker intégralement)
Si tu crée une copie du fichier trié en ordre décroissant, il suffit de lire dans dans les deux fichiers dans l'ordre naturel des fichiers.

[bacelar]

Heu, selon les spécifications Intel, qui ont dû être suivies par M$, l'espace d'adressage d'un programme 64bits devrait facilement encaisser 19,5 GB de données en mémoire virtuelle.
Si vous configurez votre système de swap pour encaisser les données, votre programme devrait ramer mais pas planter/bad_alloc.

[marc92]

A tout hasard, tu ne pourrais pas modifier la génération du dit fichier pour mettre en évidence ces couples?

Autre possibilité peut-être intéressante.

Soient quatre nombres a1, a2, b1, b2, tels que a1/b1 = 2 et a2/b2 = 2.
alors si a1 < a2, b2 < b1.

Voyons l'ensemble des nombres comme une séquence.
Le premier a est son début, le premier b sa fin.

si a/b < 2, il faut augmenter a donc avancer dans la liste. Sinon, il faut augmenter b (donc reculer dans la liste)

Donc si tu parcours les a dans l'ordre croissant, et les b dans l'ordre décroissant, tu n'as pas besoin de tout le fichier (et donc, pas besoin de le stocker intégralement)
Si tu crée une copie du fichier trié en ordre décroissant, il suffit de lire dans dans les deux fichiers dans l'ordre naturel des fichiers.

-----------------------------------------------

Cette solution semble intéressante et devrait fonctionner. Je vais la tester. Encore merci pour vos suggestions.

MB