S'il vous plaît aidez-moi à accélérer cet algorithme de mahjong

Question

J'écris des fonctions liées au mahjong en JavaScript.

Voici ce que j'ai ci-dessous, avec le code pour les cas de test.

Notez que les mains mahjong sont représentées par des tableaux, avec:

• élément 0 étant le nombre total de carreaux dans la main
• éléments 1 à 34 étant le nombre de tuiles de chaque type dans la main
  • premier craks, puis des points, puis BAMS, puis serpente, et les dragons enfin

La fonction de recherche d'attente s'exécute très lentement. Comment puis-je l'accélérer?

// tiles are indexed as follows: 
// 1..9 = 1 crak .. 9 crak 
// 10..18 = 1 dot .. 9 dot 
// 19..27 = 1 bam .. 9 bam 
// 28..34 = east, south, west, north, white, green, red 

var wall = new Array(); 
set_up_wall(); 

function set_up_wall() { 
    for (var i=1; i<=34; i++) wall[i] = 4; 
    wall[0]=136; 
} 

// draw tile from wall 
function draw() { 
    var fudge = 1-(1e-14); 
    var n = Math.floor(Math.random()*wall[0]*fudge); 
    var i = 1; 
    while (n>=wall[i]) n-=wall[i++]; 
    wall[i]--; 
    wall[0]--; 
    return i; 
} 

// get number of a tile (or 0 if honor) 
// e.g. 8 bams = 8 
function tilenum(i) { 
    if (i>27) return 0; 
    if (i%9==0) return 9; 
    return i%9; 
} 

// get suit of a tile (or 0 if honor) 
function tilesuit(i) { 
    var eps = 1e-10; 
    return Math.ceil(i/9-eps)%4; 
} 

// is this a well-formed hand? 
function well_formed(h) { 
    // this function is recursive 
    if (h[0]==2) return only_pairs(h); 
    if (h[0]==14) { 
    if (only_pairs(h)) return true; 
    if (thirteen_orphans(h)) return true; 
    } 
    if (h[0]%3 != 2) return false; // wrong no. of tiles in hand 
    // now we start splitting up the hand 
    // look for three of a kind 
    for (var i=1; i<=34; i++) { 
    if (h[i]>=3) { 
     // create new hand minus the three of a kind 
     hh = new Array(); 
     for (var j=0; j<=34; j++) hh[j]=h[j]; 
     hh[0]-=3; 
     hh[i]-=3; 
     if (well_formed(hh)) return true; 
    } 
    } 
    // look for a run of three 
    for (var i=1; i<=25; i++) { 
    if (tilenum(i)<=7) { 
     if (h[i]>=1 && h[i+1]>=1 && h[i+2]>=1) { 
     // create new hand minus the run 
     hh = new Array(); 
     for (var j=0; j<=34; j++) hh[j]=h[j]; 
     hh[0]-=3; 
     hh[i]--; hh[i+1]--; hh[i+2]--; 
     if (well_formed(hh)) return true; 
     } 
    } 
    } 
    // if we reach here, we have exhausted all possibilities 
    return false; 
} 

// is this hand all pairs? 
function only_pairs(h) { 
    for (var i=1; i<=34; i++) if (h[i]==1 || h[i]>=3) return false; 
    return true; 
} 

// thirteen orphans? 
function thirteen_orphans(h) { 
    var d=0; 
    var c=new Array(14, 1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1); 
    for (var i=0; i<=34; i++) { 
    if (c[i]==0 && h[i]>0) return false; 
    if (h[i]!=c[i]) d++; 
    } 
    return d==1; 
} 

// this is inefficient 
function waits(h) { 
    var w=new Array(); 
    for (var j=0; j<=34; j++) w[j]=false; 
    if (h[0]%3!=1) return w; // wrong no. of tiles in hand 
    // so we don't destroy h 
    var hh = new Array(); 
    for (var j=0; j<=34; j++) hh[j]=h[j]; 
    for (var i=1; i<=34; i++) { 
    // add the tile we are trying to test 
    hh[0]++; hh[i]++; 
    if (hh[i]<5) { // exclude hands waiting for a nonexistent fifth tile 
     if (well_formed(hh)) { 
     w[0] = true; 
     w[i] = true; 
     } 
    } 
    hh[0]--; hh[i]--; 
    } 
    return w; 
} 

function tiles_to_string(t) { // strictly for testing purposes 
    var n; 
    var ss=""; 
    var s = "x 1c 2c 3c 4c 5c 6c 7c 8c 9c 1d 2d 3d 4d 5d 6d 7d 8d 9d "; 
    s += "1b 2b 3b 4b 5b 6b 7b 8b 9b Ew Sw Ww Nw Wd Gd Rd"; 
    s=s.split(" "); 
    for (var i=1; i<=34; i++) { 
    n=t[i]*1; // kludge 
    while (n--) ss+=(" "+s[i]); 
    } 
    return ss; 
} 

// tests 

