je voudrais réussir a afficher le plus petit et le plus grand nombres de toutes mes sous-listes réunis,
pouvez-vous m'aider ?
import random
liste=[random.randint(0,100) for i in range(7)]
liste2D = [[random.randint(0,100) for i in range(7)] for j in range(7)]
print (liste2D)
minimum= min(liste2D)
maximum= max(liste2D
print (liste)
print ("plus petit :",minimum)
print ("plus grand :",maximum)
for liste in liste2D:
for element in liste:
print (element)
oui et après il faudra refaire la même chose pour avoir la valeur max ?
Après les listes sont pas grandes on s'en fou un peu tu me diras, mais ça me gêne sur le principe
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
La solution la plus simple sur la base de ce que tu as déjà écrit et que je rappelle ci-dessous tout en ayant retiré ce qui n'est pas utile :
import random
liste=[random.randint(0,100) for i in range(7)]
liste2D = [[random.randint(0,100) for i in range(7)] for j in range(7)]
for liste in liste2D:
for element in liste:
print (element)
consiste à rajouter deux variables mini et maxi avant tes boucles for et à écrire ligne 7 et suivantes le petit bout de code que tu as dû apprendre pour calculer le minimum et la maximum d'une liste et que tout débutant a vu et consistant à mettre à jour mini et maxi en fonction de la valeur de element. D'expérience, je sais que ce bout de code est ici dans le cas de la recherche simulatanée mal écrit par les débutants (gestion des conditions). Algorithmiquement, elle a l'avantage de ne parcourir la liste qu'une seule fois pour faire echo à ce que dit fred.
thelinekioubeur a écrit:
minimum = min(itertools.chain(*liste2D))
Oui, ça semblerait la solution pythonique et rapide. D'après mes tests elle n'est pas la plus rapide :
from random import randint
from time import perf_counter
from itertools import chain
M=4000
N=10**9
liste2D = [[randint(0,N) for i in range(M)] for j in range(M)]
begin_perf=perf_counter()
print(min(map(min, liste2D)))
print("%.2f" %(perf_counter()-begin_perf))
begin_perf=perf_counter()
print(min(chain(*liste2D)))
print("%.2f" %(perf_counter()-begin_perf))
La problématique ici est de savoir si c'est mieux de faire en sorte d'avoir min et max d'un seul coup en itérant sur les listes ou d'utiliser une méthode rapide comme celle proposée par vous deux en parcourant deux fois la liste de sous listes.
Sur le principe, je ne là parcourrait évidemment qu'une fois, mais laquelle est la plus efficace ?
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
La problématique ici est de savoir si c'est mieux de faire en sorte d'avoir min et max d'un seul coup en itérant sur les listes ou d'utiliser une méthode rapide comme celle proposée par vous deux en parcourant deux fois la liste de sous listes.
Sur le principe, je ne là parcourrait évidemment qu'une fois, mais laquelle est la plus efficace ?
Si tu ne la parcours qu'une seule fois, tu t'interdis des fonctions comme min et max et donc, le choix qui s'impose est de faire une double boucle for avec un test ce qui va être clairement lent en Python, entre 3 et 4 fois plus que d'utiliser map et parcourir deux fois la liste. Pour un code scolaire, on parcourra une fois, autrement, on utilisera autre chose.
Vu la nature du problème, il est assez naturel d'essayer reduce de functools couplé avec chain mais c'est aussi lent voire plus :
from random import randint
from time import perf_counter
from itertools import chain
from functools import reduce
M=4000
N=10**9
liste2D = [[randint(0,N) for i in range(M)] for j in range(M)]
begin_perf=perf_counter()
print(min(map(min, liste2D)), max(map(max, liste2D)))
print("%.2f" %(perf_counter()-begin_perf))
print('----------')
begin_perf=perf_counter()
def f(minimax, v):
mini, maxi=minimax
return (mini, v) if v>maxi else (v, maxi) if v<mini else minimax
it=chain([[float("inf"), -float("inf")]],*liste2D)
print(reduce(f, it))
print("%.2f" %(perf_counter()-begin_perf))
L'algorithmie domine toujours, la force de python ne doit pas être dans ses fonctions built-in. Si on ne trouve pas d'équivalent dans le langage pour avoir une solution algorithmique louable, alors on doit créer son module C.
fichier cython minimax.py
import cython
@cython.boundscheck(False) # Deactivate bounds checking
@cython.wraparound(False) # Deactivate negative indexing.
cpdef tuple get_min_max(list mylist):
cdef int mini = mylist[0][0]
cdef int maxi = mini
for li in mylist:
for value in li:
if cmp(value, mini) == -1: mini = value
elif cmp(value, maxi) == 1: maxi = value
return mini, maxi
cdef int cmp(int a, int b):
if a < b: return -1
elif a > b: return 1
else: return 0
De là je génère mon module avec cython minimax.so
from setuptools import setup
from setuptools.extension import Extension
from Cython.Distutils import build_ext
from autocython import PLATFORM_SUFFIX
ext_modules = [Extension("minimax" + PLATFORM_SUFFIX, ["minimax.pyx"])]
setup(
name="minmax",
cmdclass={"build_ext": build_ext},
ext_modules=ext_modules,
)
J'utilise mon module dans le fichier python
from minimax import get_min_max
from random import randint
from time import perf_counter
M = 4000
N = 10 ** 9
liste2D = [[randint(0, N) for i in range(M)] for j in range(M)]
def get_list_min_max(mylist):
return get_min_max(mylist)
def get_pascal(mylist):
return min(map(min, mylist)), max(map(max, mylist))
start = perf_counter()
print(get_list_min_max(liste2D))
print(perf_counter() - start)
start = perf_counter()
print(get_pascal(liste2D))
print(perf_counter() - start)
Alors en effet, ça peut paraître fastidieux, mais quand on doit chercher à résoudre un goulot d'étranglement, cython c'est la vie !!!
EDIT:
Là j'y gagne un peu plus,
minimax.pyx
from cpython.mem cimport PyMem_Malloc, PyMem_Free
import cython
@cython.boundscheck(False) # Deactivate bounds checking
@cython.wraparound(False) # Deactivate negative indexing.
def get_min_max(list mylist):
cdef int value
resp = <int *>PyMem_Malloc(2 * sizeof(int))
if not resp:
raise MemoryError()
resp[0] = mylist[0][0]
resp[1] = resp[0]
for li in mylist:
for value in li:
cmp(value, resp)
mini, maxi = resp[0], resp[1]
PyMem_Free(resp)
return mini, maxi
cdef void *cmp(int a, int *array):
if a < array[0]:
array[0] = a
return NULL
if a > array[1]:
array[1] = a
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
L'algorithmie domine toujours, la force de python ne doit pas être dans ses fonctions built-in. Si on ne trouve pas d'équivalent dans le langage pour avoir une solution algorithmique louable, alors on doit créer son module C.
Alors en effet, ça peut paraître fastidieux, mais quand on doit chercher à résoudre un goulot d'étranglement, cython c'est la vie !!!
-
Edité par fred1599 il y a environ 3 heures
Merci d'avoir fait l'effort d'écrire tout ce code, c'est très intéressant et utile, surtout si on veut se lancer dans Cython.
Toutefois, l'amélioration de performance n'est pas du tout de l'ordre de ce qu'on devrait obtenir. Quand tu utilises Cython ou autres en Python c'est pour diviser le temps par 15 ou 20 voire bien plus.
D'ailleurs, pour me rendre compte, j'ai écrit le code en C++. Résultat, pour une liste de 4000 listes, chacune de 4000 entiers, les temps sont :
Python : 0.35s
C++ : 0.01s
On est dans un rapport de 1 à 30 et pas de 1 à 2.
Le fichier de test est ICI. La première valeur est 4000 qui est le nombre de listes et d'éléments dans chaque liste et derrière il y a les 16 millions d'entrées. Placer le fichier sur l'entrée standard. Le code C++ est ici :
#include <cstdio>
#include <vector>
#include <ctime>
using namespace std;
typedef pair<int, int> ii;
ii minmax(const vector<vector<int>> &LL)
{
size_t n {LL.size()};
ii mm;
int mini=LL[0][0];
int maxi=LL[0][0];
for (size_t i=0; i<n; i++)
for (size_t j=0; j<n; j++)
{
int v=LL[i][j];
if (v<mini)
mini=v;
else if (v>maxi)
maxi=v;
}
mm.first=mini;
mm.second=maxi;
return mm;
}
vector<vector<int>> capture()
{
vector<vector<int>> LL;
int n;
scanf("%d", &n);
for (int i=0; i<n; i++)
{
vector<int> L;
for (int j=0; j<n; j++)
{
int s;
scanf("%d", &s);
L.push_back(s);
}
LL.push_back(L);
}
return LL;
}
int main (void)
{
vector<vector<int>> LL=capture();
clock_t now=0, end=0;
now = clock();
ii mm=minmax(LL);
end=clock();
fprintf(stderr, "\nTemps CPU : %.2f secondes \n\n",
(double) (end - now) / CLOCKS_PER_SEC);
printf("%d %d\n", mm.first, mm.second);
return 0;
}
Probablement qu'il faut que tu utilises dans ton Cython de meilleures optimisations parce que Cython produit normalement un temps très très proche au temps du C/C++ (ça devrait être 0.02s ou 0.03s).
Je ne connais pas trop mais je remplacerais ton type list par un type **int. Tu peux regarder l'annotateur de code Cython, les parties de code qui sont annotées en jaune appellent l'API C ce qui ralentit. Je ne comprends pas l'intérêt de ta fonction cmp et en plus elle ne doit pas être inlinée par le compilateur et donc peut être une source importante de ralentissement.
Par curiosité, j'ai regardé ce que donne Numpy. Il est très très rapide (comme du C, environ 0.02s) mais il y a le coût énorme de conversion des entiers de la liste Python dans le Numpy array si bien qu'au total il est 2 x plus lent que Python. Mais on comprend tout l'intérêt de travailler avec Numpy dès le départ. J'ai essayé aussi Numba mais, il est très inefficace avec des listes de listes.
Ah mais oui je sais bien, seulement je suis partie de ta liste de listes, ce qui pénalise énormément le travail avec cython...
La fonction cmp divise par 2 mon temps d'exécution, avant je trouvais le même temps que toi avec une double boucle.
Difficile d'optimiser dans cette situation, et je t'avoue que mon objectif était de faire un meilleur temps que toi avec un algorithme plus naturel, j'ai pas cherché trop loin.
Si pars d'un int ** je suis obligé de reconstruire la liste, ce qui m'amène à des temps désastreux.
Mais effectivement, si je ne reconstruis pas, je m'approche sans doute énormément d'un code C ou C++.
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Je viens d'essayer ton code pyx sur ma machine et il donne finalement un temps plutôt décent
Cython : 0.06 s
donc un gain d'un facteur 6, par rapport à du Python pur, ce qui est déjà très bien. Toutefois, il faut bien reconnaître que le code Python est assez loin de l'algorithme simple qu'on pourrait avoir en tête (à cause du cmp).
Oh c'est bien mieux que ça, le facteur 6 représente une différence par rapport à l'exécution de fonctions "bindings C/C++" (min et max).
Si on avait vraiment du pur python, ça serait un facteur bien plus grand...
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Effectivement mais la différence n'est pas si énorme avec une double boucle qui met 0.55s chez moi avec le même fichier (je ne mets pas le code ici puisque c'est ce qu'est censé trouver l'auteur de la question ) donc la rapport est 1 à 9 au lieu de 1 à 6.
Après plusieurs essais, il me semble qu'on peut largement simplifier le code Cython de fred sans changer les performances. Ce qui est appréciable ici c'est qu'on obtient à une ligne près exactement le code naturel que l'on écrirait en Python pur et ne faisant qu'un seul parcours de la liste. Ce code est ce que l'auteur de la question initiale souhaitait, à savoir :
def get_min_max(mylist):
mini = maxi= mylist[0][0]
for li in mylist:
for value in li:
if value < mini:
mini=value
elif value > maxi:
maxi=value
return mini, maxi
Sur mon ordi, pour traiter le fichier de 16 millions donné en lien dans un message précédent, ce code met le temps suivant :
Python : 0.575s
Pour obtenir le code Cython équivalent, il suffit de rajouter une seule petite ligne, ce qui donne le fichier minmax.pyx suivant :
def get_min_max(mylist):
cdef int value, mini, maxi
mini = maxi= mylist[0][0]
for li in mylist:
for value in li:
if value < mini:
mini=value
elif value > maxi:
maxi=value
return mini, maxi
et le temps d'exécution est
Cython : 0.065s
Même pas besoin de mettre les décorateurs, ni d'importer cython explicitement ni d'utiliser le type list ni de fonction auxiliaire. Le code de fred me donne plutôt en moyenne
Cython fred 0.064s
Au total, le gain est d'un petit peu moins d'un facteur 9, ce qui est très appréciable alors qu'on a quasiment pas touché le code Python.
D'un autre côté, on atteint toute de même pas les performances d'un code C/C++ (les perf en C seront ici similaires à celles du C++) qui est encore 4 fois plus rapide que le code Cython. Et je ne vois pas comment on pourrait améliorer Cython si on part (en Python) d'une liste de listes d'entiers. Pour que le C puisse s'appliquer, il faut extraire les int de leur capsule Python et c'est déjà ce que fait le code ci-dessus. Si au départ, on avait eu un tableau Numpy ou un array du module array, là ça aurait été très différent et on aurait eu de meilleures performances.
J'avais entre temps créé un autre fichier .pyx si tu veux tester la différence de performance
cdef void swap(list li, int *mini, int *maxi):
cdef int v
for v in li:
if v < mini[0]:
mini[0] = v
elif v > maxi[0]:
maxi[0] = v
cpdef tuple get_min_max(list li2D):
cdef int mini = li2D[0][0]
cdef int maxi = mini
for li in li2D:
swap(li, &mini, &maxi)
return mini, maxi
Chez moi les temps sont identiques mais le code est plus simple.
ctypes est normalement moins efficace après expériences multiples, c'est un module qui a plus d'intérêt dans l'utilisation de librairies C déjà existantes, mais c'est possible, seulement j'aime pas l'utiliser.
Par contre c'est une fausse idée de croire que les codes cython se rapprochent de très près du C/C++. En fait c'est assez exceptionnelles, le but de cython n'est pas de l'être, mais d'améliorer les performances en y ajoutant du types statiques là où on peut. Ce code en est un bon exemple, où l'on part d'un type python spécifique (liste de listes), et la perte de temps pour convertir en C/C++ prend énormément de temps. On gagne 50% ce qui est déjà pas mal, mieux c'est possible avec effectivement numpy, mais là encore si on part de ce type python spécifique, la conversion n'est toujours pas simple et coûteux.
Maintenant si on veut se rapprocher du C, il faut faire du cython depuis le début, et là autant faire du C/C++. Pour moi dans cet exercice le but est atteint, car avec l'algorithme naturel, on crée un module qui améliore de 50% l'utilisation du binding C/C++ (min et max) qui me gênait dans le sens algorithmique.
Merci de m'avoir remis dans le bain de cython, ça faisait un bye que j'y avais plus touché. J'apprécie toujours autant surtout que cet exemple démontre la vraie valeur et l'intérêt de ce module.
- Edité par fred1599 5 avril 2020 à 21:43:46
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
J'avais entre temps créé un autre fichier .pyx si tu veux tester la différence de performance
Plutôt légèrement plus rapide : 0.063s voire un peu moins.
fred1599 a écrit:
ctypes est normalement moins efficace après expériences multiples, c'est un module qui a plus d'intérêt dans l'utilisation de librairies C déjà existantes, mais c'est possible, seulement j'aime pas l'utiliser.
Oui, c'est ce que je voulais dire, on écrit en C++ ou C et on exécute en Python via ctypes. J'ai l'impression que les conversion de type se faisaient assez facilement
fred1599 a écrit:
Par contre c'est une fausse idée de croire que les codes cython se rapprochent de très près du C/C++. En fait c'est assez exceptionnelles, le but de cython n'est pas de l'être, mais d'améliorer les performances en y ajoutant du types statiques là où on peut. Ce code en est un bon exemple, où l'on part d'un type python spécifique (liste de listes), et la perte de temps pour convertir en C/C++ prend énormément de temps. On gagne 50% ce qui est déjà pas mal, mieux c'est possible avec effectivement numpy, mais là encore si on part de ce type python spécifique, la conversion n'est toujours pas simple et coûteux.
Maintenant si on veut se rapprocher du C, il faut faire du cython depuis le début, et là autant faire du C/C++.
Je me suis mal exprimé mais c'est exactement ça que je voulais dire : utiliser Cython pour wrapper un lib C ou C++ et là les temps sont souvent très proches (mais pas toujours).
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Découverte Python Doc Tkinter Les chaînes de caractères
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Découverte Python Doc Tkinter Les chaînes de caractères
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Découverte Python Doc Tkinter Les chaînes de caractères
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Découverte Python Doc Tkinter Les chaînes de caractères
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Découverte Python Doc Tkinter Les chaînes de caractères