哪個更快：適當的數據輸入還是適當的數據結構？

我有一個數據集，它的列是這樣的：哪個更快：適當的數據輸入還是適當的數據結構？

Consumer ID | Product ID | Time Period | Product Score 
1   | 1   | 1   | 2 
2   | 1   | 2   | 3

等。

作爲計劃的一部分（用C語言編寫），我需要處理所有消費者對特定產品和時間段組合給出的所有可能組合的產品分數。假設有3個產品和2個時間段。然後我需要處理所有可能的組合的產品分數如下所示：

Product ID | Time Period 
1   | 1 
1   | 2 
2   | 1 
2   | 2 
3   | 1 
3   | 2

我需要處理沿着上述線很多次的數據（> 10K）和所述數據集是相當大的（例如， 48K消費者，100個產品，24個時間段等）。所以速度是一個問題。

我想出了兩種方法來處理數據，我想知道哪種方法更快或者可能無關緊要？（速度事項而不是在不適當的維護/可讀性的成本）：

排序通過數據產品ID和時間段，然後循環中的數據，以提取對於所有可能的組合的數據。
存儲所有消費者的消費者ID，他們提供產品ID和時間段的特定組合的產品評分並相應地處理數據。

有什麼想法？任何其他方式來加快處理？謝謝

來源

2010-05-20 vad

與許多與性能相關的問題一樣，唯一真正的，明確的答案是編寫一個基準。速度將取決於很多事情，而且聽起來不像是在談論線性算法與二次算法的簡單情況（甚至會對輸入大小有額外的依賴性）。

因此，實施兩種方法，在樣本數據上運行它們，並計算結果。這將比我們試圖在信息有限的情況下在我們的腦海中解決它要快得多，也更具決定性。

來源

2010-05-20 14:33:03 danben

downvoter是否在意評論？ – danben 2010-05-20 14:44:47

對不起，我在回答中解決了這個問題，而不是評論。 – 2010-05-20 14:48:34

這是一條路，但我希望有人能夠提供一些見解！ – vad 2010-05-20 17:36:19

我建議過濾數據，如第二步，然後按照第一步進行處理。如果您的表現不可接受，請調整表現。爲您的基準設置一些基準，然後嘗試一些不同的方法。

在大多數現實世界的情況下，我建議不要僅僅爲了基準測試而實施多種方法。表現可能相似。如果它不相似，它可能表現不佳，並將顯然需要調整。在實現其他功能時，你的時間可能會更好。

來源

2010-05-20 14:35:12

這將使一個小型的數據庫表。如果消費者/產品/時間的全部矩陣存在，則大約0.4GB的數據。你有沒有考慮過在SQL中運行整個事情？即使你沒有完整的數據庫，對於這樣大小的數據，爲每個可能的排序順序生成一個完整的表並將每個轉儲到一個文件是可行的。然後，您可以加載任何您需要的文件，以您選擇的任何順序走它。另外，如果您可以並行運行全部10K次傳遞或者每次至少運行幾十次傳輸，那麼您可能會提前這樣做，因爲它可能會大幅減少IO等待和/或緩存未命中次數。

來源

2010-05-20 14:39:48 BCS

對於這種類型的問題，SQL不是過度使用，尤其是如果我可以將所有數據加載到內存中？ – vad 2010-05-20 17:34:35

如果你有一個scratch/test/sandbox服務器（甚至是SQLite工具），那麼根本就沒有。沒有過度殺傷的東西，只是不值得付出努力的東西。在這種情況下，如果您可以使用SQL來完成所有這些工作，那麼這將爲您節省所有數據處理工作。如果您可以比自己的解決方案更輕鬆地完成SQL IO，那麼您仍然遙遙領先。 – BCS 2010-05-20 18:12:47

其實這兩種方法看起來和我很相似。爲了存儲爲特定組合提供分數的所有客戶的客戶ID，您需要對數據進行分類或執行更昂貴的操作。

你可以交換時間嗎？如果是，那麼不要預先處理那麼多，而是創建一個包含所有組合（10x24）的數組來存儲分數。處理數據，並更新特定組合的分數。如果您需要平均分數，請存儲提供分數的客戶總數和數量。

