Discussion :

[AJMont]

Hello à tous,

j'ai un soucis avec mon code que voici...

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
from sympy import *
from sympy.geometry import *
from sympy.plotting import *
from operator import itemgetter
import sys
from itertools import groupby
import itertools
from itertools import *
from sympy.matrices import *
import time
sys.setrecursionlimit(1000000)
 
avant = time.clock()
 
#p = [Point(45489772381, -736449623108), Point(45489772381, -736136770248), Point(455065875115, -736292552948), Point(454927507396, -736292552948), Point(454956086125, -736292552948), Point(454956086125, -736344480515), Point(454956086125, -736240625381), Point(454974435912, -736363148689), Point(454974435912, -736221957207), Point(454990378684, -736274957657), Point(454990378684, -736310148239)]
p = [Point(0,0), Point(8,0), Point(8,8), Point(5,2), Point(0,8), Point(12,7), Point(14,6)] 
#p = [Point(0,0), Point(8,0), Point(8,8)]
 
seg = []
tri = []
merge = []
perm = []
 
def f2(seq):
    checked = []
    for e in seq:
        if e not in checked:
            checked.append(e)
    return checked
 
combi_seg = list(itertools.combinations(range(0, len(p)), 2))
for result in combi_seg:
    (i, j) = result
    seg.extend([Segment(p[i] , p[j])])
 
combi_tria = list(itertools.combinations(range(0, len(p)), 3))
for result in combi_tria:
    (i, j, k) = result
    if Triangle(p[i], p[j], p[k]) == Segment(p[i], p[j]) or Triangle(p[i], p[j], p[k]) == Segment(p[i], p[k]) or Triangle(p[i], p[j], p[k]) == Segment(p[j], p[k]):
       print "Similar"
    else:
       tri.extend([Triangle(p[i], p[j], p[k])])
 
merge.extend(p)
merge.extend(seg)
merge.extend(tri)
 
def creatematrix(i,j):
     if (i == 0 and j == 0):
        return "ensemb"
     if (i == 0):
        return j
     if (j == 0):
        return i
     if (j<i):
        return "0"
     if i == j :
        return "1"
     for element in intersection(tri[i-1], tri[j-1]):
        if element not in merge:
           return "0"
     return "1"
 
Matrice = Matrix(len(tri)+1, len(tri)+1, creatematrix)
print Matrice
 
def NewMatr2(matr):
    mat = matr[:,:]
    OP = 0
    nbr = 0
    puiss = int(round(matr.shape[1]/4))
    power = -1
    group = []
    while puiss in range(0,matr.shape[1]):
          results = []
          power += 1
          if group == []:
             results.extend(list(itertools.combinations(range(1, matr.shape[1]), 2+puiss)))
          else:
             results.extend(list(itertools.combinations(group, 2+puiss)))
          counter1 = 1
          if results != []:
             mat = mat.col_insert(mat.shape[1], 2*ones(mat.shape[0],1))
             mat[0,mat.shape[1]-1] = "ind_" + str(puiss+2)
             group = []
             for result in results:
                OP += 1
                prod = []
                prod.extend(list(itertools.combinations(result, 2)))
                vall0 = 1
                for elem in prod:
                   (x, y) = elem
                   vall0 = vall0 * mat[x,y]
                print str(nbr) + " ensembles trouves sur " + str(OP) + " operations." 
                if (vall0 == 1):
                   if group == []:
                      group = list(result)
                   else:
                      group.extend(list(result))
                   vall1 = "t_" + str(result)
                   vall1 = vall1.replace("(", "") 
                   vall1 = vall1.replace(", ", "_")
                   vall1 = vall1.replace(")", "")
                   try:
                      mat[counter1,mat.shape[1]-1] = vall1
                   except LookupError:
                      mat = mat.row_insert(mat.shape[1], zeros(1,mat.shape[1]))
                      mat[counter1,mat.shape[1]-1] = vall1
                   counter1 += 1
                   nbr += 1
             group = f2(group)
             group = sorted(group)
             if mat[1,mat.shape[1]-1] == 2:
                 if (mat[1,mat.shape[1]-2] == 1) or (mat[1,mat.shape[1]-2] == 0):
                    mat.col_del(-1)
                    puiss = int(round(puiss/2))
                 else:
                    mat.col_del(-1)
                    return mat
             else:
                puiss += 1
    return mat
 
M2 = NewMatr2(Matrice)
 
print M2
print M2.col(-1)
 
print 'Time execution : ',time.clock() - avant

Bizarrement il part en overload memoire, alors que j'ai réduis les calculs...
Dans le code actuel il y a un while pour réenclencher la boucle alors que précédemment il y avait un for sur le même range. Avec le for pas d'overload, mais avec le while dès que je dépasse 7 points dans p j'ai un seg fault...

Quelqu'un peut m'expliquer d'où vient le problème et comment je peux le résoudre?
Merci!

[Sve@r]

Bonjour

