Discussion :

[dreda123]

Bonjour !

Je pense avec un problème d'optimisation de mes boucles.

sachant que l_u et l_f peuvent attentre 800*3600, j'aimerai pourvoir faire mon calcul en moins de 10h comme je l'ai calculé

Avec vous une idée de comment optimiser cela ?

Merci !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
user = N.array(map(int,d[:,0]))
folder = N.array(map(str,d[:,1]))
z = N.zeros_like(user)+1
 
folderlist = uniq(folder)
userlist = uniq(user)
l_f = len(folderlist)
l_u = len(userlist)
size = l_u*l_f
 
activity_count_user_folder = []
for i in range(0,l_f):
	print i, "out of ", len(folderlist)
	cond1=(folder==folderlist[i])*z
	activity_count_user = []
	for j in range(0,l_u):
		cond2 = (user==userlist[j])
		cm = cond1*cond2
		activity_count_user.append(cm.sum())
	activity_count_user_folder.append(activity_count_user)

[Matthieu Brucher]

Ce n'est pas vraiment du calcul scientifique, là
Mais je ne sais pas comment améliorer ton code, mais par exemple la boucle for interne peut vraisemblablement être supprimée avec qqch comme :

activity_count_user.extend(user_list[N.where(userlist == user)])

si tant est que userlist est un tableau Numpy.

[DelphiManiac]

Au premier coup d'œil, utiliser xrange au lien de range devrait pas mal améliorer, mais je ne sais pas de quel ordre.

[eyquem]

Je comprends bien à peu près ce que fait ce bout de code mais des points restent un peu brumeux pour moi.

Est-ce que N est un alias pour le mot numpy ?

Je ne connais pas la notation d[:,0] si bien que je ne vois pas ce qu'est la variable obtenue par user = N.array(map(int,d[:,0]))

Puis je ne sais pas ce qu'est uniq:
s'agirait-il de la fonction unique() existant dans Numpy qui serait mal écrite ou d'un alias ?
Si bien que je ne sais pas exactement ce qu'on obtient comme variable userlist = uniq(user)

Que font les expressions folder==folderlist[i] et user==userlist[j] ?
Que fait l'expression cond1=(folder==folderlist[i])*z ?
Il y a des tableaux de booléens mais je ne comprends pas précisément.


Il faudrait aussi connaître la suite parce qu'on ne voit comme résultat de ce code que l'affichage de i, "out of ", len(folderlist).
Selon ce à quoi sert activity_count_user_folder , il est possible d'envisager donner un autre type ou non à cette variable ou à d'autres.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
print str(i) +  "out of " +  str(len(folderlist))
# est plus rapide que
print i, "out of ", len(folderlist)

mais en en restant là ce n'est pas ce qui va beaucoup changer les choses.

Un petit gain supplémentaire dans l'affichage peut ètre obtenu par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for i in xrange(0,l_f):
    if i%1000==0:
	print str(i) +  "out of " +  str(len(folderlist)

[Antoine_935]

D'ailleurs est-il nécéssaire de recalculer la longueur de folderlist à chaque itération ?

De plus, évite les recherches de membre (le point . ) dans les boucles gourmandes.
Tu peux stocker les deux fonctions append dans des variables locales, que tu utiliseras dans la boucle.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
folder_append = activity_count_user_folder.append
 
for i in ...:
    # le code
    folder_append(...)

[ledannois]

Je ne suis pas expert en python (enfin pas encore ;-) ) , mais je me demande pourquoi tu utilise le range pour ta boucle?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
for i in range(0,l_f):
	print i, "out of ", len(folderlist)
	cond1=(folder==folderlist[i])*z

Ne serait-il pas plus rapide de balayer directement la liste, car ta variable i, n'est utile que pour l'affichage du print.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
for folder_loop in folderlist:
	cond1=(folder==folder_loop)*z

Et l'affichage comme tout le monde le sais est un fonction lente et je ne vois pas trop l'intérêt d'afficher l'indice de la boucle à chaque parcours surtout pour un parcours de l_f : 800*3600 fois (presque 3 millions) juste pour de l'affichage.

Si l'affichage du print ne durait qu'1 petite milliseconde, tu prendrait 48 minutes rien que pour afficher l'indice de ta boucle!
Si le print met 5 ms tu perds presque 4 heures rien que pour l'affichage!

Toujours réfléchir à ce que l'on met dans un boucle.
Exemple :
rappeler la fonction len(folderlist) 3 millions de fois ne sert à rien car tu connait déjà le résultat : l_f.

[eyquem]

Bon, j'ai compris
1

d[:,0] signifie "la colonne 0" de l'array bidimensionnel d.
d[8,:] est la "8ième ligne" de l'array bidimensionnel d.

