如何最有效地计算一个俄罗斯方块堆叠的高度轮廓？(How to compute the height

问题陈述

我们给出一个整数数组stack长度的height 。该width告诉我们，最多的width -lowest中的每个条目位xs设置。

计算阵列profile长度的width ，使得profile[i] == max_i用： max_i是最大与stack[max_i]具有i个位组。

我怎么能比下面更有效的方式实现这一目标？

目前的解决方案

目前，我去了所有的专栏，并分别检查各个位。

下面显示了我在斯卡拉当前的实现。但随时给其他语言（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

吉斯特与基准码

在这里找到的代码。

目前的结果：

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

我写了我的解决方案上C.我希望，你将能够端口算法，Java或斯卡拉。

#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);
}