Je suis désolé, ton truc a fait exploser mon PC, même avec tes seulement 7 points et même avec ton while.

Déjà (t'es en Python 2.X) tu devrais remplacer tes range par xrange. range te génère un tableau (autant d'éléments à traiter, autant d'éléments en mémoire) alors que xrange te donne un générateur (un seul élément est stocké).

Ensuite ben je sais pas trop. Tu fais de la combinatoire (donc de la factorielle) donc cela doit générer de la masse. Python est puissant mais quand la quantité de datas dépasse un seuil, il a ses limites.
Limites peut-être plus fortes par rapport à d'autres langages mais pour la bonne et simple raison qu'il existe des outils pour Python dédiés au traitement de grandes quantités de données. Ces outils ne sont pas forcément écrits en Python mais ils sont disponibles dans Python.
Tu as par exemple numpy, pytables, sqlite et bien d'autres encore (tape "Python big datas" dans google). A mon avis, tu devrais t'intéresser à certains. Moi par exemple je gère des items contenant 100000 enregistrements, avec des calculs différentiels (item2 - item1), ben je suis passé par sqlite (mini bdd de type sql) pour ça et j'en suis bien content mais peut-être qu'il y en a d'autres encore mieux...

[AJMont]

En effet il génère quelques data... avec 6 point il génère une matrice 20*20 de données puis traite les cas C(5,20), C(6,20)... etc jusqu'à ne plus trouver de solutions... en effet dans l'exemple il fait 156000 test avant de trouver la solution...

Je vais essayer avec xrange et m'informer un peu sur les big data

[AJMont]

J'ai essayé de convertir les fonction sympy en fonctions numpy (pour celles qui existent).
Premier point positif je divise par 5 le temps d'execution!

La seule partie que je n'arrive pas à implémenter, est la partie qui coince... la génération de la première matrice.

En sympy j'ai:

Code :

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

Matrice = Matrix(len(tri)+1, len(tri)+1, creatematrix)

que je converti en numpy:

Code :

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

1
2
 
Matnum = np.array(np.array(Matrice))

J'ai essayé ça:

Code :

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

Matnum = np.fromfunction(creatematrix, (len(tri)+1, len(tri)+1))

Mais il me renvoi:
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

Le génératrice en question est:

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
def creatematrix(i,j):
     if (i == 0):
        if j == 0:
           return "ensemb"
        else:
           return j
     if (j == 0):
        return i
     if (j<i):
        return "0"
     if i == j :
        return "1"
     for element in intersection(tri[i-1], tri[j-1]):
        if element not in merge:
           return "0"
     return "1"

Une idée?

[AJMont]

Je viens de repérer le crash.
Il survient lorsque je lui demande de calculer les combinaison binomiale...
Visiblement C(163,43), ca le fait cracher.. pourtant il n'y a que 94517631078824311679906690309862603919974 element dans cette liste....

Une idée pour passer outre?

[Sve@r]

Je viens de repérer le crash.
Il survient lorsque je lui demande de calculer les combinaison binomiale...
Visiblement C(163,43), ca le fait cracher.. pourtant il n'y a que 94 517 631 078 824 311 679 906 690 309 862 603 919 974 element dans cette liste....

Une idée pour passer outre?

Pour moi, C(43, 163) (généralement on met le plus grand terme en bas) donne 4 959 572 206 997 896 172 909 073 070 411 949 866 800.
Est-ce que ça crashe au calcul de cette valeur, ou bien est-ce que cette valeur va ensuite générer une liste d'autant d'éléments ?

Si ça crashe au calcul, alors c'est la faute à la façon dont C(n, p) est calculé. En effet, si la fonction utilise la formule brute, tu montes alors très haut (p!) pour redescendre (en divisant par n! puis par (p-n)!). Dans ce cas, tu peux réécrire la fonction en l'optimisant pour que les calculs ne montent jamais plus haut que la valeur finale

Exemple

Code python :

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

1
2
3
4
5
def comb(n, p):
    s=1
    for i in xrange(1, n+1): s=s*(i+p-n)/i
    return s
# comb()

Si ça crashe parce que le résultat servira à générer autant d'items (et la fin de ta phrase me laisse penser que c'est le cas), alors tu retombes dans le pb des big datas. Perso si ça m'arrivait je passerais par sqlite (dispo en natif) pour générer mes items...

[Clodion]

Je viens de repérer le crash.
Il survient lorsque je lui demande de calculer les combinaison binomiale...
Visiblement C(163,43), ca le fait cracher.. pourtant il n'y a que 94517631078824311679906690309862603919974 element dans cette liste....

Une idée pour passer outre?

Bonjour,
Heu...
Auriez-vous une idée de nombre que "94517631078824311679906690309862603919974 éléments" représente?
A ma connaissance, cela dépasse de très très loin la capacité de l'ensemble de tous les moyens de stockage présents sur Terre, anciens et actuels combinés (sauf grossière erreur, et même si, on est à 10^38).
Mais bon, je puis me tromper!!

Clodion