L' array d[0,:] est un iterable que map() peut donc recevoir en argument.
map(int,d[:,0]) fait des éléments de l'array des entiers.

Ce qui me perturbait, c'est qu'on applique array() au produit de map() alors que d paraissait être un array dès le départ.
Mais c'est parce que map() renvoie toujours une liste , donc pour retrouver un array, on est obligé d'appliquer array() sur le résultat de map(). L'array obtenu est une ligne puisque les éléments de map(int,d[:,0]) sont des entiers et non pas des sous-listes.

d[8,:] peut se représenter aussi par d[8] parce que 'éventuels ':' après le 8 sont sous-entendus. Pour une colonne la notation d[:,x] est obligée.
d[:,0] signifie donc "colonne 0 d'un array bidimensionnel" , mais s'il s'agit d'un array de dimension 3, la signification devient alors "les lignes 0 de tous les tableaux bidimensionnels qui sont en premier indice", ou "tous les tableaux bidimensionnels d'indice antépénultiéme égal à 0" pour un array de dimension 4, etc.

Cependant il est certain que d est un array bidimensionnel parce que si ce n'était pas le cas la fonction int() dans le map() ne pourrait pas s'appliquer à des éléments qui seraient des lignes ou de nature pire encore, donc non transformables en entier.



2
z = N.zeros_like(user)+1 crée un tableau rempli de zéros de même shape que le tableau user, c'est à dire en l'occurence un tableau-ligne , puis ajoute 1 ---> tableau-ligne rempli de 1: [1 1 1 1 1 .....]




3

user==userlist[5] est équivalent à
[user[0]==userlist[5] user[1]==userlist[5] user[2]==userlist[5] user[3]==userlist[5] user[4]==userlist[5] user[5]==userlist[5] user[6]==userlist[5]....]
Donc cond2 = user==userlist[5] sera un tableau rempli de False sauf aux positions où la valeur du tableau sera celle de la position 5 de la liste. Finalement c'est un moyen de trouver toutes les positions où se trouve un élément donné.
Par exemple si
userlist = [3 , 89 , 3 , 50 , 20 , 3 , 7]
et user = [3 89 3 50 20 3 7]
alors user==userlist[5] sera [ True False True False False True False]

C'est la même chose pour
cond1=(folder==folderlist[i])*z
sauf que le fait de multiplier par z transforme les True en 1 et le False en 0, ce qui permet un décompte.

user et folder sont issus de d,
donc ces tableaux-lignes ont la même longueur.
Je prends donc la même longueur pour un exemple avec
folderlist = ['8','1','22','13','46','52','22']
et folder = ['8' '1' '22' '13' '46' '52' '22']
on a (folder==folderlist[2])*z = [0 0 1 0 0 0 1]




4
Je pense que d est un array bidimensionnel du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
[[ 3  8]
 [89  1]
 [ 3 22]
 [50 13]
 [20 46]
 [ 3 52]
 [ 7 22]]

qui collationne les couples (utilisateur,numero de folder) chaque fois qu'un utilisateur consulte un folder. Dans la colonne 0, les numéros d'utilisateurs peuvent apparaître plusieurs fois, et de même pour les numéros de dossiers dans la colonne 1.
Pour éviter d'itérer sur des séquences contenant des éléments répétés, je pense que la fonction uniq() a pour mission de produire une liste sans doublons à partir d'un tableau qui en contient.
Je ne sais pas comment elle est codée. Perso j'utilise
li_sans_doublons = list(set(li))
quand la liste li n'est pas trop grande. Je n'ai pas testé la vitesse, mais à mon avis ça doit être foufroyant.



5
Bon, il semble donc que le code passe en revue les folders (itération sur i) et que
pour chaque folder i:

- il fait la somme des 1 qui apparraissent dans
(folder==folderlist[i])*z * (user==userlist[j])
c'est le nombre de fois que l'utilisateur j a utilisé le folder i

- il ajoute ce nombre à activity_count_user
Il n'y a donc dans activity_count_user d'un folder i que des nombres de consulations de ce dossier i, sans liaison avec les identités des utilisateurs mais ce nombre de consultation est identique au nombre d'utilisateurs.

Et finalement activity_count_user_folder liste les listes d'activités de tous les folders.



Bon, tout ceci, c'est évidemment si je ne me trompe pas sur la nature de d.
On en est réduit à reconstituer les questions, quand il n'y a pas assez de renseignements qui sont donnés.


Mais je donne les réponses aussi ! 6 - Pour ce qui est d'optimiser:



- j'ai testé la fonction sum() et je me suis aperçu que
[False False True False False False True].sum() donne 2.
Donc ce n'est pas la peine de se casser la tête avec z = N.zeros_like(user)+1 :
cond1 peut s'écrire simplement cond1=(folder==folderlist[i])
Les décomptes se feront sur des tableaux de booléens.





