1

我正在用 JavaScript 写一些麻将相关的函数。

这是我下面的内容，带有测试用例的代码。

请注意，麻将手由数组表示，其中：

  • 元素 0 是手中牌的总数
  • 元素 1 到 34 是手中每种类型的牌的数量
    • 首先是craks，然后是dots，然后是bams，然后是winds，最后是dragons

查找等待的功能运行非常缓慢。我怎样才能加快速度？

// 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 />");
4

3 回答 3

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;
}
于 2009-12-18T15:47:18.383 回答
0

要复制数组，请使用 concat 函数。

var a=[1,2,3,4];
var b=a.concat();
于 2009-12-18T15:57:12.993 回答
0

我可以看到两件事在性能方面是错误的。

首先是 David M 已经注意到的：每次在 well_formed() 中递归时停止复制整个数组，只需在递归之前添加更改并在返回时退出添加，就像在 waits() 函数中所做的那样.

其次，在 well_formed() 中，每次对手进行一次增量更改时，您都会重新扫描整个数组。这本质上是低效的，相反，您应该寻找机会保留“状态计数器”。

例如，如果你总是知道你有多少对，你可以很容易地检查 only_pairs()。无需扫描 hand() 数组以查找任何非对子，而是将 pairs_counter 作为数组（或其关联上下文）的一部分，每当您将卡片添加到 hand[i] 时，然后检查是否 hand[i]=2如果它是 3，你增加对计数器，你减少它。同样，当你移除一张牌时，如果 hand[j] = 2，你会增加对数计数器，但如果它等于 1，你会减少它。

您可以在许多地方采用此策略，这将对您的绩效产生重大影响。

于 2009-12-18T16:28:46.487 回答