이 마작 알고리즘의 속도를 높이는 데 도움이됩니다.

Question

JavaScript에서 마작 관련 함수를 작성하고 있습니다.

다음은 테스트 사례 코드입니다.

• 0 요소는 손 각 유형의 타일의 개수 인
• 요소를 손으로 1 (34)이 타일의 총수 인 : 손 마작

  참고로, 배열로 표시되는

  • 제 craks 다음 점 후 BAMS 후 바람, 최종적 용

0

대기를 찾는 함수가 실제로 느리게 실행됩니다. 어떻게 속도를 높일 수 있습니까?

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

이됩니다 : 당신은 손 전체를 재구성하는 마음에 시간과 HC 주위와 곰 모두 통과

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

을, 당신은 두 개의 배열을 추가해야합니다. 그러나 이것은 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()에서 반복 할 때마다 전체 배열을 복사하지 말고 반복하기 전에 변경 사항을 추가하기 만하면 돌아올 때 추가 사항을 취소하기 만하면됩니다. waits() 함수.

둘째, well_formed()에서 손을 한 번 증분 변경 할 때마다 전체 배열을 다시 스캔합니다. 이는 본질적으로 비효율적 인 대신 "상태 카운터"를 유지할 수있는 기회를 찾아야합니다.

예를 들어, 얼마나 많은 쌍이 있는지 항상 알고 있다면 쉽게 단 pair()를 확인할 수 있습니다. 비 쌍으로 hand() 배열을 스캔하는 대신 배열 (또는 그와 관련된 컨텍스트)의 일부로 pairs_counter를 유지하면 카드를 손에 넣을 때마다 hand [i] = 2인지 확인합니다 페어 카운터가 3이면 카운트를 증가 시키면 감소합니다. 마찬가지로 카드를 제거 할 때 hand [j] = 2 인 경우 페어 카운터를 증가 시키지만 1이면 감소시킵니다.

이 전략을 사용할 수있는 곳이 많으며 실적에 큰 영향을 미칩니다.