- ensuite,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
	for j in range(0,l_u):
		cond2 = (user==userlist[j])

c'est lourd. Remplacer par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
	for ut in userlist:
		cond2 = (user==ut)

- puis,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
	activity_count_user = []
	for ut in userlist:
		cond2 = (user==ut)
		activity_count_user.append((cond1*cond2).sum())

évite de mettre à chaque fois une valeur cond1*cond2 dans une variable cm




- et hop, encore une fois et plus de variable cond2 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
	activity_count_user = []
	for ut in userlist:
		activity_count_user.append((cond1*(user==ut)).sum())

- et on peut finalement mettre ça sous forme de list comprehension:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

activity_count_user = [ (cond1*(user==ut)).sum()  for  ut in userlist ]

- on fait la même chose pour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for i in range(0,l_f):
	print i, "out of ", len(folderlist)
	cond1=(folder==folderlist[i])*z

on remplace par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for fo in folderlist:
	print i, "out of ", len(folderlist)
	cond1=(folder==fo)

- et finalement encoe, pour éviter une affectation de valeur à une variable cond1, on fait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
activity_count_user_folder = []
for i,fo in enumerate(folderlist):
	print i, "out of ", l_f
	activity_count_user = [((folder==fo)*(user==ut)).sum() for ut in userlist ]
	activity_count_user_folder.append(activity_count_user)

- si on aime la concision et qu'on est prêt à se passer de l'impression de i, "out of ", l_f
on finit par deux list comprehension imbriquées:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
#
activity_count_user_folder = [ [ ((folder==fo)*(user==ut)).sum() for ut in userlist ] for fo in folderlist ]
#

- et miracle, si on aime la concision (un peu alambiquée quand même) ET qu'on tienne à son print i, "out of ", l_f , Python assure toujours :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def fprint(i):
    if i//100==0:
        print i, "out of ", l_f

activity_count_user_folder = []
[ (activity_count_user_folder.append( [ ((folder==fo)*(user==ut)).sum() for ut in userlist ] ) , fprint(i) )  for i,fo in enumerate(folderlist) ]
print activity_count_user_folder
#

En sommant directement sur des booléens, en itérant directement dans les listes et non plus les indices, en éliminant des affectations de variables, et en utilisant des listes comprehension, ça devrait s'accélérer notablement.
J'aimerais bien avoir un retour, vu le mal que je me suis donné pour comprendre la question.
#

[eyquem]

Salut ledannois,
Pas vu ton message avant de poster

Je ne suis pas expert en python (enfin pas encore ;-) )

dis-tu.
Je sens que ça va venir vite.

Le print est effectué pour chaque tour de i dans range(0,l_f), pas de j. Ça représente l_f = 3600 tours d'après les chiffres de dreda, pas 800 x 3600.
Me demande d'ailleurs s'il n'a pas inversé par erreur: il a plus de dossiers (3600) que d'utilisateurs (800) d'après ce qu'il donne, ça se peut, mais c'est 3600 dossiers qui me paraît énorme.
À part ça, je trouve tes remarques pertinentes.

[eyquem]

Je n’ai pas pu résister à l’envie de faire des tests de vitesse sur mes propositions de code.
Bien m’en a pris car je me suis aperçu que j’ai fait une erreur monumentale.


J’ai comparé les vitesses d’exécution :

- du code original de dreda: ori()

- le code précédent avec range() remplacés par des xrange(): xra()

- le code précédent sans l’utilisation de l’array z: xrsanz()

- le code de dreda sans z et en y remplaçant les range() par itérations directes dans les listes ( for fo in folder list au lieu de for i in xrange(l_f) et for ut in userlist...): fout()

- le code sans z, avec fo et ut, et une list comprehension: foutlic()

- le meme code mais en reportant l’expression de cond1 directement dans la list comprehension: foutlic2()



Les résultats dépendent des valeurs que l’on donne à len_d (la taille du tableau initial) évidemment, mais aussi des nombres d’utilisateurs nbru et de dossiers nbrf.

