如何最有效地计算俄罗斯方块堆栈的高度轮廓? [英] How to compute the height profile of a Tetris stack most efficiently?

问题描述

我们得到了一个长度为height的整数stack数组. width告诉我们，xs的每个条目中最多设置了width-最低位.

We're given an array of Integers stack of length height. The width tells us that at most the width-lowest bits in each entry of xs are set.

计算长度为width的数组profile，使得profile[i] == max_i带有max_i的位置最大，而stack[max_i]的第i位被设置.

Compute an array profile of length width such that profile[i] == max_i with: max_i is maximal with stack[max_i] having the i-th bit set.

我怎样才能比下面更有效地实现这一目标?

How can I achieve this in a more efficient way than below?

目前，我浏览各列并分别检查每一位.

Currently I go over the columns and check each bit separately.

以下显示了我当前在Scala中的实现.但是请随意用其他语言(Java，C，C ++)给出答案，因为我主要对算法部分感兴趣(针对当前CPU进行了优化).

The following shows my current implementation in Scala. But feel free to give answers in other languages (Java, C, C++), as I am mainly interested in the algorithmic part (optimized for current CPUs).

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

Typical values

• array size height is 22
• width width is 10

在此处查找代码.

当前结果:

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

推荐答案

我在C上编写了解决方案.希望您能够将算法移植到Java或Scala.

I wrote my solution on C. I hope, you will able port algorithm to Java or 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);
}

这篇关于如何最有效地计算俄罗斯方块堆栈的高度轮廓?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！