var x; 
x = new Array(13, 0,0,0,0,0,1,2,2,2, 2,2,2,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0); 
document.write("Hand: "+tiles_to_string(x)+"<br />"); 
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />"); 
x = new Array(13, 1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1); 
document.write("Hand: "+tiles_to_string(x)+"<br />"); 
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />"); 
x = new Array(13, 0,0,0,0,0,0,0,0,0, 3,1,1,1,1,1,1,1,3, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0); 
document.write("Hand: "+tiles_to_string(x)+"<br />"); 
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />"); 
x = new Array(13, 4,0,0,3,3,3,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0); 
document.write("Hand: "+tiles_to_string(x)+"<br />"); 
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />"); 
x = new Array(13, 0,0,4,3,3,3,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0); 
document.write("Hand: "+tiles_to_string(x)+"<br />"); 
document.write("Waits: "+tiles_to_string(waits(x))+"<br /><br />"); 

Answer 1

Vous avez un tableau pour contenir le contenu de la main, et vous créez un nouveau tableau pour contenir le contenu moins un ensemble particulier de tuiles à chaque fois - dans une fonction récursive. Au lieu de toute cette création de tableau, créez deux tableaux - un pour tenir la main en considération, l'autre pour tenir les tuiles de la main que vous avez déjà considéré - et passez-les simplement tous les deux. Donc ceci:

hh = new Array(); 
for (var j=0; j<=34; j++) hh[j]=h[j]; 
hh[0]-=3; 
hh[i]-=3; 
if (well_formed(hh)) return true; 

devient ceci:

h[0]-=3; 
h[i]-=3; 
hc[0]+=3; 
hc[i]+=3; 
if (well_formed(h,hc)) return true; 

Vous passez deux heures et hc autour, et garder à l'esprit que, pour reconstruire toute la main, vous devez ajouter les deux tableaux. Mais cela peut arriver juste à la fin de considérer si le hnd est complet ou non.

EDIT: Voici ce que je veux dire plus en détail: EDIT: J'espère travailler maintenant ... faute de frappe dans la première tentative.

// is this a well-formed hand? 
function well_formed(h) { 
    hc = new Array(); 
    for (var i=0; i<=34; i++) hc[i]=0; 
    result = well_formed_recursive(h, hc); 
    for (var i=0; i<=34; i++) h[i]+=hc[i]; 
    return result; 
} 

function well_formed_recursive(h, hc) { 
    // this function is recursive 
    if (h[0]==2) return only_pairs(h); 
    if (h[0]==14) { 
    if (only_pairs(h)) return true; 
    if (thirteen_orphans(h)) return true; 
    } 
    if (h[0]%3 != 2) return false; // wrong no. of tiles in hand 
    // now we start splitting up the hand 
    // look for three of a kind 
    for (var i=1; i<=34; i++) { 
    if (h[i]>=3) { 
     h[0]-=3; 
     h[i]-=3; 
     hc[0]+=3; 
     hc[i]+=3; 
     if (well_formed_recursive(h,hc)) return true; 
    } 
    } 
    // look for a run of three 
    for (var i=1; i<=25; i++) { 
    if (tilenum(i)<=7) { 
     if (h[i]>=1 && h[i+1]>=1 && h[i+2]>=1) { 
     h[0]-=3; 
     h[i]--; h[i+1]--; h[i+2]--; 
     hc[0]+=3; 
     hc[i]++; hc[i+1]++; hc[i+2]++; 
     if (well_formed_recursive(h,hc)) return true; 
     } 
    } 
    } 
    // if we reach here, we have exhausted all possibilities 
    return false; 
} 

Answer 2

Pour dupliquer un tableau, utilisez la fonction concat.

var a=[1,2,3,4]; 
var b=a.concat(); 

Answer 3

Deux choses mal au niveau de la performance, que je peux voir. Tout d'abord, David M a déjà noté: arrêtez de copier l'ensemble de la matrice chaque fois que vous vous recourbez dans well_formed(), ajoutez simplement les changements avant de recurcir et retirez les ajouts quand vous revenez, comme vous l'avez fait dans votre Waits() fonction.

Ensuite, dans well_formed(), vous rescanz l'intégralité du tableau chaque fois que vous effectuez une seule modification incrémentielle dans la main. C'est intrinsèquement inefficace, à la place, vous devriez chercher des opportunités pour garder des "compteurs d'état" à la place. Par exemple, vous pouvez facilement vérifier only_pairs() si vous savez toujours combien de paires vous avez eues. Au lieu de scanner le tableau hand() pour les non-paires, vous gardez un pair_counter dans le tableau (ou son contexte associé), chaque fois que vous ajoutez une carte à la main [i], vous vérifiez si main [i] = 2 vous incrémentez le compteur de paires s'il est 3, vous le décrémentez. De même quand vous retirez une carte, si la main [j] = 2 vous incrémentez le compteur de paires, mais si elle est égale à 1, vous le décrémentez.

Il existe un certain nombre d'endroits où vous pouvez utiliser cette stratégie et cela aura un impact important sur vos performances.