Plus nbru et nbrf sont grands (ce sont les nombres d'utilisateurs et de dossiers sans répétition, qui servent à fabriquer le tableau de départ ; leurs valeurs se retrouvent ensuite dans l_u et l_f du code de dreda), plus la différence entre “avec range()“ et “avec xrange()“ doit se faire sentir.

Plus nbrf est grand , plus l’influence de la non création de la variable intermédiaire cond1 se fait sentir. De même nbru pour cond2.

Si nbru et nbrf sont petits , on ne voit pas la différence de temps d’une fonction avec list comprehension.

L’optimisation recherchée est souhaitable surtout pour nbru,nbrf,len_d grands. Mais avec des grandes valeurs, cela peut mettre assez longtemps à tourner.

Pour obtenir le résultat suivant, j’ai fixé des valeurs suffisamment élevées pour avoir un effet , sans être trop grandes pour que ce ne soit pas trop long:

len_d=800, nbru=30, nbrf=150. J’ai pris nbrf grand pour bien avoir l’effet impliquant une list comprehension.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Test d'identite des resultats des differentes fonctions
ori(d)
xra(d)==ori(d) :		True
xrsanz(d)==ori(d) :		True
fout(d)==ori(d) :		True
foutlic(d)==ori(d) :		True
foutlic2(d)==ori(d) :		True
foutlicimbriq(d)==ori(d) :	True
len_d = 800    nbru = 30     nbrf = 150
0.9581 0.9648 0.9531 1.0451 0.9573 0.9866   moyenne 0.977 = m1
1.1359 0.9456 0.9484 0.8930 0.9142 1.0378   moyenne 0.979
1.0249 0.9399 1.0257 0.9641 0.8925 0.8786   moyenne 0.954
0.9998 0.8252 0.8532 0.8559 0.8955 1.0845   moyenne 0.919
0.9391 0.9177 1.0509 0.9700 0.8545 1.0025   moyenne 0.955
2.0795 2.3230 1.9688 2.1559 1.9946 2.1762   moyenne 2.116
2.1889 2.0547 2.1676 1.9707 2.1759 1.9786   moyenne 2.089

En vert, le code de reference = le code original ( ori() ) de dreda.

Ce résultat est éloquent.

1) D’abord on remarque que les modifications dont on pouvait attendre une influence notable sur le temps d’exécution ( xrange() au lieu de range(), itérations directes dans les listes, non utilisation de z, utilisation d’une list comprehension) ont en réalité un effet fort peu marqué.


2) Par contre, et honte sur moi de ne pas y avoir pensé, en remplaçant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
        cond1=(folder==fo)
        activity_count_user = [(cond1*(user==ut)).sum() for ut in userlist]

par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

        activity_count_user = [((folder==fo)*(user==ut)).sum() for ut in userlist]

on fait répéter au code le calcul de (folder==fo) plusieurs fois, et pas seulement nbrf fois mais nbrf x nbru fois ! (nbrf=l_f et nbru=l_u en fait).

Effet immédiat: doublement du temps d’exécution !



Ceci signifie que les opérations (folder==fo) et (user==ut) , même si elles sont sans doute plus rapides avec des tableaux que si on faisait le même genre de chose avec des listes, demandent un certain temps d’exécution.

Or , quelles que soient les finasseries techniques qu’on emploie pour l’algorithme décliné jusqu’à présent, chaque fois que le programme calcule une expression folder==folderlist[i] , il répète en réalité sur toutes les valeurs du tableau-ligne folder le test folder[k]==folderlist[i] qui a déjà été fait plusieurs fois:
pour un calcul donné, folderlist[i] est une constante et k parcours range(0,l_f) et
- soit à la position k , folder[k]==folderlist[i] est False: cela est le cas pour toutes les autres valeurs de folderlist[i] qui sont différentes de folder[k] à cette position k
- soit folder[k]==folderlist[i] est True, mais c’est ça a déjà été le cas , et ce le sera encore, quand la comparaison folder[k]==folderlist[i’] a été faite pour une autre valeur folderlist[i’] identique placée à une autre position i’

Donc le programme passe son temps a répété des comparaisons déjà faites parce qu’une valeur donnée folderlist[i] se trouve en plusieurs positions dans folder.


Évidemment.


Mais me disant cela, ça ma rappelé un problème similaire dans lequel quelqu’un voulait classer des mots en fondant le positionnement d’un mot donné dans le classement en fonction de la liste classée de ses nombres de co-occurences avec les autres mots.

http://www.developpez.net/forums/d65...-fichier-long/

Problème qui s’etait trouvé résolu vraiment comme il fallait quand dividee a présenté un algorithme basé sur une répartition préalable des données dans un dictionnaire.

J’ai donc retraité le problème de trouver activity_count_user_folder en faisant la même chose.

J'ai rassemblé avant comparaisons toutes les occurences d’utilisateurs (éléments de userlist ) pour un dossier donné (élément de folderlist) plutôt que de faire chercher au programme plusieurs fois la même chose pour un dossier donné et retester sur toute la longueur de folder à chaque fois.

Les codes correspondants se trouvent dans le message suivant: fonctions dicc() et dicclicompr()




