C：有效地循環大陣列

我有一個有大約500個數字的主列表整數數組。而且，我有一組100個隨機數字，它從主列表中挑選以找出缺失的數字。現在，我需要通過這個隨機數字列表對照主列表。 C編程中最好的方法是在不掛起程序的情況下通過它。如果我對500個元素進行簡單的'for'循環，它會掛起，因爲它需要遍歷整個列表。有人可以指示我嗎？C：有效地循環大陣列

謝謝。

來源

2012-10-15 Daisy

如果列表與UI不相關，則可以在後臺線程中運行該函數。 – vishy

雖然看起來好像只做了一次，但500個條目的數組不應該在代碼中出現任何明顯的減速。 – nickolayratchev

好吧，舉個例子，我給了500，讓我們拿走了5萬個元素。 – Daisy

首先，你應該分析它。我們正在討論的最大值只有500 * 100 = 50,000次操作。一臺普通的現代計算機能夠在十分之一秒內完成它，除非你非常低效地編寫它。

假設您想要優化它，您應該對主數組進行排序，並對隨機數組的每個元素運行一個binary search。這會將操作次數從50,000減少到最多900次，因爲對500個數字進行二分搜索最多需要9次比較。

下面是使用內置的標準C庫的排序和二進制搜索功能（qsort和bsearch）的實現：

int less_int(const void* left, const void* right) { 
    return *((const int*)left) - *((const int*)right); 
} 

int main(void) { 
    size_t num_elements = 500; 
    int* a = malloc(num_elements*sizeof(int)); 
    for(size_t i=0 ; i<num_elements ; i++) { 
     a[i] = rand() % num_elements; 
    } 
    qsort(a, num_elements, sizeof(int), less_int); 
    size_t num_rand = 100; 
    int* r = malloc(num_rand*sizeof(int)); 
    for(size_t i=0 ; i < num_rand ; i++) { 
     r[i] = rand() % num_rand; 
    } 

    for (size_t i = 0 ; i != num_rand ; i++) { 
     int *p = (int*) bsearch (&r[i], a, num_elements, sizeof(int), less_int); 
     if (p) { 
      printf ("%d is in the array.\n", *p); 
     } else { 
      printf ("%d is not in the array.\n", r[i]); 
     } 
    } 

    free(a); 
    free(r); 
    return 0; 
}

這裏是一個link to this running program on ideone。

來源

2012-10-15 12:51:45 dasblinkenlight

對隨機數組進行排序並對其進行二進制搜索以查找主數組中的每個元素以找出丟失的元素？ – SparKot

我對此感到抱歉，它不適用於iPhone，這只是C程序。 – Daisy

@ user1729070那麼它應該是一個更小的問題，因爲電腦比手機更快。這裏的東西是_profile_和_measure_。除非您需要每秒重複幾次，否則很可能不會引人注目。 –

n - 隨機數組長度。主數組數組長度。

排序隨機arrary。 n * log（n）
二級搜索排序數組中的每個元素在主列表中。因此，你會有每個缺失的元素。 （M）*的log（n）

=>（M + N）*的log（n）整個操作。與N = 100和M = 500我們已經相比50000迭代與原始編碼

600 *日誌（100）日誌到基座2

約3986次迭代。 PS：如果兩個數組都被排序，只需比較O（m）即可。

來源

2012-10-15 13:07:00 SparKot

C：有效地循環大陣列

回答

相關問題