CODEWITHSUNDEEP
pythonarraysalgorithmspace-complexity
Saad Malik
Saad Malik

Reputation: 111

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.

  1. I define a space that represents the dimensions of the image and initiate an empty array (restrictList)
  2. Using the genLoc function, I randomly pick a point (x,y). restrictList is empty when the first point is picked.
  3. I then calculate all points that will be occupied by the object. These points are added to the array(restrictList)
  4. I then call genLoc again, to pick another random (x,y). If (x,y) exists is restrictList, the function calls itself again.
  5. 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

Upvotes: 1

Views: 143

Answers (1)

wwii
wwii

Reputation: 23753

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.

Upvotes: 1

Related Questions