En faisant varier len_d on met en évidence que la solution avec dictionnaire préalable est une optimisation d’autant meilleure que len_d est grand. Ça tombe bien.
J’ai pris nbru = 120, nbrf = 25 petit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
len_d = 50    nbru = 120    nbrf = 25
0.1064 0.1101 0.1089 0.1089 0.1100 0.1270   moyenne 0.111 = m1
0.0783 0.0790 0.0761 0.0912 0.0801 0.0787   moyenne 0.080 = 72.0 % de m1
0.0763 0.1112 0.1103 0.0770 0.1152 0.1263   moyenne 0.102 = 91.8 % de m1
 
En fait assez variable à ce niveau de len_d
len_d = 50    nbru = 120    nbrf = 25
0.1069 0.1208 0.1087 0.1109 0.1124 0.1153   moyenne 0.112 = m1
0.0833 0.0839 0.0837 0.1031 0.0801 0.0795   moyenne 0.085 = 76.1 % de m1
0.0773 0.1188 0.0778 0.0803 0.1112 0.1119   moyenne 0.096 = 85.5 % de m1
 
len_d = 50    nbru = 120    nbrf = 25
0.1336 0.1127 0.1242 0.1119 0.1141 0.1124   moyenne 0.118 = m1
0.0856 0.0857 0.0831 0.0852 0.1065 0.0814   moyenne 0.087 = 74.4 % de m1
0.0822 0.0789 0.0795 0.0940 0.0780 0.0804   moyenne 0.082 = 69.5 % de m1

En faisant varier len_d

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 100    nbru = 120    nbrf = 25
0.2767 0.2689 0.2771 0.2303 0.2075 0.2162   moyenne 0.246 = m1
0.1516 0.1518 0.1508 0.1531 0.1658 0.1467   moyenne 0.153 = 62.2 % de m1
0.1523 0.1425 0.1452 0.1484 0.1464 0.1644   moyenne 0.149 = 60.9 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 250    nbru = 120    nbrf = 25
0.3695 0.3576 0.3466 0.3755 0.3376 0.3561   moyenne 0.357 = m1
0.2375 0.2902 0.3286 0.2935 0.2425 0.2529   moyenne 0.274 = 76.7 % de m1
0.2198 0.2322 0.2240 0.2277 0.2471 0.2380   moyenne 0.231 = 64.8 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
len_d = 500    nbru = 120    nbrf = 25
0.4757 0.4651 0.4780 0.4631 0.4913 0.6376   moyenne 0.501 = m1
0.2767 0.3021 0.2896 0.2803 0.2768 0.3043   moyenne 0.288 = 57.4 % de m1
0.2743 0.2730 0.2691 0.2928 0.2616 0.3350   moyenne 0.284 = 56.6 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 800    nbru = 120    nbrf = 25
0.5810 0.6596 0.7365 0.6244 0.6038 0.6379   moyenne 0.640 = m1
0.2892 0.3164 0.2959 0.3308 0.3818 0.3769   moyenne 0.331 = 51.8 % de m1
0.2875 0.2808 0.2936 0.3163 0.2747 0.2902   moyenne 0.290 = 45.3 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
en_d = 1500    nbru = 120    nbrf = 25
0.9051 0.7170 0.6986 0.7199 0.7365 0.7241   moyenne 0.750 = m1
0.3365 0.3649 0.4487 0.3522 0.3330 0.3243   moyenne 0.359 = 47.9 % de m1
0.3138 0.3329 0.3138 0.3061 0.3736 0.4197   moyenne 0.343 = 45.7 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 3000    nbru = 120    nbrf = 25
1.1641 1.3668 1.2445 1.2437 1.1330 1.3798   moyenne 1.255 = m1
0.3949 0.3854 0.3845 0.4131 0.3829 0.5319   moyenne 0.415 = 33.0 % de m1
0.4371 0.3688 0.3946 0.3726 0.4036 0.4123   moyenne 0.398 = 31.7 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 6000    nbru = 120    nbrf = 25
2.3528 2.4230 2.3608 2.0365 2.5129 2.8524   moyenne 2.423 = m1
0.4939 0.5764 0.6181 0.5018 0.5156 0.5080   moyenne 0.535 = 22.1 % de m1
0.5042 0.6338 0.5524 0.5180 0.4863 0.4938   moyenne 0.531 = 21.9 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 10000    nbru = 120    nbrf = 25
5.2634 5.2788 5.4100 5.2780 5.4311 5.5281   moyenne 5.364 = m1
0.6575 0.6653 0.6757 0.8466 0.6691 0.6728   moyenne 0.697 = 13.0 % de m1
0.6618 0.6623 0.6715 0.6676 0.7884 0.7404   moyenne 0.698 = 13.0 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 20000    nbru = 120    nbrf = 25
9.9479 9.8372 9.6724 9.6241 9.5920 9.6631   moyenne 9.722 = m1
1.0558 1.0610 1.0772 1.1787 1.1665 1.0608   moyenne 1.100 = 11.3 % de m1
1.2586 1.0701 1.0689 1.0502 1.2395 1.0498   moyenne 1.122 = 11.5 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 40000    nbru = 120    nbrf = 25
19.203 19.371 19.374 19.307 19.339 18.979   moyenne 19.26 = m1
2.0777 1.9452 1.9510 2.2998 2.0109 1.8789   moyenne 2.027 = 10.5 % de m1
1.9731 2.0779 2.1044 2.0758 2.1433 2.0118   moyenne 2.064 = 10.7 % de m1

