Limite pour la taille d'un vector

Bonjour à tous!

Bon... j'ai un petit problème technique à vous poser... J'ai un programme (VC++) qui insére des strings de longueur 100 (environ) dans un vector<string>.
Il doit ensuite trier ce vector puis le lire pour écrire dans des fichiers ce qu'il contient. C'est un peu résumé mais en gros c'est ça...

Bref, je m'aperçois que potentiellement, mon programme doit pouvoir extraire et stocker dans ce vector 34 000 000 de strings... Pour ensuite les trier et les lire.

Pensez-vous cela possible? J'ai du mal à croire que beaucoup de PC puissent tenir la charge...

Sa devrait prendre dans les 200mo... donc ça passe :).

Cool!

Mais quel calcul tu fais pour trouver ça? Je ne trouve que des tailles aberrantes...

Bonjour,
Si ça peut aider, std::vector possède une fonction max_size() qui renvoit la longueur maximale théorique d'un vector atteignable par la machine.

Mais bon, dans ton cas, il me semble que c'est rapé :

En supposant qu'une string de longueur 100 fasse environ 100 octets :

34 000 000 * 100 = 3 400 000 000 octets
3 400 000 000 / 1024 = 3320312 ko
3320312 / 1024 = 3242 mo
3242 / 1024 = 3.1 go !

100 * 34 000 000 = 3 400 000 000 octets ~ 3 Go.

Ca passe pas...

Déjà si tu as autant de strings tu dois avoir des fichiers énormes!

Les solutions que je vois, c'est d'utiliser des choses comme le tri par fusion avec des fichiers: tout d'abord tu fais plusieurs fichiers avec par exemple dans chacun 1000 strings triées, et ensuite tu appliques le tri par fusion à ces fichiers en créant à chaque fois un fichier de la taille de la somme des deux fichiers desquels il est issu...

Le tri par fusion ne te demande que de lire les fichiers ligne à ligne, sans devoir les stocker intégralement en mémoire, ce qui fait que tu auras une consommation mémoire quasi nulle :ccool:

Ouai voilà! C'est ce que j'avais trouvé aussi... du coup c'est grillé...

En fait pour expliquer un peu le contexte, j'ai environ 10 000 fichiers contenant chacun près de 4 000 lignes. Le tout prend entre 3 et 4 Go sur un DVD. Le but est de stocker ces lignes dans un conteneur, de les trier, puis de les réécrire (après un formatage spécial) des des fichiers séparés (A savoir un fichier pour chaque lignes commençant par les mêmes 10 caractères). Sur un traitement de 60 fichiers en entrée, ça me donne environ 800 fichiers en sortie. Je pense que ce nombre ne devrait pas exéder les 1000 quelque soit le nombre de fichiers en entrée.

Bref, toujours est-il qu'il faut que je stocke et trie 10 000 x 4 000 = 40 000 000 de lignes......

Citation:

---

Envoyé par Arzar

En supposant qu'une string de longueur 100 fasse environ 100 octets :

---

Salut,
Pourquoi la longueur d'une string devrait être proportionnelle à sa taille ? Il peut y avoir un buffer séparé avec une allocation dynamique dédiée non ?

Salut,

Une string contient trois pointeurs (vers la chaine, vers la fin de la chaine et vers la fin de la zone allouée) et une allocation dynamique qui correspond à la taille de la chaîne.

Une string de 100 caractères pèse donc 103 octets (3 en statique et 100 en dynamique).

Citation:

---

Envoyé par Dreambeliever

Salut,

Une string contient trois pointeurs (vers la chaine, vers la fin de la chaine et vers la fin de la zone allouée) et une allocation dynamique qui correspond à la taille de la chaîne.

Une string de 100 caractères pèse donc 103 octets (3 en statique et 100 en dynamique).

---

J'ai lu un peu rapidement et j'ai cru qu'il voulait dire que les 100 caractères étaient contigües dans le vecteur. Donc au temps pour moi, je n'ai rien dit :oops:

Salut,

Citation:

---

Envoyé par caradhras

Le but est de stocker ces lignes dans un conteneur, de les trier, puis de les réécrire (après un formatage spécial) des des fichiers séparés (A savoir un fichier pour chaque lignes commençant par les mêmes 10 caractères).

---

Je ne vois pas bien pourquoi tu as besoin de trier toutes les chaînes d'un coup pour faire ça.
Tu commences par créer les fichiers de destination en ajoutant chaque chaîne dans son fichier, puis tu reprends chaque fichier que tu tries indépendamment des autres.

