請幫我加快這個麻將算法

Question

我正在用JavaScript編寫一些麻將相關的功能。

下面是我在下面的代碼測試用例。

注意，麻將手被陣列表示，其中：

• 元件0 1至34爲磚的總數在手
• 元件是在手每種類型的瓦片的數目
  • 第一craks，然後點，然後BAMS，然後卷繞，最後小龍

查找等待的功能運行非常慢。我如何加快速度？

// 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

你有一個數組來保存手的內容，然後你要創建一個新的數組來保存每次的內容減去一組特定的瓷磚 - 在遞歸函數。而不是所有這些數組的創建，創建兩個數組 - 一個持有的手正在考慮之中，另一個持有你已經考慮過的手牌 - 並且只是通過它們。所以這個：

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; 

變成這樣：

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

你記住，重建整隻手同時通過H和HC左右，而熊，你需要添加兩個數組。但是，在考慮hnd是否完整時，這可能是正確的。

編輯：這裏是我的意思的詳細信息： 編輯：現在的工作，我希望......錯字的第一次嘗試。

// 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

要複製數組，請使用concat函數。

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

Answer 3

兩件事情在性能方面是錯誤的，我可以看到。

首先是David M已經注意到的：每次在well_formed（）中遞歸時都停止複製整個數組，只是在遞歸之前添加更改，然後在返回時退出添加，就像您在等待（）函數。

其次，在well_formed（）中，每當您對手執行單一增量更改時，都會重新掃描整個陣列。這本質上是低效的，相反，你應該尋找機會來保持「狀態計數器」。

例如，如果你總是知道你有多少對，你可以輕鬆地檢查only_pairs（）。不用掃描hand（）數組獲取任何非對，只要將一張牌添加到數組（或其相關聯的上下文）中，您就可以保留一個pairs_counter，然後檢查hand [i] = 2如果它是3，你就增加對數計數器，你減少它。同樣，當你移除一張牌時，如果hand [j] = 2，你增加對數計數器，但是如果它等於1，則減少它。

有許多地方你可以使用這個策略，它會對你的表現產生很大的影響。