Search code examples
python-3.xalgorithmtimecomputation

Question(s) regarding computational intensity, prediction of time required to produce a result

Introduction

I have written code to give me a set of numbers in '36 by q' format ( 1<= q <= 36), subject to following conditions:

  1. Each row must use numbers from 1 to 36.
  2. No number must repeat itself in a column.

Method

The first row is generated randomly. Each number in the coming row is checked for the above conditions. If a number fails to satisfy one of the given conditions, it doesn't get picked again fot that specific place in that specific row. If it runs out of acceptable values, it starts over again.

Problem

Unlike for low q values (say 15 which takes less than a second to compute), the main objective is q=36. It has been more than 24hrs since it started to run for q=36 on my PC.

Questions

  1. Can I predict the time required by it using the data I have from lower q values? How?

  2. Is there any better algorithm to perform this in less time?

  3. How can I calculate the average number of cycles it requires? (using combinatorics or otherwise).

Solution

  • Can I predict the time required by it using the data I have from lower q values? How?

    Usually, you should be able to determine the running time of your algorithm in terms of input. Refer to big O notation.

    If I understood your question correctly, you shouldn't spend hours computing a 36x36 matrix satisfying your conditions. Most probably you are stuck in the infinite loop or something. It would be more clear of you could share code snippet.

    Is there any better algorithm to perform this in less time?

    Well, I tried to do what you described and it works in O(q) (assuming that number of rows is constant).

    import random

def rotate(arr):
    return arr[-1:] + arr[:-1]

y = set([i for i in range(1, 37)])

n = 36
q = 36

res = []

i = 0
while i < n:
    x = []
    for j in range(q):
        if y:
            el = random.choice(list(y))
            y.remove(el)
            x.append(el)
    res.append(x)
for j in range(q-1):
    x = rotate(x)
    res.append(x)
    i += 1
i += 1

    Basically, I choose random numbers from the set of {1..36} for the i+q th row, then rotate the row q times and assigned these rotated rows to the next q rows. This guarantees both conditions you have mentioned.

    How can I calculate the average number of cycles it requires?( Using combinatorics or otherwise).

    I you cannot calculate the computation time in terms of input (code is too complex), then fitting to curve seems to be right.

    Or you could create an ML model with iterations as data and time for each iteration as label and perform linear regression. But that seems to be overkill in your example.