Mémoire autorisée en Python

Bonjour,

Je me demande si vos seuils de mémoire (et de temps) pour les codes donnés en Python ne devraient pas être revus. Plusieurs problèmes codés en Python ne sortent pas (erreur mémoire ou temps d'exécution) alors que le même algo codé en C lui sort.

Le dernier exemple que j'ai à disposition est QCM 2002, "2ème plus grand". L'algo le plus simple est le suivant : on trie la liste et on récupère l'avant-dernier élément de la liste triée. Si je le code en C avec qsort, je passe tous les tests, si je le code en Python avec la méthode sort() (et non pas la fonction sorted() qui elle crée une copie de la liste initiale), j'ai une erreur de mémoire.

Si celui en C fonctionne, c'est parce que c'est très difficile de discriminer entre un algorithme en O(n) (qui est attendu) et un algorithme en O(n log n). Dans un monde idéal, qsort ne devrait pas passer. Je suis donc content que Python soit bloqué ici, même si c'est pour une mauvaise raison (mémoire et non temps) :-)

Pour les temps d'exécution, il y a déjà un énorme facteur multiplicatif autorisé entre le C et Python (x 30 si je me souviens bien). Le problème de Python ici est que ses opérations sur les conteneurs masquent parfois une grande complexité derrière un appel simple... Cela fait assez longtemps qu'on voudrait essayer d'utiliser Psyco pour contourner ça. Je ne sais pas où ça en est. Honnêtement, on aurait du mal à autoriser plus de x 30 sans donner des avantages à Python dans d'autres exercices....

Pour la mémoire, on autorise 6 mégas supplémentaires. Pendant les demi-finales de l'an dernier, nous n'avions pas eu de problème avec 5 mégas en plus. Maintenant si vous avez des algorithmes dont vous pensez qu'ils sont optimaux (y compris au niveau de l'utilisation mémoire, en utilisant les structures de Python à bon escient) et qui passent en C et non en Python, on peut toujours augmenter cette valeur, ou éventuellement mettre un facteur multiplicatif (si les structures de bases prennent plus de mémoire pour chaque élément qu'en C). Je ne connais pas assez le Python pour me prononcer sur le sujet, si vous trouvez des références nous permettant de mieux ajuster ceci, je suis preneur :-)

Le recours à qsort n'était là que pour simplifier l'exposé de mon propos : le même algo voire des codes identiques qui ne réagissent pas de la même façon.

En réalité, j'ai le même problème avec l'algorithme linéaire : je l'ai écrit en C, il passe les 10 tests ; je le reprends en Python (à partir d'un copier-coller du code C ! je change juste un else if par elif, etc) et bien, j'ai une erreur mémoire :

QCM2002.2.7
Sortie de débogage :

Limite de memoire depassee
Erreur fatale

Je précise que j'ai évité une boucle du type for i in range(n) et même j'ai évité une boucle en for i in xrange(n) et que j'ai utilisé une boucle while .

Ce n'est pas du tout normal.

Pouvez-vous nous envoyer le code sur entraineur (at) ml.prologin.org pour qu'on puisse voir s'il faut augmenter la marge ou s'il s'agit plutôt d'un problème de facteur multiplicatif ? (un tableau d'entiers qui prendrait plus de place à être stocké qu'en C, par exemple).

Merci !

Ça y, c'est envoyé.

Vous avez testé mon code ?

Bonjour Candide,

Tout d'abord, désolé pour le délai plutôt long :)
Je suis en train de regarder le problème et refait plusieurs tests. Les coefficients que nous appliquons pour le python me semblent corrects.

Mais, en effet, l'algo qu'on à reçu sur info@ devrait en effet passer les tests ! Je cherche donc actuellement d'où vient le problème et ajusterai la mémoire sous peu !

Je referai un post par ici lorsque ça sera fait !

Bon j'ai un peu oublié de re-poster, mais la limite mémoire pour Python était en effet sous estimée.
Je l'ai donc ajustée, n'hésitez pas à poster ici si vous rencontrez toujours des problème, bien que normalement il n'y ait pas de raison maintenant :)