比較兩個非常大的列表（不適合內存）的最佳方法是什麼？

我有一個程序，從列表中的每個項目，並將其與另一個列表中的所有其他項目進行比較。迄今爲止它一直工作得很好，但數據量變大，將超過系統內存。比較兩個非常大的列表（不適合內存）的最佳方法是什麼？

我想知道什麼是最好的方式來比較兩個非常大的列表（也許5-10 GB每個列表）？

這是我正在做的一個非常簡單的例子（除非列表很大，for循環中的值實際上正在處理/比較中）。

import java.util.Collection; 
import java.util.HashSet; 
import java.util.Arrays; 

public class comparelists { 
    public static void main(String [] args) { 
     String[] listOne = {"a","b", 
       "c","d", 
       "e","f", 
       "g","h", 
       "i","j", 
       "k","l"}; 

     String[] listTwo = {"one", 
       "two", 
       "three", 
       "four", 
       "five","six","seven"}; 

     for(int listOneItem=0; listOneItem<listOne.length; listOneItem++){ 
      for (int listTwoItem=0; listTwoItem<listTwo.length; listTwoItem++) { 
       System.out.println(listOne[listOneItem] + " " + listTwo[listTwoItem]); 
      } 
     } 

    } 
}

我意識到必須有一些磁盤IO在這裏，因爲它不適合在內存中，我INTIAL方法是兩個列表保存爲文件，並保存了一堆從那麼listOne線，然後流的整個文件listTwo，然後從listOne中獲得更多的行等等。有沒有更好的辦法？或者像我在上面那樣訪問列表的Java方式，但是根據需要交換到磁盤？

來源

2012-11-12 user1735075

http://programmers.stackexchange.com/ –

*這兩個*列表太大而不適合內存？你需要做什麼比較，結果會是什麼？ –

@JonSkeet對於內存來說都是太大了。每個項目都是一堆數據並在程序中處理。它不是簡單的文本比較或任何東西。 – user1735075

您可以將大數據放在平面文件中，然後一次從文件中流入一個數據項。這樣，在任何給定時間只有兩項數據在內存中。

顯然，這是不會贏得任何效益獎，但這裏是一個使用包含每個項目一行在文本文件中的數據文件，一個簡單的例子：

BufferedReader readerA = new BufferedReader(new FileReader("listA.txt")); 
String lineA; 
while ((lineA = readerA.readLine()) != null) 
{ 
    BufferedReader readerB = new BufferedReader(new FileReader("listB.txt")); 
    String lineB; 
    while ((lineB = readerB.readLine()) != null) 
    { 
     compare(lineA, lineB); 
    } 
    // TODO: ensure .close() is called on readerB 
} 
// TODO: ensure .close() is called on readerA

如果你正在使用的數據太複雜了，無法在文本文件中輕鬆存儲每行一個項目，您可以使用ObjectInputStream和ObjectOutputStream做類似的事情，它可以一次讀取和寫入一個Java對象到一個文件。

如果你可以設法在內存中適應listB，那麼顯然你會在第一個循環中節省相當多的磁盤訪問。如果有足夠的重複數據，記憶可能會幫助您將listB放入內存。

此外，項目的比較是一個教科書示例，可以通過使用並行化來加速問題。例如。將數據比較工作交給工作線程，以便文件讀取線程可以專注於最大化磁盤的吞吐量。

來源

2012-11-12 18:07:29

值得注意的是大約需要800年。 ;） –

@PeterLawrey你對執行時間的評論很有洞察力，我贊成他們。但他並沒有詳細說明執行時間的限制，我也不知道他得到的問題有多深。所以我想從最基本的代碼開始，針對特定問題的優化可能會被應用。例如，如果數據適用於該類型的優化，則您的預先分類建議將會很有趣。 –

+1你的答案順便說一句，因爲它是你可以做的最好的問題給予的信息。 –

使用享元模式。這裏是一個鏈接：

http://en.wikipedia.org/wiki/Flyweight_pattern

來源

2012-11-12 17:39:03

我可以看到你的目標來執行2的Cartesian product非常大名單的東西。

而且我認爲你擔心的低效率是從文件讀入主內存的時間。

如何將列表劃分爲可以加載到內存中的塊。說l1[0]是l1和l1[1]中前1000個項目的列表，是下1000個項目的列表。

然後，你要比較：

l1[0] with l2[0] 
l1[0] with l2[1] 
l1[0] with l2[2] 
... 
l1[0] with l2[0] 
l1[1] with l2[1] 
l1[2] with l2[2] 
...

與從文件中讀取少acheive相同的總的效果。

來源

2012-11-12 18:04:58 Billiska

比較兩個非常大的列表（不適合內存）的最佳方法是什麼？

回答

相關問題