Discussion :

[dark_nights]

Bonjour tout le monde,

En fait je voudrais trier un fichier qui contient deux colonnes : un fichier et sa clé md5 (sachant que la première colonne est la clé md5).

J'aimerais savoir si c'est possible de trier ce fichier par rapport à la clé md5, en utilisant une commande en C++ ou Qt, et écrire le resultat dans un fichier texte, sans tout charger dans la mémoire et faire le tri à la main (donc un peu comme la commande sort de linux)...

Merci d'avance.

[Florian Goo]

Bonjour,

Tu ne veux pas charger en mémoire parce que le fichier est trop volumineux ?
À première vue, ça me semble difficile de faire ça sans charger en mémoire.

[dark_nights]

Oui il est très volumineux même, et c'est très lours à gérer en mémoire.

[koala01]

Salut, et bienvenue sur le forum.

Non, ce n'est pas possible: Un fichier est "gravé dans le marbre"...

Si tu veux modifier le fichier (d'une autre manière que le simple ajout d'une information à la fin de celui-ci), il faut "briser la pierre" et recommencer

Ceci dit, il est *relativement* facile d'arriver à obtenir un contenu trié, étant donné que, tant la somme Md5 que le nom du fichier peuvent être considérés comme étant de simple chaines de caractères.

En effet, la norme fournit un conteneur génial pour gérer des couples clé / valeur de manière triée: la classe map, disponible dans l'espace de noms std par inclusion du fichier d'en-tête <map>.

Tu peux donc te contenter d'un code "aussi simple que"

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
 
#include <map> // pour std::map
#inlcude <string> // pour ... std::string
#include <fstream> // pour std::ifstream et std::ofstream
#inlude <iostream> // pour std::cin et std::cout
#include <ssream> // pour std::stringstream
int main()
{
    std::cout<<"Introdusez le nom du fichier à trier :";
    std::string filename;
    std::cin>>filename;
    std::map<std::string, std::string> lamap;
    /* la récupération du contenu du fichier.
     * Les données récupérées sont introduites directement dans ù
     * le conteneur ad-hoc ;)
     */
    {
        std::ifstream ifs(filename.c_str());
        std::string temp;
        /* tant que nous arrivons à lire quelque chose dans le fichier*/
        while(std::getline(ifs,temp)
        {
            std::stringstream ss;
            ss<<temp;
            /* récupérons la clé et la valeur */
            std::string key;
            std::string value;
            ss>>key>>value;
            /* et plaçons les dans le tableau associatif */
            lamap.insert(std::make_pair(key, value) );
        }
    }
    /* le conteneur map étant automatiquement trié par la clé,
     * nous pouvons directement réécrire les éléments dans le fichier
     * (il sera détruit et réécrit)
     */
    std::ofstream ofs(filename.c_str());
    for(std::map<std::string, std::string>::const_iterator it = lamap.begin();
        it!=lamap.end();++it)
        ofs<<(*it).first<<" "<<(*it).last<<std::endl;
    /* c'est fini :D */
    return 0;
}

Le code est améliorable à loisir, et nous pourrions prendre la précaution de tester l'ouverture du fichier, la présence de lignes vides ou autres joyeusetés dans le genre

[white_tentacle]

Découpe ton gros fichier en petits fichiers, trie sur ces petits fichiers (pas de problème de mémoire, puisque le fichier est petit), et fusionne ensuite.

Lors de la fusion, tu n'as pas besoin d'avoir les deux fichiers en mémoire, puisqu'ils sont déjà triés. Il te suffit d'avoir une ligne de chaque fichier en mémoire.

[Florian Goo]

Il me semble qu'en lisant un fichier ligne par ligne, cela n'entraine pas le chargement dudit fichier en mémoire…
Je verrais bien un truc dans le genre :

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
 
long md5_min;
 
for(...) //pour chaque ligne du fichier
{
	long md5_lu = ...; //lire md5
 
	if(...) //est le md5 le plus petit ?
	{
		//écrire la valeur associée à md5_min dans fichier.temp
		md5_min = md5_lu;
	}
	else
	{
		//écrire la valeur associée à md5_lu dans fichier.temp
	}
}
 
//écrire la valeur associée à md5_min dans fichier_trié.temp
 
//effacer fichier
 
//remplacer fichier par fichier.temp
 
//effacer fichier.temp

Et tu fais une boucle parente, pour chaque valeur.
Tu peux aussi traiter plusieurs md5_min à la fois plutôt que d'en faire un seul, ça ira plus vite.

À ma connaissance (je peux me tromper), il n'y a rien de tout fait pour faire cela.

[dark_nights]

Merci beaucoup pour vos réponses
Mon problème venait du fait que je ne peux pas vraiment indexer par rapport à la clé md5, vu qu'ilpeut y avoir des doublons.
Dans ce cas, je serais obligé d'avoir une structure de map<string, vector<string>> ce qui est vraiment lourd à gérer.
En tout cas je crois que j'ai trouvé la structure de données convenable (map<string, string>) avec un peu de bidouillage après.
Merci encore une fois

[dark_nights]

@ Florian Goo

Je ne cherche pas que la md5 la plus petite. Je dois ecrire tous les md5 par ordre alphabétique. Comme tu dis, je ne récupère que la plus petite clé md5, et comment fais-je pour écrire le reste à moins que je fasse une autre lecture ?

[Florian Goo]

La plus petite clé est la seule qui n'est pas recopiée dans le fichier.temp !
Mais en effet mon algorithme n'est pas le meilleur

[Jean-Marc.Bourguet]

Bonjour tout le monde,

En fait je voudrais trier un fichier qui contient deux colonnes : un fichier et sa clé md5 (sachant que la première colonne est la clé md5).

J'aimerais savoir si c'est possible de trier ce fichier par rapport à la clé md5, en utilisant une commande en C++ ou Qt, et écrire le resultat dans un fichier texte, sans tout charger dans la mémoire et faire le tri à la main (donc un peu comme la commande sort de linux)...

Merci d'avance.

Tu as un fichier assez gros pour ne pas tenir en memoire? Il fait quelle taille?

system("sort...") est alors a coup sur la solution la plus facile a mettre en oeuvre.

Sinon, un merge sort tel qu'esquisse par white_tentacle. C'est pas tres complique a mettre en oeuvre. Tu peux faire une recherche sur "tri externe".