來源

2010-05-20 14:43:03 kgiannakakis

我沒有得分在不同時間。數據並未實時到達。 – vad 2010-05-20 17:32:21

您有任何影響力的最慢部分可能會複製大塊內存。因此，第一種應用技巧是將每行的值放在結構中，並僅通過指針引用它，直到完成所有處理。該結構是這樣的：在那個

typedef struct { 
int consumer; 
int product; 
int time; 
int score; 
} rowData;

大廈我認爲你最好的辦法是遍歷輸入行，並建立由消費者確定結構的二叉樹（或其他有序結構）和產品，和包含指針的查找表到所有匹配rowData：

typedef struct { 
int consumer; 
int product; 
rowData * matches; 
} matchLut;

一旦所有的行已被放置在的查找在樹表然後每個束可以被處理。

來源

2010-05-20 14:54:09 youngthing

靈活數組的內存分配應該被智能地處理，儘管我沒有提到如何做到這一點！ – youngthing 2010-05-20 14:55:21

是的我有類似的想法... – vad 2010-05-20 17:36:57

如果內存允許將數據存儲在二維數組中（真的是3D，但我會在稍後討論）。這個數組將被索引（product_id，time_period）。

如果處理數據允許2D數組的每個元素可能是新數據的累加器，那麼您可以讀入數據元素，然後調整2D數組的相應元素以反映它。如果此方法起作用，則在完成讀取時將處理您的數據。

如果您的處理要求您每次都存在來自每個數據元素的數據，那麼可以使您的二維數組的每個元素成爲一個列表（此是第三D）。如果您不知道每個（product_id，time_period）會有多少個客戶條目，則它可以是一個可變長度列表。讀完數據後，您需要重新訪問2D數組的每個元素以處理每個列表。如何安排陣列以及如何訪問元素對性能至關重要。你可能會想動態聲明這一點，但在這個例子中

struct element_t element[NUMBER_OF_PRODUCTS][NUMBER_OF_TIME_PERIODS]; 
// don't forget to initialize these elements to empty 
... 
for (p = max_product_id; p >= 0; p--) { 
    for (t = max_time_period; t >= 0; t--) { 
     process(element[p][t]); 
    } 
}

會更好地工作，如果你想移動到下一個，因爲之前處理每一件產品。如果您想在處理每個時間段（針對所有產品）之前切換聲明的行，列和循環，以實現更好的緩存命中，那麼在切換到下一個時間段之前。

你應該注意，這不會對「排序這些數據」進行排序。

如果內存不允許，那麼您在讀取數據時可能需要將部分數據存儲到文件中。這與上面提到的數組/循環組織/緩存命中優化具有相同的問題，但它會放大很多倍。在讀取主數據結束時，您希望能夠處理來自特定臨時文件的所有數據（可能包含給定產品的所有數據（給定時間段內的xOR）），然後再轉到下一個。試圖做到這一點的主要不利之處在於，當您閱讀數據時，您很可能必須處理無法同時打開每個臨時文件的問題。這可能需要您提出一種開放文件交換的方式（與內存交換相同，除了交換的內容是打開的文件而不是內存頁面）。不過，這將是一個完整的其他問題。

來源

2010-05-20 15:59:18 nategoose

內存不是問題。您的建議是我在考慮第二步時想到的。謝謝 – vad 2010-05-20 17:30:44

我建議你根據最常訪問的進程重新排序你的數據。訪問頻率最高的數據應該是最簡單和最快速的訪問。

另外，請看Database Normalization。這是一個組織數據以儘量減少重複的概念，並且使訪問數據的效率更高。

另一個想法是使用不太流行的數據搜索索引。

來源

2010-05-20 17:26:45

我需要經常訪問所有組合。我意識到數據規範化，但使用SQL或其他一些似乎是在這裏矯枉過正。 – vad 2010-05-20 17:35:30

數據庫可能過度殺傷，但程序中的數據標準化可能有一些好處。 – 2010-05-21 16:22:01

哪個更快：適當的數據輸入還是適當的數據結構？

回答

相關問題