布尔型网格的随机指数

Question

比方说，我有一个N大小的方形booleangrid（二维数组）。其中一些值为true，部分值为false（未指定<true values>/<false values>比率）。我想随机选择一个指标(x, y)，以便grid[x][y]是true。如果我想要一个时间，有效的解决方案，我会做这样的事情（蟒蛇）：

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

但这是O(N^2)，这是绰绰有余了，再多说了，一个井字棋游戏的实施，但我猜测它会为大型内存消耗更多的内存。

如果我想要的东西，这不是消耗内存的，我会做：

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

你可以使用一个实现为具有对数深度的二叉树的字典。这需要O(N^2)空间，并允许您在O(log(N^2)) = O(logN)时间内搜索/删除。你可以例如使用Red-Black Tree。

的算法来找出一个随机值可能是：

t = tree.root 
if (t == null) 
    throw Exception("No more values"); 
// logarithmic serach 
while t.left != null or t.right != null 
    pick a random value k from range(0, 1, 2) 
    if (k == 0) 
     break; 
    if (k == 1) 
     if (t.left == null) 
      break 
     t = t.left 
    if (k == 2) 
     if (t.right == null) 
      break 
     t = t.right 

result = t.value 
// logarithmic delete 
tree.delete(t) 
return result 

当然，你可以代表(i, j)指数为i * N + j。

没有额外的内存，您无法跟踪对单元格状态的更改。在我看来，你不可能比O(N^2)更好（遍历数组）。

Answer 2

如果网格是静态的或变化不大，或者您有时间做一些预处理，则可以存储一个数组，该数组保存每行真值的数量，真值的总数以及列表非零行（所有这些如果电网发生变化，你可以不断更新）中：

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个真值的位置。

（你可以简单地选择一个非空行，然后再挑选来自该行的真实价值，但会造成不均匀的概率。）

对于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。