algorithm - bool 网格的随机索引

Question

假设我有一个正方形 boolean grid (二维数组)大小为 N .一些值是 true有些是false (<true values> / <false values> 比率未指定)。我想随机选择一个指数 (x, y)这样grid[x][y]是true .如果我想要一个省时的解决方案，我会做这样的事情(Python):

x, y = random.choice([(x, y) for x in range(N) for y in range(N) if grid[x][y]])

但这是 O(N^2) ，这对于 tic-tac-toe 游戏的实现来说已经绰绰有余了，但我猜想对于大 N 来说它会消耗更多的内存。 .

如果我想要一些不占用内存的东西，我会这样做:

x, y = 0, 0
t = N - 1
while True:
    x = random.randint(0, t)
    y = random.randint(0, t)
    if grid[x][y]:
        break

但问题是，如果我有一个大小为 10^4 的网格而且只有一两个true中的值，可能需要永远“猜测”哪个指数是我感兴趣的指数。我应该如何使这个算法最优？

Answer 1

如果网格是静态的或变化不大，或者您有时间进行一些预处理，您可以存储一个数组，其中包含每行真值的数量、真值的总数以及一个列表非零行(如果网格发生变化，您可以随时更新所有这些行):

grid        per row

0 1 0 0 1 0    2
0 0 0 0 0 0    0
0 0 1 0 0 0    1
0 0 0 0 1 0    1
0 0 0 0 0 0    0
1 0 1 1 1 0    4
       total = 8

non-zero rows: [0, 2, 3, 5]

要选择一个随机索引，选择一个随机值 r 直到真值的总数，用每个非零行的真值数遍历数组，将它们相加直到你知道 r-第 r 个真值在中，然后遍历该行以找到第 r 个真值的位置。

(您可以简单地先选择一个非空行，然后从该行中选择一个真值，但这会产生不均匀的概率。)

对于 N×N 大小的网格，预处理将花费 N×N 时间和 2×N 空间，但最坏情况下的查找时间为 N。在实践中，使用下面的 JavaScript 代码示例，预处理和查找时间(以毫秒为单位)的顺序为:

  grid size      pre-processing    look-up  
10000 x 10000        5000            2.2  
 1000 x  1000          50            0.22  
  100 x   100           0.5          0.022  

如您所见，对于大型网格，查找比预处理快 2000 多倍，因此如果您需要在同一(或略微改变的)网格上随机选择多个位置，预处理会很有道理。

function random2D(grid) {
    this.grid = grid;
    this.num = this.grid.map(function(elem) {         // number of true values per row
        return elem.reduce(function(sum, val) {
            return sum + (val ? 1 : 0);
        }, 0);
    });
    this.total = this.num.reduce(function(sum, val) { // total number of true values
        return sum + val;
    }, 0);

    this.update = function(row, col, val) {           // change value in grid
        var prev = this.grid[row][col];
        this.grid[row][col] = val;
        if (prev ^ val) {
            this.num[row] += val ? 1 : -1;
            this.total += val ? 1 : -1;
        }
    }

    this.select = function() {                        // select random index
        var row = 0, col = 0;
        var rnd = Math.floor(Math.random() * this.total) + 1;
        while (rnd > this.num[row]) {                 // find row
            rnd -= this.num[row++];
        }
        while (rnd) {                                 // find column
            if (this.grid[row][col]) --rnd;
            if (rnd) ++col;
        }
        return {x: col, y: row};
    }
}

var grid = [], size = 1000, prob = 0.01;              // generate test data
for (var i = 0; i < size; i++) {
    grid[i] = [];
    for (var j = 0; j < size; j++) {
        grid[i][j] = Math.random() < prob;
    }
}
var rnd = new random2D(grid);                         // pre-process grid
document.write(JSON.stringify(rnd.select()));         // get random index

保留包含至少一个真值的行的列表只对非常稀疏填充的网格有意义，其中许多行不包含真值，所以我没有在代码示例中实现它。如果您实现它，非常稀疏数组的查找时间将减少到不到 1µs。