Et en faisant varier nbrf, c’est à dire le nombre de clés du dictionnaire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 6000    nbru = 120    nbrf = 25
2.3528 2.4230 2.3608 2.0365 2.5129 2.8524   moyenne 2.423 = m1
0.4939 0.5764 0.6181 0.5018 0.5156 0.5080   moyenne 0.535 = 22.1 % de m1
0.5042 0.6338 0.5524 0.5180 0.4863 0.4938   moyenne 0.531 = 21.9 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 6000    nbru = 120    nbrf = 40
3.4999 3.5185 3.2737 3.2876 3.2588 3.0084   moyenne 3.307 = m1
0.6626 0.6760 0.6647 0.6869 0.6452 0.7606   moyenne 0.682 = 20.6 % de m1
0.7323 0.6564 0.6577 0.6659 0.8209 0.6521   moyenne 0.697 = 21.0 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
len_d = 6000    nbru = 120     nbrf = 80
7.3460 7.9488 6.9285 6.6177 6.9553 6.6676   moyenne 7.077 = m1
1.0973 1.0919 1.3039 1.0835 1.1244 1.1954   moyenne 1.149 = 16.2 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 6000    nbru = 120     nbrf = 150
11.183 11.544 12.588 14.135 12.395 12.674   moyenne 12.42 = m1
1.8749 1.8667 2.0038 2.0208 1.9063 1.8598   moyenne 1.922 = 15.4 % de m1
1.9975 1.7868 2.0098 1.7773 1.9883 1.9831   moyenne 1.923 = 15.4 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
len_d = 6000    nbru = 120     nbrf = 500
40.527 39.154 38.836 38.024 40.854 41.081   moyenne 39.74 = m1
5.8614 6.0237 5.8663 5.8196 6.0164 6.0675   moyenne 5.942 = 14.9 % de m1
5.7376 5.6885 5.8088 5.6852 5.7073 5.6956   moyenne 5.720 = 14.3 % de m1

J’ai poussé un peu les feux sur les 3 parametres

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
len_d = 8000    nbru = 150     nbrf = 700
117.59 124.49 129.14 108.83 105.73 111.91   moyenne 116.2 = m1
10.426 10.480 10.920 10.676 10.861 10.722   moyenne 10.68 = 9.18 % de m1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
len_d = 9000    nbru = 180     nbrf = 900
174.54 186.80 171.36 166.03 177.81 178.84   moyenne 175.9 = m1
15.668 15.585 15.810 16.130 17.792 17.353   moyenne 16.39 = 9.31 % de m1

Je ne peux pas aller plus loin parce que j’ai un ordi peu performant



Mission accomplie: temps d'exécution divisé par 10


Je tire comme enseignement:

- les list comprehension, c’est séduisant parce que ça va plus vite et c’est plus concis, mais il ne faut pas se laisser entrainer à les utiliser sans mettre en balance les avantages et les inconvénients dans un code précis.. En voulant absolument être concis, comme je l’ai fait, on risque d’introduire ou d’augmenter un inconvénient lié aux modifications nécessaires pour utiliser une list compr.

- j’étais bien d’accord avec ledannois en le lisant, mais je le suis encore plus maintenant:

Toujours réfléchir à ce que l'on met dans un boucle.

- la qualité d’un programme réside dans son algorithme; ce n’est pas le choix de tel ou tel procédé technique qui fait la plus grande différence.

[eyquem]

J'ai oublié de mettre le code de comparaison

Les iterations sont menées par la fonction repeat(repet,iterat) du module timeit
repet : nombre de répétitions d’une mesure
iterat: nombre d’itération d’une fonction donnée pour faire une mesure

Ce code a tout ce qu'il faut pour tourner dès qu'il a été copié

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
from random import choice,randrange
from numpy import array,zeros_like,hstack
from timeit import Timer
 
 
len_d = 800
nbru = 30
nbrf = 150
zf = len(str(nbrf))
 
d = array([[choice([str(randrange(1,nbru+1))]),choice([str(randrange(1,nbrf+1)).zfill(zf)])] for i in xrange(len_d)])
 
