什麼是有效的方法來過濾數組

Question

我在linux上編程c，我有一個大整數數組，如何過濾它，例如，找到適合某些條件的值，例如，值> 1789 & & value < 2031.做這件事的有效方法是什麼？我需要先排序這個數組嗎？

我已經閱讀了答案並感謝大家，但我需要在這個大陣列上多次做這樣的過濾操作，不僅僅是一次。那麼每次最好的方法是一個接一個迭代它？

Answer 1

排序排列第一。然後在每個查詢中執行2個二進制搜索。我假設查詢會像 -

Find integers x such that a < x < b 

第一二進制搜索會發現元件，使得Array[i-1] <= a < Array[i]和第二二進制搜索的索引i會發現指數j這樣Array[j] < b <= Array[j+1]。那麼你想要的範圍是[i, j]。

該算法的複雜性是在預處理O(NlogN)和O(N)每個查詢，如果您想對所有的元素和O(logN)每次查詢遍歷，如果你只是想計算過濾元件的數量。

讓我知道如果你需要幫助實現在C.二進制搜索有一個在C++ STL命名用C binary_search()和lower_bound()和upper_bound()庫函數。

Answer 2

要過濾數組，您必須查看每個元素一次。沒有必要查看任何元素更多比一次，所以簡單的線性搜索符合您條件的項目的數組將會像您所能得到的那樣高效。

排序數組最終會多次查看某些元素，這對於您的目的不是必需的。

Answer 3

如果您想要對數組執行的唯一操作是獲取與此條件匹配的值，則只需遍歷數組並檢查每個值的條件（O(n)與O(nlogn)）就會更快。但是，如果您要對此數組執行多個操作，則最好對其進行排序。

Answer 4

您可以使用max heap作爲與源數組大小相同的數組實現。使用min-1值初始化數值，並在數字進入時將值插入最大堆中。第一個檢查是查看要插入的數字是否大於第一個元素，如果不是，放棄它，如果它更大然後將其插入到數組中。要獲取數字列表，請閱讀新數組中的所有數字，直到min-1。

Answer 5

如果您可以騰出更多內存，那麼您可以掃描您的數組一次，獲取匹配值的索引並將其存儲在另一個數組中。這個新的數組將顯着縮短，因爲它只有與特定模式相匹配的值的索引！事情是這樣的

int original_array[SOME_SIZE]; 
int new_array[LESS_THAN_SOME__SIZE]; 

for (int i=0,j=0; i<SOME_SIZE; i++) 
{ 
    if (original_array[i]> LOWER_LIMIT && original_array[i]< HIGHER_LIMIT) 
    { 
     new_array[j++] = i; 
    } 
} 

你需要做一次以上，並形成現在起，

for (int i=0; i< LESS_THAN_SOME_SIZE; i++) 
{ 
    if (original_array[new_array[i]]> LOWER_LIMIT && original_array[new_array[i]]< HIGHER_LIMIT) 
    { 
     printf("Success! Found Value %d\n", original_array[new_array[i]]) 
    } 
} 

因此，在一些內存的成本，就可以節省大量的時間。即使你花費了一些時間排序，你也必須每次解析排序的數組。該方法中，陣列的長度以及排序時間（在額外存儲器，當然:)成本）

Answer 6

嘗試這個庫最小化：http://code.google.com/p/boolinq/

它是基於迭代器和儘可能快地可以是沒有任何開銷。但它需要C++ 11標準。尤爾代碼將被寫在聲明路：

比基於迭代器的掃描速度更快

int arr[] = {1,2,3,4,5,6,7,8,9}; 

auto items = boolinq::from(arr).where([](int a){return a>3 && a<6;}); 
while (!items.empty()) 
{ 
    int item = items.front(); 
    ... 
} 

只能是多線程掃描...