有什麼算法/優化計算數組元素的條件子集？

Question

我的程序經常處理大量的數據，並且它的一個特定組件根據條件創建了這些數據的一個子集。你可以認爲這是，有字符串，

10457038005502 

問題是返回的第一個五年（比方說）非0的元素，即返回：

14573 

其實不然，每個該字符串的元素是包含大量數據的大數據結構，整個數據集的大小通常爲幾千兆字節，並且包含數以萬計的元素和來確定是否應該包括該元素（不是' 0'）每個元素需要被處理。我已經說過了，因爲我已經明確地解釋它，並且試圖將重點放在算法或技術上，而不是我們的具體實現和數據。

• 編輯：感謝那些迄今已回覆的人。所有的建議 圍繞多線程，這 我同意是一個很好的方法，我希望 本身的問題可以被視爲 一個算法問題（我們做 有帶螺紋的任務框架這 將融入。） - 我可疑， 雖然我不知道，這是一個 一般問題適用於 搜索各種數據。 有鑑於此，一個真棒回覆將 是「Schwarzenegger等人提出的 算法X在1995年爲此，google 這個詞。」

我們當前的方法是從輸入數據集中沿着數組的第一個點開始的單線性線性搜索，計算一個元素是否需要保留，並根據需要構建結果。通常所請求的數據子集並不在開頭 - 使用字符串示例，您可能需要知道元素8-15（如果存在15，那麼在您輸入數據結束之前您可能不知道）。 ）當然，我們不知道輸出數據集中的元素8是否在輸入數據集中，除非我們已經處理了遠離開始的數據集。

我們還應該如何解決這個問題？

我正在尋求任何完全不同的方法或算法來解決這類問題的輸入。

• 還有什麼其他方法可以解決這個問題，即快速獲取任意子集？

• 瞭解當前的解決方案是由於每個元素的處理量而產生的計算限制，或者更確切地說，因爲它需要生成每個元素以檢查它是否爲'0'，什麼算法或你可能會建議解決這個問題嗎？有什麼辦法可以最大限度地減少程序的工作嗎？

如果它影響到特定的庫或工具，我們使用C++（不受管理;我們使用Embarcadero C++ Builder 2010。）例如，我們不能使用LINQ，如果沒有使用它，我認爲它可能是這類問題的一個有用的工具/語言功能。但是，我們當然可以實施任何算法解決方案，您通常可以在其他環境中以較少的工作來實現這些解決方案

Answer 1

假設每個計算可以獨立於其他計算（即，項目的結果不依賴於前一項的結果），那麼顯而易見的第一步將是使用多線程並行執行計算。

Answer 2

從你的問題的快速閱讀，我想你可能想要實施某種形式的主 - 並行。讓一個線程（或您選擇的進程）讀取前N個條目，啓動N個線程（或進程）並將一個任務傳遞給每個線程。然後每個線程獨立工作並在完成時（成功或失敗）向主控者報告。然後，主人確定是否需要創建更多任務並傳遞給工作人員。

這樣做的主要潛在問題可能是確保跨工作人員的良好負載平衡，並確保主線程不是太多的瓶頸。

OpenMP 3.0支持這種類型的任務並行性，並具有相當平緩的學習曲線。