Есть ли способ повысить эффективность этого алгоритма, который генерирует случайные координаты xy?

Question

Я работаю над алгоритмом, который случайным образом отображает объекты на большом изображении. Вот рабочий процесс того, что у меня сейчас есть.

1. Я определяю пространство, которое представляет размеры изображения, и инициирую пустой массив (restrictList)
2. Используя genLo c функции, я случайным образом выбираю точку (x, y). restrictList пуст, когда выбирается первая точка.
3. Затем я вычисляю все точки, которые будут заняты объектом. Эти точки добавляются в массив (restrictList)
4. Затем я снова вызываю genLo c, чтобы выбрать другой случайный (x, y). Если (x, y) существует в restrictList, функция вызывает себя снова.
5. Это будет продолжаться до тех пор, пока мы не выберем случайную точку, которой нет в списке ограничений.

Проблема в следующим образом, по мере того, как отображается больше объектов, размер массива restrictList увеличивается. С каждой итерацией выбор действительной случайной точки занимает больше времени. Самый большой недостаток, который я здесь вижу, заключается в том, что я зря трачу вычислительную мощность, многократно выбирая случайную координату из пространства изображения. Одной из альтернатив, которые я пробовал, было использование массива - [x for x in AllPossiblePoints if x not in restrictList] и выбор случайного индекса. Это занимает еще больше времени, потому что массив AllPossiblePoints очень большой. Я думаю, мне нужен способ убедиться, что координаты (x, y), которые находятся в restrictList, не генерируются случайным образом в первую очередь.

def genLoc(x,y, restrictList):

Valx = randint(0, x)
Valy = randint(0, y)

point = (Valx, Valy)
if point in restrictList:
    return genLoc(dimx, dimy, restrictList)

elif point not in restrictList:
    return point

Answer 1

ПЕРЕСМОТРЕНО

Это решение потребует от вас заранее сгенерировать все возможные координаты. Он использует наборы и set logi c для удаления возможностей по мере их использования. random.sample используется для выбора точки из возможных. Моя МРЭ придумана, чтобы проиллюстрировать это - (все линейно ).

import random

# fake function that identifies
# unusable points after placing an object
def calc_objectspace(point,obj=None):
    objdims = range(-5,5)
    # linear all the same size
    objspace = set(point+n for n in range(-5,5))
    objspace.add(point)    # as needed
    return objspace

# make all the points as a set
allthestuff = set(range(10000))

# iterate over the objects getting placed
for obj in range(10):
    # random.choice won't work with a set
    point = random.sample(allthestuff,1)[0]
    # determine occupied points
    obj_space = calc_objectspace(point)
    # reduce the possible points
    allthestuff.difference_update(obj_space)
    print(len(allthestuff))

Временная сложность s.difference_update(t) равна O (len (t)).

Это решает проблему поиска случайной координаты, которая еще не используется.

Невозможно оценить Стоимость создания всех координат аванс . Если это слишком дорого, вероятно, придется вернуться к поиску пригодных для использования координат. Использование набора для удержания всех ограниченных очков сократит время тестирования членства.