生成用C的所有元组 - 比嵌套循环更好的办法？

问题描述

我有一个数组双X [] 长度11和功能 F（双X []） 。我想找到的最小功能 F（）通过离散化。因此，对于给定的值 VAL1，将val2，...，VALN 我需要一个循环低谷{val_1，...，val_n} ^ 11 X的所有元组。我可以很容易地使用11个嵌套循环，但是这真的是最有效的，我可以做什么？

I have an array double x[] of length 11 and a function f(double x[]). I want to find the minimum of the function f() by discretization. So for given values val1, val2, ..., valn I need a loop trough all the tuples of x in {val_1, ..., val_n}^11. I could easily use 11 nested loops, but is this really the most efficient I could do?

编辑：
澄清的东西：函数f（）是在一个11维的集合来定义。我要评估的一个11维网格的顶点的功能。对于网格尺寸 ^ h ，数组的条目可能值 X [] 可能是 0 ， ^ h ， 2 * H ... N * ^ h = val_1，val_2，...，val_n。因此，在开始 F（val_1，val_1，...，val_1）应进行评估，然后 F（val_1，val_1，... val_1，val_2），......而在与 F（val_n，val_n，...，val_n）。我不关心顺序其实，但我不关心速度，因为有很多这样的元组。为precise，有n ^ 11个这样的元组。因此，对于N = 10 F（）已评估10 ^ 11倍。我的电脑可以评估 F（）每秒约5 * 10的6次方倍，因此对于n = 10 的F（评价）需要5个小时。这就是为什么我在寻找实现它最有效的方式。

To clarify things: the function f() is defined on an 11 dimensional set. I want to evaluate the function on the vertices of the an 11 dimensional grid. For a grid size h, possible values for the entries of the array x[] could be 0, h, 2*h, ..., n*h = val_1, val_2, ...,val_n . So in the beginning f(val_1, val_1, ..., val_1) should be evaluated, then f(val_1, val_1, ...,val_1, val_2), ... and in the and f(val_n, val_n, ..., val_n). I don't care about the order actually, but I do care about speed, because there are many such tuples. To be precise, there are n^11 such tuples. So for n=10 f() has to evaluated 10^11 times. My computer can evaluate f() approximately 5*10^6 times per second, so for n=10 the evaluation of f() takes 5 hours. That's why I'm searching for the most efficient way to implement it.

推荐答案

下面是伪code（不一定是语法，正确的C code）对于非递归的方法来遍历所有可能的元组：

Here is pseudocode (not necessarily syntactically-correct C code) for a non-recursive approach to iterate over all possible tuples:

const int vals[]        = { val1, val2, val3, ... };

int       x[NUM_DIMS]   = { vals[0], vals[0], ... };  // The current tuple
int       i[NUM_DIMS]   = { 0 };                      // Index of each element in x[]


while (1)
{
    f(x);  // Whatever

    // Update x (we increment i[] treated as a base-N number)
    int j;
    for (j = 0; j < NUM_DIMS; j++)
    {
        i[j]++;                          // Increment the current digit
        x[j] = vals[i[j]];               // Update (via mapping)
        if (i[j] < NUM_VALS) { break; }  // Has this digit wrapped?
        // We've caused a carry to the next digit position
        i[j] = 0;                        // Wrap
        x[j] = vals[0];                  // Update (via mapping)
    }
    if (j == NUM_DIMS) { break; }  // All digits wrapped, therefore game over
}

这篇关于生成用C的所有元组 - 比嵌套循环更好的办法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！