retouche complexité

[canny.git] / stc / exp / python / stc_r.py

diff --git a/stc/exp/python/stc_r.py b/stc/exp/python/stc_r.py
index 854c7807b277ff0f4bda3649c3ed81369efbc2bc..615fa5573c55d7fa7d1a43e45d0178afecf11c8b 100644 (file)
--- a/stc/exp/python/stc_r.py
+++ b/stc/exp/python/stc_r.py
@@ -5,6 +5,7 @@ import gc
 
 infinity = 100000000000
 
+DEBUG = True
 
 
 # forward part
@@ -64,7 +65,8 @@ def forward(H_hat,x,message,lnm,rho):
     i=0
     while i < nbblock: # pour chaque bit du message
         for j in xrange(w):   # pour chaque colonne de H_hat
-            #print indx, "en entrant",wght
+            if DEBUG :
+                print indx, "en entrant",wght
             k = 0
             while k < int(2**h): # pour chaque ligne de H
                 w0 = wght[k] + x[indx]*rho[indx]
@@ -78,13 +80,17 @@ def forward(H_hat,x,message,lnm,rho):
                 k +=1 
             indx +=1
             wght = [t for t in newwght]
-            #print " apres calcul",wght
+            if DEBUG :
+                print " apres calcul",wght
 
         for j in xrange(int(2**(h-1))):   # pour chaque colonne de H
             wght[j] = wght[2*j + message[indm]]
         wght = wght[:int(pow(2,h-1))] + [infinity for _ in xrange(int(pow(2,h)-pow(2,h-1)))]
         indm +=1
         i +=1
+        if DEBUG :
+            print "pruning",wght
+        
     start = np.argmin(wght)
     return (start,path)
 
@@ -116,7 +122,6 @@ def backward(start,H_hat,x,message,lnm,path):
 
 
 def trouve_H_hat(n,m,h):
-    assert h ==7 
     alpha = float(n)/m
     assert alpha >= 2 
     index = min(int(alpha),9)
@@ -133,9 +138,10 @@ def trouve_H_hat(n,m,h):
     return(mat, index*m)
 
 
-def stc(x,rho,message):
+def stc(x,rho,message,hhat=-1):
     lnm = len(message)
-    (mat,taille_suff) = trouve_H_hat(len(x),len(message),7)
+    (mat,taille_suff) = trouve_H_hat(len(x),lnm,7) \
+        if hhat == -1 else (hhat,len(hhat)*lnm)
     x_b = x[:taille_suff]
     (start,path) = forward(mat,x_b,message,lnm,rho)
     return (x_b,backward(start,mat,x_b,message,lnm,path),mat)
@@ -217,11 +223,11 @@ message = [randint(0,1) for _ in xrange(26000)]
 print max([message[l]-message2[l] for l in xrange(len(message))])
 print equiv(message,message2)
 
-"""
+
 count = 0
 
-while count < 100 and eval :
-    lx = randint(500,1000)
+while count < 1000 and eval :
+    lx = randint(5000,10000)
     x = [randint(0,1) for _ in xrange(lx)]
     rho = [randint(1,9) for _ in xrange(lx)]
 
@@ -239,3 +245,9 @@ while count < 100 and eval :
                      
 print count
 
+"""
+x = [0, 1, 0, 1, 1, 1, 0, 0]
+rho = [4, 2, 5, 4, 9, 8, 7, 6]
+message = [1,1,0,1]
+
+print stc(x,rho,message,[1,3])