I have been staring at what I have produced for almost 5 hours and I still cannot see how and where to improve my implementation. I am implementing an Orthogonal sampling method according to the description of Orthogonal Sampling.
import numpy as np from numba import jit import random def Orthogonal(n): assert(np.sqrt(n) % 1 == 0),"Please insert an even number of samples" step = int(np.sqrt(n)) row_constraints = [ False for i in range(n) ] column_constraints = [ False for i in range(n) ] subbox_constraints = [ False for i in range(n)] result =  append = result.append def map_coord_to_box(x:int, y:int, step:int)->int: horz = int(np.floor(x/step)) vert = int(np.floor(y/step)) return vert * step + horz def remap_value(value:float, olb:int, oub:int, nlb:int, nub:int)->int: # https://stackoverflow.com/questions/1969240/mapping-a-range-of-values-to-another delta_old = abs(oub - olb) delta_new = abs(nub - nlb) ratio = (value - olb) / delta_old return ratio * delta_new + nlb while(all(subbox_constraints) == False): value = np.random.uniform(low=-2, high=2, size=2) x = int(np.floor(remap_value(value, -2, 2, 0, n))) y = int(np.floor(remap_value(value, -2, 2, 0, n))) if not (row_constraints[y] or column_constraints[x] or subbox_constraints[map_coord_to_box(x, y, step)]): #check_constraints(row_constraints, column_constraints, subbox_constraints, x, y, step): append(tuple(value)) row_constraints[y] = True column_constraints[x] = True subbox_constraints[map_coord_to_box(x, y, step)] = True return result
The problem is obvious when generating 100 samples it takes on average 300 ms, and I need something faster as I need to generate at least 10.000 samples. So I have not sat still. I tried to use jit for the sub-functions but it does not make it faster, but slower. I am aware that these function calls in python have a higher overhead. And so far on my own I thought using these functions are a way to approach the sampling method I want to implement. I have also asked a friend and he came up with a different approach which is on average a factor 100 faster than the above code. So he only prunes every row and columns and after randomly choosing those and stores the indices in to a list which later fills randomly.
def orthogonal_l(n): bs = int(np.sqrt(n)) result = [0 for i in range(n)] columns = [[i for i in range(bs)] for j in range(bs)] c = 0 for h in range(bs): rows = [i for i in range(bs)] for z in range(bs): w = random.choice(rows) x = random.choice(columns[w]) columns[w].remove(x) rows.remove(w) x += w * bs result[x] = c c += 1 return result, bs
How can I make use of pruning with my own code and is it wise to do so? If not, how can I improve the code, if so, where?