How could I reduce the time complexity of this nested loop?

Question

I'm in the process of learning to optimize code and implement more data structures and algorithms in my programs, however I'm experiencing difficulties with this code block.

My primary goal is to reduce this from a O(n**2) time complexity mainly not using a nested loop.

numArray = np.array([[20, 12, 10, 8, 6, 4], [10, 10, 10, 10, 10, 10]], dtype=int)
rolls = [[] for i in range(len(numArray[0]))]

for i in range(len(numArray[0])):
    for j in range(numArray[1, i]):
        rolls[i].append(random.randint(1, numArray[0, i]))

The code is supposed to generate x amount of random integers (where x is index i of the second numArray subarray, e.g. 10) between 1 and index i of the first numArray subarray (e.g. 20).

Then repeat this for each index in the first numArray subarray. (In the whole dice program numArray subarrays are user generated integers, but I assigned fixed numbers to it for simplicities sake while optimizing.)

Can you provide how the desired output and shape should look like. (Maybe shrink it down even more for here) — Daraan
– Daraan, Commented Oct 13, 2022 at 13:31

LTJ · Accepted Answer · 2022-10-13 13:36:49Z

1

You could use np.random.randint since you're already importing numpy. It accepts a size argument to produce multiple random values in one go.

rolls = [list(np.random.randint(1, numArray[0][idx], val)) for idx, val in enumerate(numArray[1])]

This of course assumes that both lists in numArray are the same length, but should get you somewhere at least.

answered Oct 13, 2022 at 13:36

LTJ

1,2706 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How could I reduce the time complexity of this nested loop?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related