使用C生成所有元組 - 比嵌套循環更好的方法？

我有一個長度爲11的數組double x[]和一個函數f(double x[])。我想通過離散化找到函數f()的最小值。所以對於給定的值val1, val2, ..., valn我需要一個循環遍歷{val_1，...，val_n}^11中x的所有元組。我可以很容易地使用11個嵌套循環，但是這真的是我能做的最有效率的嗎？使用C生成所有元組 - 比嵌套循環更好的方法？

編輯： 澄清事情：函數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個小時。這就是爲什麼我正在尋找最有效的方式來實施它。

來源

2012-01-10 lumbric

你真的是「高效」，或者你的意思是「最整潔」？ – 2012-01-10 14:36:17

我需要*真*快的東西。我期望該計劃運行數小時。但是，當然，如果代碼的*也是*可讀性和靈活性的話，那就太棒了。 – lumbric 2012-01-10 14:39:55

什麼是f（）？你能用筆和紙找到最低限度嗎？你看過漸變下降算法嗎？ – Phonon 2012-01-10 14:40:33

這裏是僞代碼（不一定是語法，正確的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 
}

來源

2012-01-10 14:55:40

@OliCharlesworth **非常好！這絕對是這些實現中需要*重要*評論的一種實現方式（由您的回答的評論數量來證明）。 – dasblinkenlight 2012-01-10 15:19:41

@dasblinkenlight：公平地說，上面的評論是因爲我沒有正確地閱讀這個問題。但我會添加評論。 – 2012-01-10 15:21:17

非常好，我同意。請告訴我，你並沒有自己發明這個;-) – 2012-01-10 15:28:02

當你需要的循環數量太高或者在編譯時不知道的時候要做的事情是使用遞歸。

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; 
}

來源

2012-01-10 14:40:39 dasblinkenlight

啊，是的，這聽起來不錯。但是，與for循環相比，遞歸非常慢嗎？ – lumbric 2012-01-10 14:49:47

它肯定比嵌套循環慢，但它通常不是遞歸作爲一種實現技術，減慢了事情的速度，而是在遞歸調用的每個級別上做了什麼。在這種情況下，我懷疑時間會受到'check'功能的支配。 – dasblinkenlight 2012-01-10 15:14:45

啊這也是一個非常有用的提示！不幸的是，我確信我不會巧妙地優化「檢查」功能。 – lumbric 2012-01-10 15:23:38

您可能希望減少對處理器緩存的壓力。因此，如果Nval_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);

來源

2012-01-10 21:00:42

使用C生成所有元組 - 比嵌套循環更好的方法？

回答

相關問題