テトリススタックの高さプロファイルを最も効率的に計算するにはどうすればよいですか？

debugcn 投稿 Dev

ziggystar

問題文

stack長さの整数の配列が与えられますheight。widthほとんどのことを教えてくれるwidthの各エントリの-lowestビットがxsセットされています。

with：が-番目のビットを設定して最大になるようなprofile長さの配列を計算します。widthprofile[i] == max_imax_istack[max_i]i

以下よりも効率的な方法でこれを達成するにはどうすればよいですか？

現在の解決策

現在、列を調べて、各ビットを個別にチェックしています。

以下は、Scalaでの現在の実装を示しています。しかし、私は主にアルゴリズムの部分（現在のCPU用に最適化されている）に興味があるので、他の言語（Java、C、C ++）で自由に答えてください。

Scalaコード：

def tetrisProfile(stack: Array[Int]): Array[Int] = {
  var col = 0
  val profile = new Array[Int](width)
  while(col < width){
    var row = 0
    var max = 0
    while(row < height){
      if(((stack(row) >> col) & 1) == 1)
        max = row + 1
      row += 1
    }
    profile(col) = max
    col += 1
  }
  return profile
}

典型的な値

配列サイズheightは22です
幅widthは10です

ベンチマークコードの要点

ここでコードを見つけてください。

現在の結果：

original:    2.070s,        2.044s,        1.973s,        1.973s,        1.973s
maxihatop:   0.492s,        0.483s,        0.490s,        0.490s,        0.489s

olegarch

私はCでソリューションを作成しました。アルゴリズムをJavaまたはScalaに移植できることを願っています。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define WIDTH  10
#define HEIGHT 22

// Convert (1 << n) to n for n == 0-10
static char bit2ndx[11] = {-1, 0, 1, 8, 2, 4, 9, 7, 3, 6, 5};
int *tetrisProfile(int *input) {
  int row;
  // allocate memory and set everything to -1 - default rc value,
  // returned if no any result for this column
  int *rc = (int *)malloc(WIDTH * sizeof(int));
  memset(rc, ~0, WIDTH * sizeof(int));
  // create bitset for columns for check
  int testbits = (1 << WIDTH) - 1;
  // Iterate rows from up to bottom, and while exist columns for check
  for(row = HEIGHT - 1; row >= 0 && testbits != 0; row--) {
    int rowtestbits = testbits & input[row];
    while(rowtestbits != 0) {
      // extract lowest bit_1 from bitset rowtestbits
      int curbit = rowtestbits & -rowtestbits;
      rc[bit2ndx[curbit % 11]] = row;
      rowtestbits ^= curbit;
      testbits    ^= curbit;
    }
  }
  return rc;
}

int stack[HEIGHT] = {0x01, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x100, 0x200,
                       0,   0,   0,   0,    0,    0,    0,    0,     0,     0,
                       0,   0};


main(int argc, char **argv) {
  int i;
  int *ret = tetrisProfile(stack);
  for(i = 0; i < WIDTH; i++)
      printf("ret[%02d]=%d\n", i, ret[i]);
  free(ret);
}