Генерировать все кортежи с C - лучший способ, чем вложенные циклы? - PullRequest
Новая
       28

Генерировать все кортежи с C - лучший способ, чем вложенные циклы?

2 голосов
/ 10 января 2012

У меня есть массив double x[] длины 11 и функция f(double x[]).Я хочу найти минимум функции f() путем дискретизации.Поэтому для заданных значений val1, val2, ..., valn мне нужен цикл через все кортежи x в {val_1, ..., val_n} ^ 11.Я мог бы легко использовать 11 вложенных циклов, но действительно ли это самый эффективный из всех, что я мог сделать?

Редактировать: Чтобы прояснить ситуацию: функция 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).На самом деле меня не волнует порядок, но меня волнует скорость, потому что таких кортежей много.Чтобы быть точным, есть n ^ 11 таких кортежей.Так что для n = 10 f() приходится оценивать 10 ^ 11 раз.Мой компьютер может оценивать f() примерно 5 * 10 ^ 6 раз в секунду, поэтому для n = 10 оценка f() занимает 5 часов.Вот почему я ищу наиболее эффективный способ его реализации.

Ответы [ 3 ]

6 голосов
/ 10 января 2012

Вот псевдокод (необязательно синтаксически правильный код C) для нерекурсивного подхода для перебора всех возможных кортежей: 

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
}
3 голосов
/ 10 января 2012

Что нужно сделать, если число необходимых вам циклов слишком велико или неизвестно во время компиляции, это использовать рекурсию. 

void check(double *x, int count) {
     // Check the tuple
}
void process(double *x, double *tuple, int count, int pos) {
    if (pos == count) {
        check(tuple, count);
    } else {
        for (int i = 0 ; i != count ; i++) {
            tuple[pos] = x[i];
            process(x, tuple, count, pos+1);
        }
    }
}
int main() {
    double x[11] = {1,2,3...}, tuple[11];
    process(x, tuple, 11, 0);        
    return 0;
}
1 голос
/ 11 января 2012

Возможно, вы захотите уменьшить нагрузку на кэш процессора. Поэтому, возможно, если N в val_N мало, и вы представляете его как N вместо N*h, как предполагает @OliCharlesworth, вы можете использовать меньший тип (например, unsigned char).

Кроме того, цикл может быть уменьшен до: 

static inline int incx(uint8_t *x, unsigned int len) {
    ++*x;

    // compute any overflow
    unsigned int i = 0;
    while (x[i] >= len && i < len) {
        x[i++] -= len;
        ++x[i];
    }

    // if the last value overflows, we're done
    return (i < len);
}

uint8_t x[LEN];

memset(x, 0, sizeof(x));

while (incx(x, sizeof(x)))
    f(x);
...