Exo 5 mémoire

Je pense avoir une solution pour le problème 5 mais malheureusement je ne comprends pas du tout comment est évaluée la quantité de mémoire utilisée.

Premièrement, je ne comprends pas où se situe la limite. Pour le problème 4 par exemple on nous impose une limite de 20mo, sauf que... je suis passé avec 32mo. Mieux encore, sur le problème 1 la limite est à 1mo, mais je suis passé avec 7mio. Or je ne stocke rien, si ce n'est les inputs, donc j'en déduis que ces 7mio ne viennent pas de mon programme. Mais d'où viennent-ils ?! Sur le problème 1, vous ne semblez pas les prendre en compte pour évaluer la quantité de mémoire utilisée. Mais, 7mio en ne stockant rien, c'est beaucoup, surtout pour un prgm de 10 lignes. Revenons sur le pb4, certains instances passent avec 2mo, soit nettement moins que pour le problème 1, pourquoi ?! Si 7mio est le minimum, sans rien stocker, comment je peux tomber à 2mo ?!

Venons en au problème, sur le problème 5 je passe les 5 premières instances avec 4,5mo, mais sur la 6ème le test échoue car trop de mémoire est utilisée et il m'indique 914Kio, soit très loin de la limite. Soit, j'en déduis qu'il est incapable de donner la mémoire utilisée, mais qu'il s'arrête quand même. Sauf que le truc c'est que j'ai tout essayé pour prendre le moins de place possible. Je commence par prendre le graphe en input, puis je fais ce que j'ai à faire dessus, puis je le supprime en libérant la mémoire, puis enfin je prends les requêtes en les traitants une par une. Je ne peux pas prendre moins de mémoire, je ne fais que sauvegarder le graphe, en listes d'adjacences; et 5 autres tableaux d'entiers de taille n (typiquement le tableau signaux). Il m'est impossible de prendre moins de place, et le j'ai demandé au Garbage Collector de Caml de m'indiquer combien de mémoire il utilisait, et nous sommes très loin des 20mo. Je vois pas où est-ce que je prends trop de place. Alors j'ai essayé de changer de structures, quitte à sacrifier le temps j'ai essayé d'utiliser un type moins lourd pour mon graphe (Au lieu de d'ensemble d'entiers via Set.Make, n'utiliser que des simples List), et là surprise : je ne passe même plus le premier test pour faute de mémoire. Ça n'a plus aucun sens, pourquoi est-ce qu'en sacrifiant le temps pour la place, je prends encore plus de mémoire. Non seulement j'en prends plus, mais pas qu'un peu, puisqu'avant j'utilisais 4mio et maintenant je dépasse les 30 ?!

En bref, comment en utilisant uniquement 5 tableaux d'entiers de taille N, et un graphe en liste d'adjacence de N sommets et M arête (donc en utilisant N + 2*M case de mémoire), je ne passe pas ?! J'ai toujours laissé passer les calculs très bizarres de la mémoire (cf ce que j'ai dit sur le problème 1), mais là ça n'a plus aucun sens.

Dernière interrogation, pour éviter de me prendre toujours plus de pénalités (à -256 points...) je me suis mis à tester mon prgm pour la problème 5, dans le testeur du problème 4 (en changeant juste les inputs), et il m'indique au plus 17Mio dans la dernière version (celle où je sacrifie la complexité en temps avec des List et non des Set) et 22 si j'utilise des Set (ce qui est prévisible). Mais pourquoi sur le problème 5, c'est l'inverse ?! Est ce qu'avoir plus de calculs (moins bonne complexité en temps) demande plus de mémoire ?!

Êtes vous sûr d'avoir mis la "véritable" (cf ce que j'ai dit sur le pb1) limite de mémoire à 20Mo pour le problème 5 en Ocaml?

Bon courage et merci d'avance si vous réussissez à m'aider.

Désolé si mon ton sonne sec, je me pose honnêtement toutes ces questions et je suis un peu HS après avoir tout essayé pour optimiser mon code pendant des heures. Avec des retours que je comprends pas (pour ne pas dire absurde). Bonne soirée à vous,

Bonsoir,

Pour info les contraintes mémoire et temps sont adaptées en fonctions des langages (plus de détails ici).

Lorsque je lance ton programme sur tous les tests (même ceux qui sont skipped), je remarque que tu passes tous les tests sauf le 05 (ton programme crashe avec un stack overflow et la consommation mémoire est très très grande).

J'ai alors essayé de compiler ton code avec le drapeau -g et lancer ton programme avec OCAMLRUNPARAM=b et le test 05 en entrée. Voici le résultat que j'ai obtenu :

1
2

Fatal error: exception Stack_overflow
Raised by primitive operation at Pit_pat in file "/tmp/pit_pat.ml", line 91, characters 13-28

En espérant t'avoir aidé,

PS je parle du programme de ce rendu

Merci beaucoup !

Malheureusement je n'arrive pas à résoudre, en réalité c'est devenu encore plus mystérieux. À la ligne et aux caractères indiqués, je fais juste un Array.make n []. Je demande donc simplement un tableau de listes vides de taille au plus 100000. Ce que j'utilise aussi pour stocker mon graphe, il n'y a aucune raison pour que mon prgm plante sur cette instruction, et puis pourquoi sur un test en particulier o_O. C'est délirant !

rbvuipgenazpcujbzepu bpcoenc ebpcojbpeph bveuoabfui anecfmaz AHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

J'ai trouvé, j'ai simplement mis rpz i au lieu de find i à un endroit, du coup c'était le bordel. Des heures pour cette merde AHHHHHHHHHHHHH

Merci beaucoup pour votre aide et bonne soirée ! 😊😊

Pas de soucis, je clos le thread.

Bonne continuation pour la suite du concours.