MAT.

vContent.max_size() = 134 217 727

ça signifie que je ne peux pas stocker plus de 134Mo (approx.) dans mon vecteur?

Soit, en partant du principe que chaque string stocké fasse 103o : ~1 300 000 strings...

Et j'en ai 40 000 000 à traiter... :aie:

Citation:

---

Envoyé par caradhras

vContent.max_size() = 134 217 727

ça signifie que je ne peux pas stocker plus de 134Mo (approx.) dans mon vecteur?

Soit, en partant du principe que chaque string stocké fasse 103o : ~1 300 000 strings...

Et j'en ai 40 000 000 à traiter... :aie:

---

cf mon message précédent avec le tri par fusion.

Citation:

---

Envoyé par Mat007

Salut,


Je ne vois pas bien pourquoi tu as besoin de trier toutes les chaînes d'un coup pour faire ça.
Tu commences par créer les fichiers de destination en ajoutant chaque chaîne dans son fichier, puis tu reprends chaque fichier que tu tries indépendamment des autres.

MAT.

---

C'est plus par facilité qu'autre chose parce que les fichiers de destinations sont des fichiers XML... Du coup pour les trier c'est moins évident. Mais je crois bien que c'est la seule solution...

Par contre, ça veut dire qu'il y aura 40 millions d'accès en écriture répartis sur 800 fichiers...

EDIT : Dreambeliever => Je suis en train de creuser aussi la solution du tri fusion ;) Mais ça veut dire qu'à la fin j'obtiendrai un fichier trié de 3.4 Go. Bon celà dit c'est pas vraiment un problème...

Non, c'est vrai que je me suis mal exprimé :aie:
Pour clarifier :

max_size renvoit le nombre d'élément maximum de type T que peut contenir un vector en se basant sur sa taille statique (sizeof(T))
Par exemple, chez moi :
std::vector<std::string>::max_size() : 134 217 727
std::vector<int>::max_size() : 1 073 741 823

Donc je suis sensé pouvoir mettre jusqu'à 134 217 727 string dans un vector.... Mais en effet c'est trompeur dans ce cas, car le calcul ne tient pas compte du fait que la string elle-même alloue de la mémoire, comme l'a expliqué DreamBeliever :mrgreen:

En fait je me suis aussi trompé sur la taille d'une string:

un pointeur fait 4 octets (sur les systèmes 32 bits), donc la taille de la string est de 12 + la taille de la chaine. :oops:

Citation:

---

Envoyé par Arzar

Bonjour,
Si ça peut aider, std::vector possède une fonction max_size() qui renvoit la longueur maximale théorique d'un vector atteignable par la machine.

Mais bon, dans ton cas, il me semble que c'est rapé :

En supposant qu'une string de longueur 100 fasse environ 100 octets :

34 000 000 * 100 = 3 400 000 00 octets
3 400 000 000 / 1024 = 3320312 ko
3320312 / 1024 = 3242 mo
3242 / 1024 = 3.1 go !

---

Omg... je crois que j'ai oublier un zéro dans mon calcul xD.

J'ai planché un peu sur les solutions possibles et je pense partir là dessus :

Citation:

---

Pour chaque fichier f1

Pour chaque ligne de f1

Ecrire la ligne dans le fichier f2 correspondant aux 10 premiers caractères

---

Je me retrouve donc avec quelque chose comme 1000 fichiers contenant chacun 40 000 lignes (environ). Puis :

Citation:

---

Pour chaque fichier f2

Extraire les lignes dans un vector

Trier le vector

Ecrire le fichier XML en sortie

---

Salut,

En fait, il y a deux problèmes distincts:

Celui du nombre d'éléments qu'un vecteur peut contenir, et qui est limité par:

1. Le nombre d'adresses mémoire accessibles
2. la mémoire totale disponible
3. la plus grosse plage mémoire contigüe disponible

Car, en effet, un vecteur n'est qu'un tableau contigu d'éléments fort similaire à ce qui se fait en C ou en C++ avec les fonctions repsective malloc et new.

D'un autre coté, il y a des restrictions plus ou moins similaires au niveau de la std::string, même si les différents caractères qui la représentent peuvent potentiellement ne pas être contigus en mémoire.

Ces limitations seront modifiées par une série de situations purement contextuelles comme

• Le système d'exploitation utilisé (certaines versions de windows mettent des limites arbitraires à la quantité de mémoire manipulable par une application)
• la quantité éventuelle de mémoire virtuelles dont dispose le système d'exploitation
• la quantité de mémoire vive dont dispose le système