user = array(map(int,d[:,0]))
print 'user :\n',user,'\n len(user) =',len(user),',',type(user),user.dtype
folder = d[:,1]
print 'folder :\n',folder,'\n len(folder) =',len(folder),',',type(folder)
z = zeros_like(user)+1
print 'z :',z,'\n len(z) =',len(z),',',type(z)
 
print
userlist = list(set(user))
userlist.sort()
l_u = len(userlist)
print 'userlist =',userlist
print 'l_u = len(userlist) =',len(userlist)
folderlist = list(set(folder))
folderlist.sort()
l_f = len(folderlist)
print 'folderlist =',folderlist
print 'l_f = len(folderlist) =',len(folderlist)
 
print
del user,folder,userlist,folderlist,l_u,l_f
 
###########################################################################################
 
# 1 ------ original ------------------------------------------------------
def ori(d):
    user = array(map(int,d[:,0]))
    folder = d[:,1]
    z = zeros_like(user)+1
    userlist = list(set(user))
    userlist.sort()
    folderlist = list(set(folder))
    folderlist.sort()
    l_u = len(userlist)
    l_f = len(folderlist)
    activity_count_user_folder = []
    for i in range(0,l_f):
        cond1=(folder==folderlist[i])*z
        activity_count_user = []
        for j in range(0,l_u):
            cond2 = (user==userlist[j])
            cm = cond1*cond2
            activity_count_user.append(cm.sum())
        activity_count_user_folder.append(activity_count_user)
    return activity_count_user_folder
 
 
# 2 -------- xrange ---------------------------------------------------
def xra(d):
    user = array(map(int,d[:,0]))
    folder = d[:,1]
    userlist = list(set(user))
    userlist.sort()
    folderlist = list(set(folder))
    folderlist.sort()
    l_u = len(userlist)
    l_f = len(folderlist)
    activity_count_user_folder = []
    for i in xrange(0,l_f):
        cond1=(folder==folderlist[i])*z
        activity_count_user = []
        for j in xrange(0,l_u):
            cond2 = (user==userlist[j])
            cm = cond1*cond2
            activity_count_user.append(cm.sum())
        activity_count_user_folder.append(activity_count_user)
    return activity_count_user_folder
 
 
# 3 -------- xrange , pas de z ---------------------------------------------------
def xrsanz(d):
    user = array(map(int,d[:,0]))
    folder = d[:,1]
    userlist = list(set(user))
    userlist.sort()
    folderlist = list(set(folder))
    folderlist.sort()
    l_u = len(userlist)
    l_f = len(folderlist)
    activity_count_user_folder = []
    for fo in folderlist:
        cond1=(folder==fo)
        activity_count_user = []
        for ut in userlist:
            activity_count_user.append( (cond1*(user==ut)).sum())
        activity_count_user_folder.append(activity_count_user)
    return activity_count_user_folder
 
 
# 4 -------- fo, ut ---------------------------------------------------
def fout(d):
    user = array(map(int,d[:,0]))
    folder = d[:,1]
    userlist = list(set(user))
    userlist.sort()
    folderlist = list(set(folder))
    folderlist.sort()
    l_u = len(userlist)
    l_f = len(folderlist)    
    activity_count_user_folder = []
    for fo in folderlist:
        cond1=(folder==fo)
        activity_count_user = []
        for ut in userlist:
            activity_count_user.append( (cond1*(user==ut)).sum() )
        activity_count_user_folder.append(activity_count_user)
    return activity_count_user_folder
 
 
 
# 5 -------- fo, ut, list comprehension ---------------------------------------------------
def foutlic(d):
    user = array(map(int,d[:,0]))
    folder = d[:,1]
    userlist = list(set(user))
    userlist.sort()
    folderlist = list(set(folder))
    folderlist.sort()
    l_u = len(userlist)
    l_f = len(folderlist)    
    activity_count_user_folder = []
    for fo in folderlist:
        cond1=(folder==fo)
        activity_count_user = [(cond1*(user==ut)).sum() for ut in userlist]
        activity_count_user_folder.append(activity_count_user)
    return activity_count_user_folder
 
 
# 6 -------- fo, ut, list comprehension ---------------------------------------------------
def foutlic2(d):
    user = array(map(int,d[:,0]))
    folder = d[:,1]
    userlist = list(set(user))
    userlist.sort()
    folderlist = list(set(folder))
    folderlist.sort()
    l_u = len(userlist)
    l_f = len(folderlist)    
    activity_count_user_folder = []
    for fo in folderlist:
        activity_count_user = [((folder==fo)*(user==ut)).sum() for ut in userlist]
        activity_count_user_folder.append(activity_count_user)
    return activity_count_user_folder
 
