如何最有效地计算俄罗斯方块堆栈的高度剖面？

Question

问题陈述

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

计算长度为 width 的数组 profile 使得 profile[i] == max_i 具有： max_i 是最大的 stack[max_i] 具有 i-第位设置。

我怎样才能以比下面更有效的方式实现这一点？

当前解决方案

目前，我会查看各列并分别检查每一位。

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

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

要点与基准代码

Find the code here.

当前结果：

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

Answer 1

我在 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);
}

如何最有效地计算俄罗斯方块堆栈的高度剖面？

How to compute the height profile of a Tetris stack most efficiently?

java

performance

scala

optimization

bit-manipulation

问题陈述

当前解决方案

典型值

要点与基准代码