Случайный показатель булевой сетки

Question

Предположим, у меня есть квадрат booleangrid (2D-массив) размером 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), что более чем достаточно для, скажем, реализация крестики-нолики игра, но я предполагаю, что это принесет гораздо больше памяти для больших 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

Вы можете использовать словарь, реализованный как двоичное дерево с логарифмической глубиной. Это занимает 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 мкс.