Is there a way to increase the efficiency of this algorithm that generates random x-y coordinates?
I’m working on an algorithm that randomly plots objects on a large image. Here is the workflow of what I currently have.
- I define a space that represents the dimensions of the image and initiate an empty array (restrictList)
- Using the genLoc function, I randomly pick a point (x,y). restrictList is empty when the first point is picked.
- I then calculate all points that will be occupied by the object. These points are added to the array(restrictList)
- I then call genLoc again, to pick another random (x,y). If (x,y) exists is restrictList, the function calls itself again.
- This will continue until we pick a random point that is not in restrict list.
The problem is as follows, as more objects are plotted, the size of the array – restrictList increases. With each iteration, it takes longer to pick a valid random point. The biggest flaw that I can see here is that I’m wasting processing power by repeatedly picking a random coordinate from the image space. One alternative that I tried was using an array – [x for x in AllPossiblePoints if x not in restrictList] and picking a random index. This takes even longer because the array AllPossiblePoints is very large. I think I need a way to make sure that the (x,y) coordinates that are in restrictList, do not get randomly generated in the first place.
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 
REVISED
This solution will require you to generate all possible coordinates in advance. It uses sets and set logic to remove possibilities as they are used. random.sample is used to choose a point from the possibles. My mre is contrived to illustrate that – (everything is linear).
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)) The time complexity of s.difference_update(t) is O(len(t)).
This solves the problem of hunting for a random coordinate that isn’t already used.
Cannot assess the cost of creating all the coordinates up front. If it is too costly then probably have to revert to hunting for a usable coordinate. Using a set to hold all the restricted points will reduce the time for the membership testing.
