Salut,

L'étape "cruciale" lorsqu'on remplit un std::vector est le moment où l'on rajoute un élément de plus que ce que la capacité du tableau n'autorise, car il faut à ce moment là augmenter la capacité du tableau.

Et ca, ca se fait en demandant (au système d'exploitation) un nouvel espace mémoire, dont la taille est -- généralement -- équivalente au double de la capacité actuelle du tableau.

Le problème va survenir parce que, pendant un court instant, le tableau va utiliser trois fois la taille de l'espace mémoire qui correspond à sa capacité actuelle, et que le système d'exploitation risque donc de ne pas avoir assez d'espace mémoire à nous offrir.

Bien sur, je ne m'étendrai pas sur le problème de performances que cela engendre, car il faudra que le tableau copie ou déplace l'intégralité de ce qu'il contient de son espace mémoire d'origine vers le nouvel espace mémoire qu'il vient d'obtenir de la part du système d'exploitation.

Par chance, on peut limiter grandement les situations dans lesquelles il devient nécessaire d'augmenter la capacité du tableau, par exemple, avec la fonction reserve(), qui a pour effet de faire directement en sorte que la capacité du tableau soit "directement suffisante" pour nous assurer que le tableau n'aura jamais besoin d'augmenter sa capacité.

Malheureusement, tous les essais que j'ai pu faire m'ont mené à la conclusion qu'il n'est clairement pas possible de monter au delà de 1 073 741 824 double dans un std::vector (du moins, sur mon système actuel).

Tu peux faire toi-même le test, car, selon ton système, les valeurs peuvent changer: j'ai utilisé le code "tout simple que voici:

#include <vector>
#include <iostream>
int main(){
    std::vector<double> tab;
    size_t size = 2;
    try{
        while(true){
        tab.reserve(size);
        size*=2;
        }
    }
    catch(std::bad_alloc&e){
    }
    std::cout<<tab.capacity()<<"\n";
    return 0;
}

Si bien que, selon mon test, tu devrais pouvoir avoir un code proche de

int main(){
    std::vector<double> tab;
    tab.reserve(1073741824);
    std::ifstream ifs("fichier.txt");
    double d;
    while(ifs>>d && tab.size()

qui te permettrait de charger le maximum d'informations possibles.

Seulement, il faut faire attention!!! Car cela va te faire bouffer littéralement toutes les ressources de ton pc, au point que plus rien d'autre risque de fonctionner!  Et ca, ce n'est pas vraiment la meilleure idée que l'on puisse avoir

Ce qu'il faudrait donc, dans un premier temps, c'est essayer de savoir combien de segments se trouvent dans ton fichier, puis d'essayer de travailler "par lot", en découpant ton fichier en tronçons de ... mettons, 1 000 000 de données.

Car, si j'ai bien compris, les calculs que tu fais ont toujours trait à un segment donné et au segment qui se trouve "juste après" dans le fichier?

Bonjour koala01,

Merci pour ta réponse rapide.

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. Mon fichier comprends 160 millions de segments ... soit 19,5 GB !

Dans ce cas est-ce que c'est judicieux de découper le fichier en tronçons ?

Merci.

Marc

Ca peut être judicieux d'avoir un moyen de trouver rapidement des zones intéressantes.

p.ex. puisque tout est trié, tu peux avoir un curseur de lecture L et un de recherche R.

Tu commences avec L sur le premier élément, et R sur le second, et avec une recherche dichotomique (std::upper_bound()), tu cherches entre R et la fin, un élément qui matche, c'est ton nouveau R

Si tu trouves exactement, c'est parfait. Dans tous les cas tu sais qu'à partir de maintenant, pour le L suivant, ta recherche dichotomique se fait dans le nouvel [R, fin[.

Le hic, c'est si tu as du texte qui ne permet pas de travailler par bloc. Mais même si tu arrives à repasser sur des blocs, la recherche dichotomique va soit provoquer beaucoup de petites I/O (une catastrophe), soit beaucoup de chargement de buffers, pas forcément mieux.

Honnêtement, je regarderai s'il n'y aurait pas moyen de faire ça avec un Base de Données. Je ne suis pas un grand connaisseur, mais je soupçonne que cela peut être plus efficace.

PS: comme dit sur dvpz, oublie goto. Sincèrement!

PPS: si tu connais certaines propriétés de croissance de tes nombres, il peut y avoir moyen d'utiliser une recherche plus efficace que la dichotomique.

Un grand merci pour ton analyse. Il n'y a hélas pas de propriétés sur la croissance de ces nombres. J'avais préalablement fait un sort sur ce fichier.

Dans mon fichier, je peux supprimer les colonnes textes (noms des extrémités des segments) et vais travailler sur ta piste de la recherche dichotomique même si cela nécessite beaucoup d'I/O. Je préfère un programme un peu long qu'un "bad_alloc".

Merci.

A mes doux souvenirs des tris externes où la RAM ne dépassait pas 640ko, sniff.

Bon, des algorithmes un peu moins bourrin que de remplir la RAM comme une dinde, c'est pas ça qui manque.

Google doit te permettre de trouver ton bonheur avec "external sort".

Mais, avec une programme 64bits et en mettant ce qui faut dans le système de swap/mémoire virtuelle, on peut avoir une dinde assez grande, et c'est bientôt Thanksgiving.

Bonjour Bacelar,

Je découvre le "tri externe" qui permet de passer outre les limitations de la taille de la RAM. Cela peut-être utile à connaitre.

Mais ici le fichier est déjà trié. La recherche dichotomique semble s'imposer ...

Merci.

koala01 a écrit:

L'étape "cruciale" lorsqu'on remplit un std::vector est le moment où l'on rajoute un élément de plus que ce que la capacité du tableau n'autorise, car il faut à ce moment là augmenter la capacité du tableau.

Et ca, ca se fait en demandant (au système d'exploitation) un nouvel espace mémoire, dont la taille est -- généralement -- équivalente au double de la capacité actuelle du tableau.

Le problème va survenir parce que, pendant un court instant, le tableau va utiliser trois fois la taille de l'espace mémoire qui correspond à sa capacité actuelle, et que le système d'exploitation risque donc de ne pas avoir assez d'espace mémoire à nous offrir.

On peut s'affranchir de ce soucis en utilisant un conteneur dont l'occupation en mémoire n'est pas continue, type liste chainée std::list. On aura de moins bonnes performances lors du parcours de la collection, mais on sera affranchi du soucis d'insertion, non ?

Après, de toute manière, pas n'importe quel PC va pouvoir charger 19,5 GB en RAM

Mais quel est ton algorithme exactement ? puisque le code que tu nous as fourni est plutôt sale et j'ai l'impression que tu veux faire du combinatoire sur 19,5 GB !

EDIT : Ah non voilà, avec un tri et des algos de recherche, ça me semble déjà plus judicieux

-
Edité par romantik 21 novembre 2017 à 14:24:53

Ceci étant dit, d'après ton code, tu as affaire à  un fichier texte.  Ce n'est clairement pas le meilleur moyen de représenter les informations, car un fichier binaire (dont tu aurais expurgé tout ce qui n'a rien à voir avec tes segments) pourrait s'avérer bien plus efficace.

A moins, bien sur, d'envisager la création d'un fichier d'index, ce qui est toujours possible

Je m'explique:

Un fichier texte, c'est très bien pour permettre à un utilisateur humain de comprendre ce qui se trouve dans le fichier.  Mais ce n'est certainement pas la représentation la plus efficace que l'on puisse trouver pour que l'ordinateur puisse manipuler les données

Comme tes valeurs sont représentées sous forme de double, dans un fichier texte, elles peuvent aussi bien prendre la forme de 0.4 que la forme de 3.1415926 ou encore la forme de 01234 e-12.  Si, en plus, il y a des informations autres qui viennent se fourrer dans l'histoire, il devient tout à fait impossible de déterminer le nombre de bytes dont il faut se déplacer dans le fichier (dans un sens ou dans l'autre) pour pouvoir atteindre une donnée spécifique, sur base de la position de la donnée que l'on vient de traiter.

Une solution pourrait consister à créer un deuxième fichier (binaire) qui contiendrait l'offset de chacun des segments qui t'intéresse, dans l'ordre où ils apparaissent, car un offset écrit sous forme binaire prendra toujours la même taille sur le fichier.  De cette manière, si tu es sur le segment 34568 et que tu veux retrouver le segment 156485, il te "suffit" de te déplacer de (156485 - 34568) = 121917 * la taille d'un offset pour pouvoir retrouver l'offset auquel se trouve le segment qui t'intéresse.

Une autre solution consiste, comme je l'ai dit, à créer un fichier binaire expurgé ne contenant que les informations de segment qui t'intéressent, car, un double est toujours composé d'un nombre bien défini de bytes (8, sur ma machine), ce qui te permet, encore une fois, de te déplacer plus rapidement dans le fichier, car, il "suffit" de te placer à l'offset correspondant au "numéro" du segment qui t'intéresse multiplié par la taille d'un double pour pouvoir le lire directement.

Après, d'autres solutions pourraient être envisagées, comme, par exemple, le recours à une base de données... Mais, l'un dans l'autre, le problème qui consiste à être confronté à un nombre d'éléments bien plus important que celui que ta machine peut décemment en contenir reste un gros problème

Moi je ne ne chargerais déjà pas la totalité des données, car ça ne sert probablement à rien hormis saturer la RAM de la machine. Je segmenterai mon bloc de données en pages, je me débrouille pour monter en mémoire un index complet des pages, sans monter leur contenu, puis un système de cache pour monter les contenus à la demande avec un système d'identificateur de page et des shared/weak pour les contenus. De sorte que je vais pouvoir limiter la taille de mon cache à x pages, et je peux m'arranger pour définir une stratégie de conservation des pages dans le cache qui sera adaptée à mon problème (garder les plus demandées par exemple, ou bien garder les dernières demandée...). Un tel système va m'imposer de maintenir l'index et de faire en sorte qu'il soit toujours synchro avec les données sur le disque, mais en contrepartie me coûtera bien moins en RAM car si grand que puisse être le fichier de données, la taille de l'index sera relativement petite et je dispose en outre de la possibilité de segmenter mon fichier, ie avoir un fichier d'index et x fichiers de données, ce qui pourra le cas échéant permettre de gérer des jeux de données absolument monstrueux, en déportant les fichiers de données sur des mémoire de masse externes qu'on connectera à la demande. En proxyfiant bien tout ça, l'utilisateur accédera à ses données comme s'il s'agissait d'un tableau entièrement contenu en mémoire.

Par exemple en travaillant sur un jeu de données de 64 Go, et une page de 8 Mo, mon index contient 4000 entrées. J'ai le coût fixe des 4000 entrées (mais ce n'est pas bien lourd) auquel il faudra ajouter le coût du nombre de pages que j'ai dans le cache, en le fixant à 10 pages je bouffe 80 Mo ce qui est tout à fait supportable pour un PC moderne, si je suis gourmand je monte à 20 pages 160 Mo, pas de soucis non plus. Si ta stratégie de cache est bien foutue, tu n'auras probablement pas besoin de plus, après il faut régler et affiner le bazar mais ça nécessite plus d'analyse (et des tests de performances)...

-
Edité par int21h 24 novembre 2017 à 20:48:24