关于计算强度、预测产生结果所需时间的问题

Question

简介

我已经编写了代码来为我提供一组“36 by q”格式的数字 (1<= q <= 36)，但要满足以下条件：

每行必须使用 1 到 36 之间的数字。
任何数字都不能在列中重复。

方法

第一行是随机生成的。将检查下一行中的每个数字是否符合上述条件。如果数字不满足给定条件之一，则不会在该特定行的特定位置再次选择它。如果它运行超出可接受的值，它将重新开始。

问题

与低 q 值（比如 15，计算时间不到一秒）不同，主要的 objective 是 q=36。自从它在我的电脑上开始运行 for q=36 已经超过 24 小时了。

问题

我可以使用我从较低 q 值获得的数据来预测它所需的时间吗？怎么样？
是否有更好的算法可以在更短的时间内执行此操作？
如何计算它需要的平均循环次数？（使用组合学或其他方式）。

Answer 1

图表 q 与时间
拟合一条曲线，
外推到 q = 36。

您可能还想绘制 q 与 log(time) 的关系图，因为这可能会给出更容易拟合的曲线。

Answer 2

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

通常，您应该能够根据输入确定您算法的运行时间。 Refer to big O notation.

如果我对你的问题的理解正确，你不应该花费小时来计算满足你的条件的 36x36 矩阵。很可能您陷入了无限循环或其他问题。你可以分享代码片段会更清楚。

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

好吧，我尝试按照您的描述进行操作，并且它在 O(q) 中有效（假设行数不变）。

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

基本上，我从第 i+q 行的 {1..36} 集合中选择随机数，然后将行旋转 q 次并分配这些旋转的行到下q行。这保证了你提到的两个条件。

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

我无法根据输入来计算计算时间（代码太复杂），那么拟合曲线似乎是正确的。

或者您可以创建一个 ML 模型，其中迭代作为数据，每次迭代的时间作为标签，并执行线性回归。但这在您的示例中似乎有些矫枉过正。

关于计算强度、预测产生结果所需时间的问题

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

python-3.x

algorithm

time

computation