et par une série de situations purement factuelles (donc impossible à prévoir de prime abord) comme le nombre d'applications qui fonctionnent en même temps, et bien sur, l'utilisation de la mémoire (vive et / ou virtuelle) que font chacune de ces applications.

Tout cela pour dire qu'il faut encore énormément se méfier des calculs théoriques permettant de savoir si "ca passe ou non", car la pratique sera souvent différente:

Si le calcul théorique met en évidence que "ca ne passe de toutes façons pas", tu peux t'y fier les yeux fermés.

Mais s'il met en évidence que "ca passe" mais que tu es fort proche des limites "admises", cela pourrait ne plus passer une fois en situation réelle...

Ceci dit, il ne faut pas se faire d'illusions: tu ne pourra de toutes manières pas partir sur moins de 40.000.000 de lectures et autant d'écritures, vu que tu devra de toutes manières lire l'ensemble des données et les réécrire.

De plus, je présumes que cette application sera destinée à être effectuée automatiquement à une période de "moindre activité" (typiquement, durant la nuit), de manière à remettre le système "en état" pour une nouvelle journée de travail.

Si ce point de vue se confirme, j'aurais tendance à dire que la facilité devrait prévaloir sur l'efficacité (finalement, si l'application "mouline" pendant deux heures au lieu de une alors que tu dors gentiment, quelle importance :question:)

Ce que je ferais alors, c'est travailler en deux temps:
Dans un premier temps, je répartirais les entrées de mes 60 fichiers d'origine dans les 800 à 1000 fichiers de destination.

Dans un deuxième temps, si les différents fichiers doivent présenter les données triées, je lirais chacun de ces 800 à 1000 fichiers de destination et j'effectuerais le tri de leur contenu.

Bien sur, cela signifie très clairement que l'on arrive à 80.000.000 de lectures et autant d'écritures, et que cela prendra effectivement deux fois plus de temps (ou peu s'en faut), mais cela nous donnerait l'assurance que l'ensemble du processus ne s'approchera jamais d'une "limite" quelconque due à l'état du système au moment où l'application sera en action ;)

Si tu es en XML, pourquoi ne pas t'appuyer sur un moteur XSL : tu génère ton fichier XML non trié et tu fais une transformation XSLT qui réordonne alphabétiquement ? Faudrait faire un bench pour voir si ce serait plus ou moins performant que tout faire à la main en C++.

Merci pour ces explications :ccool:

Je suis parti là-dessus : à savoir répartir les données contenues dans mes 10 000 fichiers dans 1 000 fichiers en sortie en effectuant donc un premier tri.

Puis je lis ensuite chacun des 1 000 fichiers créés. Et pour chaque je stocke tout dans un vector où j'effectue le traitement souhaité et je réécris tout correctement dans un fichier XML.

Bon après, comme tu dis, ça prendra du temps. Pour le moment j'ai extrait environ 400Mo des 3.4Go de données en 30 minutes... Je ferai donc tourner ça cette nuit ;)

Autre question pour rebondir un peu sur le sujet : Dans la première partie du processus, je n'utilise donc que très peu de mémoire puisqu'il ne s'agit que d'ouverture de fichier d'un côté et d'écriture de l'autre.
Les fichiers en entrée sont directement lu depuis un DVD. Les fichiers en sortie sont écrits sur un disque dur classique. A chaque ligne lue sur un des fichiers en entrée, j'ouvre le fichier de sortie correspondant, j'écris la ligne et je referme le fichier. Tout ça environ 40 millions de fois. Du coup ma question est la suivante : Y'a-t-il un intérêt quelconque à faire cette opération sur une machine plus puissante (en terme de proc par exemple)? Ou est-ce de toutes façons limité à la vitesse de lecture du lecteur DVD et à la vitesse d'écriture sur disque dur?

Tu sera, de toutes manières, effectivement limité du fait des vitesse de lecture et d'écriture...

Ceci dit, tu peux "gagner" un peu de temps en décidant malgré tout de lire l'ensemble du fichier d'origine d'une seule traite, avant d'en séparer le contenu dans les différents fichiers de destination.

il ne faut en effet pas oublier que, si tu prend le temps d'ouvrir un fichier, d'écrire dedans et de le refermer pour chaque ligne lue dans le fichier d'origine, ton lecteur DVD aura continué à tourner pendant tout ce temps, et qu'il devra "terminer le tour" avant la lecture suivante...

(tout ceci modulo, bien sur, la taille des informations lues et les différents buffers potentiels)