Problème 5 possible en Python avec quelle quantité de mémoire ?

Bonjour,

J'ai soumis un code Python qui passe les 15 premiers tests en moins de 0.5 secondes, mais qui plante sur le 16 ème test / Votre programme a dépassé la limite mémoire / 12.9 Mo.

Et même avec une gestion très serrée de la mémoire ("del" de toutes les variables inutiles avant d"en créer d'autres...) ça plante encore sur le test n° 18.

La contrainte a l'air très serrée pour Python, rien que le programme vide prend déjà 7.6 Mo

• êtes vous certains que c'est possible en Python et que c'est bien paramétré ?

• qu'il ne reste pas un N > 10 000 d'avant la modification de l'énoncé ?

• et qu'il n'y a absolument aucun test avec l,h > 1 000 000 ou S (surface totale de la flotte) > 10000 ?

Si quelqu'un a réussi le problème 5 en Python ça m'intéresse de savoir quelle quantité mémoire il a utilisé. Juste savoir si c'est possible de le faire avant de continuer à chercher...

Merci.

Modifie ton programme pour vérifier N, l, h, S; si il repère une erreur fait le afficher les données d'entrée pour vérifier ton hypothèse.

BTW, c'est quoi cette modification de l'ennoncé?

Et aussi, 10 000 vaisseaux -> 20 000 points -> 20 000 * 64 bits -> ~1MO donc ça rentre largement dans la mémoire limite.

Merci de ton idée de modifier le programme, mais au niveau 5 la correction n'imprime rien et je suspecte l'information de taille mémoire 13 Mo d'être inexacte, donc on avance dans le noir...

L'énoncé initial c'était 1 000 000 de vaisseaux (je leur ai signalé l'erreur) maintenant c''est 10 000 vaisseaux x 4 coordonnées = 40 000 entiers.

Au moment où je transforme les vaisseaux en lignes de force H et V, vu que S <= 10 000, je peux avoir provisoirement 40 000 + 20 000 + 20 000 = 80 000 entiers maxi, avant du supprimer les vaisseaux pour redescendre à 40 000 entiers, puis ensuite je recrée 60 000 entiers maxi pour le traitement.

Ce n'est pas grand chose 100 000 entiers, je ne comprends pas pourquoi ça ne passe pas les tests, mais c'est vrai que le 'del' Python ne libère pas forcement la mémoire, d'où ma question de savoir si quelqu'un a réussi en Python ?

Tu peux stocker les coordonnées sur 32 bit je crois.

1 000 000 de vaisseaux ça fait trop, mais surface de 10 000, tu as moyen d'économiser de la mémoire là dessus. A toi de réfléchir, je ne veux pas trop te gâcher le challenge.

Ce n'était pas impossible 1 000 000 vaisseaux et S = 10 000, ça voulait juste dire qu'il y avait forcement 99% de superpositions et donc je transformais directement les vaisseaux en lignes de force au fur et à mesure de leur saisie avant de les mettre dans une grille réduite équivalente.

Mais de toutes manières maintenant c'est 10 000 vaisseaux et ça ne passe toujours pas ... aaaaargh .... j'attends que quelqu'un me confirme que c'est possible en Python.

Comment tu transformes un vaisseau en ligne de force?

Et bien tu le recouvres de lignes de forces horizontales ou verticales. Tout le but de cet algorithme est d'optimiser ce choix (horizontal ou vertical) en fonction des vaisseaux qui se touchent.

Parce que quand le vaisseau est isolé le problème est trivial : les lignes sont verticales (si le vaisseau est plus haut que large) ou horizontales (dans le cas contraire).

Mais y'a un cas ou un vaisseau est déjà couvert par un autre et où il faut 0 lignes de force par exemple nan?

Le recouvrement est un cas où les vaisseaux ne sont pas isolés et bien sûr c'est le but du problème que de gérer tous ces cas.

Je pense avoir trouvé un algo correct puisque ça passe les 17 premiers tests rapidement avec un langage interprété, mais ça bute sur la contrainte de mémoire.

Le problème c'est qu'on ne gère pas directement la mémoire en Python - et d'ailleurs on ne sait même pas la limite attribuée par Prologin - mais en l'absence de fonction de tri .sort() ou sorted() qui peut faire doubler temporairement la taille d'un tableau, normalement il n'y a pas trop de surprises.

Donc tu as juste une liste de points de 40 000 élements max? Aucune autre liste? Tu libères bien les variables intermédiaires?

En fait au départ j'ai 40 000 entiers maxi (après saisie des 10 000 vaisseaux), puis temporairement 80 000 maxi (après conversion des vaisseaux en lignes), puis 40 000 maxi (après 'del' des vaisseaux) , puis en fait 100 000 entiers dans le pire des cas (avec les variables de traitement de l'algorithme).

Ca devrait passer et sur mon ordi sous linux en intégrant à différent endroits de mon code python / import resource / print( resource.getrusage(resource.RUSAGE_SELF).ru_maxrss ) ça utilise beaucoup moins de mémoire que ce que signale PROLOGIN.

Je vais essayer de quantifier le problème avec le problème n°3 très simple qui utilise pile 1 000 000 entiers.

J'AI TROUVE UNE EXPLICATION POSSIBLE grâce à l'exercice n° 3 : le test de performance de PROLOGIN signale 80 Mo au maxi, je suppose que c'est avec la contrainte maxi de 1 000 000 de minerais.

Utiliser 80 octets par entier, alors que normalement les entiers sont codés sur 4 octets (32 bytes), c'est 16 fois trop, il y a un gros PROBLEME.

Le même programme chez moi utilise 7 Mb à vide et 47 Mb avec 1 000 000 d'entiers, ça fait 5 octets (40 bits) par entier, là c'est normal.

Et même s'il y a eu une confusion entre Octets et Bits, ça consomme encore 2 fois trop de mémoire.

Tu affiches la consommation de ton programme je crois, sans prendre en compte celle de python (j'peux me tromper).

Essaie avec une limite de mémoire sur ton terminale et lance ton programme.

Tu te trompes oui, vu que je raisonne par différence.

Sur mon ordi : 7 Mbytes à vide et 47 MBytes avec 1 000 000 d'entiers, ça fait 5 Mo de différence lorsqu'on a jouté les 1 000 000 d'entiers, c'est cohérent.

Sur PROLOGIN : 80 Mo sur le problème 3 avec 1 000 000 entiers, la consommation de mémoire annoncée est étonnante.

7 Mbytes à vide et 47 MBytes avec 1 000 000 d'entiers, ça fait 5 Mo

Tu veux pas plutôt dire 7 mégabits et 47 mégabits ? 47 mégaoctets - 7 mégaoctets ça fait pas 5 mégaoctets.

OUI des mégabits plutôt.

47 Mbits - 7 Mbits = 40Mbits = 5 Mo, ce serait cohérent pour 1 000 000 d'entiers.

Alors que la conso de 80 Mo annoncée par PROLOGIN n'est pas cohérente pour 1 000 000 d'entiers.

Mais je n'ai pas trouvé de notice claire sur "resource.getrusage(resource.RUSAGE_SELF).ru_maxrss" donc j'ai un doute sur l'unité, si c'est des ko il resterait encore un facteur 2.

Après 30 tests (de toutes manières je suis au max de la pénalité au-delà de 16 tests)...

.. j'arrive aux conclusions (provisoires) suivantes :

1/ Le test n°16 est déjà passé à 18 Mo et a déjà planté à 10 Mo, donc les informations de mémoire utilisée ne sont pas très fiables.

2/ Le test n°17 est déjà passé à 39 Mo, donc il n'y a peut-être pas de limite de mémoire globale, mais probablement une limite de mémoire pour chaque test, si c'est vrai ça a des conséquences importantes sur la stratégie.

Car je m'étais dis qu'il y aurait toujours au moins 1 cas avec un vaisseaux en position (0,0) et un vaisseaux en position (1000000,1000000) et donc que ça ne sert à rien de réduire l'espace avec min(x),min(y),max(x),max(y) : il faut directement rechercher les zones vides partout à l'aide de booléens True/False (qui ne prennent pas beaucoup de place mémoire).

ERREUR : si c'est possible de réduire l'espace de façon aussi triviale par min max, alors ils l'auront fait, donc ils auront mis une contrainte mémoire spécifique à ce test, donc on doit le faire aussi : sur le test 16 il n'y avait même pas assez de place mémoire pour des booléens !!!

PROBLEME MEMOIRE RESOLU.

En C, et beaucoup de langages (l’interpréteur python est basé sur du C il me semble) un booléen, c'est juste un byte (8 bits) qui vaut soit 0000 0000 ou 0000 0001 donc on économise pas mes masses de mémoire avec ça...

C'est quand même 4 fois moins de place qu'un entier standard, alors quand la contrainte est serrée...

En Python lorsque je crée 1 000 000 de booléens, la fonction resource.getrusage(resource.RUSAGE_SELF).ru_maxrss augmente de 8000 "trucs"

• si l'unité de "truc" c'est le kbit alors c'est 1 octet par booléen

• si l'unité de "truc" c'est le ko alors c'est 8 octets par booléen

Toujours pas réussi à trouver l'unité de cette foutue fonction resource.getrusage(resource.RUSAGE_SELF).ru_maxrss

Soit à peu près 8000 ko -> cette fonction répond en ko.