最大限度地減少大負載數的算法

Question

我有一個算法，我需要計算大對象之間的所有成對距離（其中距離是一個真實的度量，因此dist(a,b) == dist(b,a)，在所有其他度量要求之間）。我有大約一千個物體，所以我需要計算大約500,000個距離。有幾個問題：

1. 所有這1000個對象都是序列化的，坐在磁盤上的單個文件中。
2. 與相對平凡的距離計算相比，從磁盤讀取數據是一項巨大的操作。
3. 我不能在所有的內存中同時進行交換，然後顛簸。我一次可以存儲500個內存。
4. 這意味着在某些時候，我需要在先前讀取並釋放內存之後，將對象重新讀入內存。

因此，鑑於從磁盤讀取是瓶頸，並且我無法一次讀取超過一半的數據，任何人都可以考慮讀取和釋放這些對象的算法，從而最大限度地減少總讀取次數？

我認爲在上半年閱讀，做所有這些成對的距離，釋放所有的內存和閱讀下半年，然後做所有這些成對的距離。在這一點上，我仍然需要前半部分物體和第二部分物體之間的距離，我不知道該做什麼。我還考慮過有一個緩存，當滿的時候，隨機選擇一個當前對象驅逐並讀取下一個對象，但我覺得必須有更好的選擇。我認爲像LRU這樣的東西，但它可能會導致所需對象在最後一次計算時被驅逐的行爲。

總而言之，我有點卡住了。有什麼建議？

Answer 1

在上半場加載積分。計算成對距離。將前半部分保存在內存中，逐個加載下半部分的點，計算距離。加載整個下半部分並計算成對距離。這大約是每點1.5個讀取點，這在下面的模型中是最佳的。

的模型是適用於此任務的語法正確的程序是（我，Ĵ），其含義是加載的形式LOAD指令序列點我到內存位置Ĵ。如果對於每一對點都存在一個指令，那麼程序是正確的，在該指令之後兩個點都在內存中。

很明顯，在一個正確的程序中，每個點至少加載一次。假設正好有1000點和500個地點，那麼至少有500次驅逐有利於第一次加載點。假設不失一般性，記憶中沒有任何重複點。一個點後p贊成點q被加載首次的被驅逐，有必要重新加載p爲了使距離p和q之間被計算。因此，至少有500次重新加載，因此至少有1500次加載。

Answer 2

我首先想到的（所以它可能不是最好的一個）：

對每個i：

• 讀第i個組的這些250之間的距離計算。

• 對於250每個剩餘組j：

  • 閱讀的第j個基團。

  • 計算第i組和第j組的點之間的距離。

  • 放棄組j。

• 放棄組i。

所以，你會讀出以下幾組：

i j 
1 2 
    3 
    4 
2 3 
    4 
3 4 
4 

你本身注意到，閱讀小組4是毫無意義 - 讀3時，你可以計算出的距離（或一些其他）組。

因此，您以每點平均讀取(1+2+3+3)/4 = 2.25讀取結束。

Answer 3

我會盡量稍微改進@Dukeling的答案。如果我理解正確，這將更好

i j 
1 2 
    3 
    4 
2 
3 
    2 

現在你有（1 + 3 + 2 + 1）/4=1.75讀取每點。