從百萬條記錄中獲得排名前10位和後10位

我有一份報告顯示2-4百萬條記錄。我從oracle到java獲取記錄並將其推送到excel報告。所有這些都已經完成！從百萬條記錄中獲得排名前10位和後10位

現在，我還需要添加一個新的選項卡，前10名和最後10條記錄。什麼是最好的方法來做到這一點？

我應該在java中使用PriorityQueue實現還是使用二叉樹來保持前10位和後10位的軌道。我不需要在數據結構中存儲十億條記錄。我只需要一次保存10個。 ex：

PriorityQueue<DataObject> queueTop10 = new PriorityQueue<DataObject>(10, topComparator); 
PriorityQueue<DataObject> queueLast10 = new PriorityQueue<DataObject>(10, leastComparator); 
    while (data is coming from database) 
    { 
    // push to excel stuff here 
    queueTop10 .add(dataObject); OR binarytreeTop.insert(dataObject) 
    queueLast10.add(dataObject); OR binarytreeLeast.insert(dataObject) 
    }

請讓我知道我是否也可以使用其他數據結構。

感謝

來源

2015-05-11 user1797559

你是什麼意思的「前10名」？每個記錄是否有某種分數？或者你在尋找最常出現的關鍵值？或者是什麼？ – erickson

國際海事組織它只是使用堆只獲取最小元素的工作較少。樹更加有組織，但需要更多計算來維護該組織。在你的情況下，你需要訪問前10和10個記錄，並且堆可能不適合你。我相信你應該使用樹實現（'TreeMap'），額外的開銷也許是合理的。 –

誰讀這些報告？許多唱片開始進入「如果我們把這份報告給國內每個人......」或者「如果我們把這些網頁疊在一起，我們就有一堆X％的路要登上月球」。另外，[OutOfMemoryError]（http://docs.oracle.com/javase/8/docs/api/java/lang/OutOfMemoryError.html）。 –

最受歡迎的算法使用最小堆（Java中的PriorityQueue），但在算法中應該有一些大小檢查。假設每個項目都有一個分數，並且您想要收集最高分數的10個項目。 PriorityQueue有效地與最低分數公開資料：

PriorityQueue<DataObject> top = new PriorityQueue(10, comparator); 
for (DataObject item : items) { 
    if (top.size() < 10) top.add(item); 
    else if(comparator.compare(top.peek(), item) < 0) { 
    top.remove(); 
    top.add(item); 
    } 
}

來源

2015-05-11 16:46:03 erickson

，因爲它的功能類似於Java的堆您可以使用優先級隊列。請參閱How does Java's PriorityQueue differ from a min-heap? If no difference, then why was it named PriorityQueue and not Heap?

來源

2015-05-11 16:43:39 nullPointer

PriorityQueue<T>不會與你的代碼工作的，是的，因爲10在構造函數是初始能力;你的隊列會隨着你的增長而增長到1B項目。

然而，TreeSet<T>將工作，一個小的修改。您需要添加刪除第11項的代碼，每次隊列增長過去十次時：

TreeSet<DataObject> top10 = new TreeSet<DataObject>(topComparator); 
TreeSet<DataObject> bottom10 = new TreeSet<DataObject>(leastComparator); 
while (data is coming from database) { 
    top10.add(dataObject); 
    if (top10.size() == 11) { 
     top10.pollLast(); 
    } 
    bottom10.add(dataObject); 
    if (bottom10.size() == 11) { 
     bottom10.pollLast(); 
    } 
}

來源

2015-05-11 16:49:02 dasblinkenlight

嘿，非常感謝您的快速回復！如果我能夠通過erickson管理priorityQueue以僅包含10個元素（如下所示），那麼您認爲哪種數據結構會更高效/更快。 – user1797559

@ user1797559我不認爲會有任何不同，因爲隊列很小。事實上，您可能會將其更改爲一個數組，並對10個項目進行線性搜索而不會看到任何差異（這是內存中隨機位置的3次比較與內存中連續位置的10次比較，因此參考位置可能會縮小間距爲你）。如果你去30到50個元素，故事可能會有所不同，但對於10個項目可能無所謂。 – dasblinkenlight

這是一個很好的觀點！再次感謝！ – user1797559

excel電子表格中有40億條記錄？不，你不需要https://superuser.com/questions/366468/what-is-the-maximum-allowed-rows-in-a-microsoft-excel-xls-or-xlsx

你應該在數據庫上這樣做，而不是依賴於java的實現。對於這麼多的記錄來說，它肯定會比優化的db查詢效率低。

來源

2015-05-11 16:59:59 NimChimpsky

嘿！感謝您及時的回覆。我真的很抱歉打字錯誤。我意思是2-4百萬條記錄，而不是十億條。我們將其保存爲CSV格式，並將其分爲不同的輸出文件。由於排序邏輯有點複雜，所以我不想在數據庫上做這件事，所以查詢需要很多連接。由於我已經獲得了一次數據，我認爲它會更快，如果我可以使用相同的並使用比較器topComparator和leastComparator提取前10個和最少10個記錄。請讓我知道你在想什麼。 – user1797559

從百萬條記錄中獲得排名前10位和後10位

回答

相關問題