# 7 -------- fo, ut, list comprehension imbriquees ---------------------------------------------------
def foutlicimbriq(d):
    user = array(map(int,d[:,0]))
    folder = d[:,1]
    userlist = list(set(user))
    userlist.sort()
    folderlist = list(set(folder))
    folderlist.sort()
    l_u = len(userlist)
    l_f = len(folderlist)    
    activity_count_user_folder = [[((folder==fo)*(user==ut)).sum() for ut in userlist] for fo in folderlist]
    return activity_count_user_folder
 
 
# 8 -------- dictionnaire ---------------------------------------------------
def dicc(d):
    from collections import defaultdict
    foldic = defaultdict(list)
 
    user = array(map(int,d[:,0]))
    folder = d[:,1]
    userlist = list(set(user))
    userlist.sort()
    folderlist = list(set(folder))
    folderlist.sort()
    l_u = len(userlist)
    l_f = len(folderlist)
    for ln in d:
        foldic[ln[1]].append(int(ln[0]))
    activity_count_user_folder = []
    for fo in folderlist:
        activity_count_user = []
        ar = array(foldic[fo])
        for ut in userlist:
            activity_count_user.append( (ar==ut).sum())
        activity_count_user_folder.append(activity_count_user)
    return activity_count_user_folder
 
# 9 -------- dictionnaire list compr---------------------------------------------------
def dicclicompr(d):
    from collections import defaultdict
    foldic = defaultdict(list)
 
    user = array(map(int,d[:,0]))
    folder = d[:,1]
    userlist = list(set(user))
    userlist.sort()
    folderlist = list(set(folder))
    folderlist.sort()
    l_u = len(userlist)
    l_f = len(folderlist)
    [ foldic[ln[1]].append(int(ln[0])) for ln in d ]
    activity_count_user_folder = []
    for fo in folderlist:
        ar = array(foldic[fo])
        activity_count_user = [(ar==ut).sum() for ut in userlist ]
        activity_count_user_folder.append(activity_count_user)
    return activity_count_user_folder
 
def aff1(t):
    for u in t:
        print str(u)[0:6],
    print '  moyenne',str(sum(t)/len(t))[0:5],'= m1'
    return sum(t)/len(t)
 
def aff(t):
    for u in t:
        print str(u)[0:6],
    print '  moyenne',str(sum(t)/len(t))[0:5]
 
def affd(t,m):
    for u in t:
        print str(u)[0:6],
    print '  moyenne',str(sum(t)/len(t))[0:5],'=',str(100*sum(t)/len(t)/m)[0:4]+' % de m1'
 
 
print "Test d'identite des resultats des differentes fonctions"
print 'ori(d)'
print 'xra(d)==ori(d) :\t\t',ori(d)==xra(d)
print 'xrsanz(d)==ori(d) :\t\t',ori(d)==xrsanz(d)
print 'fout(d)==ori(d) :\t\t',ori(d)==fout(d)
print 'foutlic(d)==ori(d) :\t\t',ori(d)==foutlic(d)
print 'foutlic2(d)==ori(d) :\t\t',ori(d)==foutlic2(d)
print 'foutlicimbriq(d)==ori(d) :\t',ori(d)==foutlicimbriq(d)
print 'dicc(d)==ori(d) :\t\t',ori(d)==dicc(d)
print 'dicclicompr(d)==ori(d) :\t',ori(d)==dicclicompr(d)
print
 
 
 
 
repet = 6
iterat = 1
t1 = Timer('ori(d)','from __main__ import ori,d').repeat(repet,iterat)
t2 = Timer('xra(d)','from __main__ import xra,d').repeat(repet,iterat)
t3 = Timer('xrsanz(d)','from __main__ import xrsanz,d').repeat(repet,iterat)
t4 = Timer('fout(d)','from __main__ import fout,d').repeat(repet,iterat)
t5 = Timer('foutlic(d)','from __main__ import foutlic,d').repeat(repet,iterat)
t6 = Timer('foutlic2(d)','from __main__ import foutlic2,d').repeat(repet,iterat)
t7 = Timer('foutlicimbriq(d)','from __main__ import foutlicimbriq,d').repeat(repet,iterat)
t8 = Timer('dicc(d)','from __main__ import dicc,d').repeat(repet,iterat)
t9 = Timer('dicclicompr(d)','from __main__ import dicclicompr,d').repeat(repet,iterat)
 
 
print 'len_d =',len_d,'   nbru =',nbru,'    nbrf =',nbrf
m1 = aff1(t1)
aff(t2)
aff(t3)
aff(t4)
aff(t5)
aff(t6)
aff(t7)
affd(t8,m1)
affd(t9,m1)