Ç初始化（非常）大的整數與對應於索引

EDIT3值數組：通過限制陣列的初始化僅奇數優化。謝謝@羅尼！Ç初始化（非常）大的整數與對應於索引

EDIT2：謝謝大家，好像沒有什麼更多我可以爲此做。

編輯：我知道，Python和哈斯克爾在其他語言中實現或多或少執行相同的操作我有波紋管，並且該遵守的代碼將擊敗他們的任何一天。我只是想知道標準C（或任何庫）是否具有內置函數來更快地完成此操作。

我使用埃拉託塞尼算法實現在C語言的原篩並需要初始化任意大小ñ的0-2的整數數組Ñ。我知道，在Python，你可以這樣做：

integer_array = range(n)

，就是這樣。或在Haskell：

integer_array = [1..n]

不過，我似乎無法找到C實現類似的方法，我已經想出瞭解決辦法初始化了它的數組，然後遍歷，每個值分配給指數在那個時候，但它感覺非常低效。

int init_array() 
{ 
    /* 
    * assigning upper_limit manually in function for now, will expand to take value for 
    * upper_limit from the command line later. 
    */ 
    int upper_limit = 100000000; 
    int size = floor(upper_limit/2) + 1; 

    int *int_array = malloc(sizeof(int) * size); 
    // debug macro, basically replaces assert(), disregard.  
    check(int_array != NULL, "Memory allocation error"); 

    int_array[0] = 0; 
    int_array[1] = 2; 

    int i; 

    for(i = 2; i < size; i++) { 
     int_array[i] = (i * 2) - 1; 
    } 

    // checking some arbitrary point in the array to make sure it assigned properly. 
    // the value at any index 'i' should equal (i * 2) - 1 for i >= 2 
    printf("%d\n", int_array[1000]); // should equal 1999 
    printf("%d\n", int_array[size-1]); // should equal 99999999 

    free(int_array); 

    return 0; 

error: 
    return -1; 
}

有沒有更好的方法來做到這一點？（不，顯然沒有！）

來源

2013-07-23 Dalton

爲什麼會變成這樣低效？這看起來完全最佳。任何明智的編譯器都不難理解這些代碼的作用，並以任何最適合該平臺的方式實現它。 –

它只是好像應該有一些辦法更快地初始化爲0值數組爲n。因爲我正在查看任意大小的數組，所以即使在編譯的C代碼中實現時，這最終可能會減慢算法的速度。 – Dalton

爲什麼你認爲其他方式會更快？這個代碼可能是次優的？你已經乾淨清楚地告訴編譯器你想要什麼，什麼會阻止它生成最有效的代碼來實現這種效果？ –

這裏更好的算法大概是在優化分配方面一個更好的選擇： -

減半採取的事實，即你只需要測試在奇數大小int_array_ptr篩
運行該通過一些輪因式分解的數字3,5,7 70％，以減少後續的比較+

這應該加快速度。

來源

2013-07-23 02:30:46 Ronnie

+1。算法改進打敗了微觀優化。 – Thilo

**優秀**。這個答案完美地表明瞭@Thilo所做的非常重要的一點。 –

含義：更多行代碼更有效率。 – Thilo

我想出瞭解決方案初始化數組，然後遍歷它，在這一點上指定每個值到索引，但它感覺非常低效。

您可能可以減少代碼行數，但我認爲這與「效率」無關。儘管Haskell和Python中只有一行代碼，但引擎蓋下面發生的事情與您的C代碼所做的事情是一樣的（在最好的情況下;根據實現方式它可能會更糟糕）。

有標準庫函數，以填補常數值（他們可以想見，有更好的表現，但我不會押注）一個數組，但這並不適用於此。

來源

2013-07-23 02:21:16 Thilo

+1許多解釋型語言，如python，都是用C語言編寫的。 –

我可以看到有一點意義的最小改進是在循環中與0而不是'size'進行比較。 CPU在這方面更好。我懷疑這是否會產生重大影響。 – Thilo

Haskell和Python版本（以及Python 3）實際上是O（1）。 –

Ç初始化（非常）大的整數與對應於索引

回答

相關問題