在Java中維護top-k

在java中無法使用這種方法：在Java中維護top-k

我從一個文件中逐行傳輸字符串集。

s1 s2 s3 
s4 s5 
s6 s7 s8 s9 s10 
...

我每一行加載到TreeSet，做了一些分析，並把它扔掉，並移動到下一行...我能適應各行的內容在內存中，但不是萬能的。

現在我想保持迄今爲止在掃描中遇到的前5個最大的字符串集合（不存儲任何其他內容）。

我想有一個SetSizeComparatorPriorityQueue，與當隊列大小達到5任何人得到了一個更簡潔的解決方案add/poll？

（我今天不能腦子。我有啞......）

來源

2010-09-28 badroit

你是如何確定什麼是「最大的」設置？ – NullUserException 2010-09-28 00:38:41

基數的設置... .size（） – badroit 2010-09-28 00:41:18

您的解決方案聽起來不錯。你必須「偷看（）」來知道當前集合是否比隊列中最差的一個更好。您還必須在「比較」功能中打破關係。 – 2010-09-28 00:44:32

創建一個元組，例如LineTuple，由一個行及其字符串頻率組成。
擁有LineTuples的min heap，比較器用於比較頻率值。
對於前k行，將它們插入到堆中。
從第（k + 1）第一行起，
- 提取物中的根，即具有最低頻率的元組，來自堆，和（此操作O(lg k)）。
- 用當前行創建一個元組，並將其插入堆中。（該操作是平均恆定時間，最壞情況下O(lg k)）
在任何時間點，包含在堆中k元組是k最大線。

我不太流利的Java，所以我不能提供任何代碼示例。但是，請檢查here，here。

來源

2010-09-28 01:01:55 Arun

是的，這幾乎是我提到的'PriorityQueue'方法。 – badroit 2010-09-28 01:21:47

不抽取和插入每一步都需要每次都重新堆疊？所以成本是O（n * log k）。其中n是流中項目的數量？應該可以得到O（n + m * log k），其中m是大於前面項目的前k項的項數（m與平均情況下的log n成比例並且等於n in最壞的情況）？ – 2010-09-28 20:03:12

Reheaping包含在'extract root'和'insert'操作中。 – Arun 2010-09-28 20:07:09

爲什麼沒有下文的工作？

<T> T[] topK(Iterator<? extends T> items, int k, Class<T> clazz, Comparator<? super T> cmp) { 
    T[] topK = Arrays.newInstance(clazz, k); 
    if (k == 0) { return topK; } 
    for (int i = 0; i < k && items.hasNext(); ++i) { 
    topK[i] = items.hasNext(); 
    } 
    // TODO: what is the appropriate output when there are less than k input? 
    Arrays.sort(topK, cmp); 
    for (T item; items.hasNext();) { 
    item = items.next(); 
    if (cmp.compareTo(item, topK[k - 1]) < 0) { 
     int pos = Arrays.binarySearch(topK, item); 
     if (pos < 0) { pos = ~pos; } 
     System.arraycopy(topK, pos, topK, pos + 1, k - (pos + 1)); 
     topK[pos] = item; 
    } 
    } 
    return topK; 
}

變速周圍是O（K），其是不太理想，但成功的比較的數量應該減小作爲TOPK得到逐漸變大，並且比較每個步驟是爲O（log K）這是與使用PriorityQueues獲得的任何基於堆的方法相同。

來源

2010-09-28 01:01:25

有趣的方法，但我發現'PriorityQueue'更方便，並且會提供大致相同的複雜性（稍微好一些，沒有承擔小的成本，但假設相對較小的top-k，成本很小）。 – badroit 2010-09-28 01:28:14

下面是一個算法，用於從流中隨機選擇k元素：

from random import randint 

def rand_k(a, k): 
    ret = [] 
    n = 0 
    for e in a: 
    n += 1 
    if len(ret) < k: 
     ret.append(e) 
    else: 
     if randint(1, n) <= k: 
     ret[randint(0, k-1)] = e 
    return ret

注意，每個元件將具有概率的k/n被選擇，其中n是元件的總數。需要O(n)時間和O(k)內存。

EDIT

在位置i（從1開始）選擇元件，用i > k的概率，是：

(k/i) * (1 - (k/(i+1))*(1/k)) * ... * (1 - (k/n)*(1/k))

即，選擇第i個元素的概率，而不是由以下任何元素取代它。簡化產品的每一個因素：

= (k/i) * (i/(i+1)) * ((i+1)/(i+2)) * ... * ((n-1)/n)

其中取消後，在結果：

= k/n

的i <= k的情況是相似的。

來源

2010-09-28 03:44:35

漂亮。儘管如此，仍然沒有完全包裹我的頭，但是看到一個元素剩下的概率進展爲'1 -1/2 -1/3 ... -1 /（nk）'，我假設'K/N'？而且插入的概率給出了一個元素保持到該點的概率相同的概率？不適合，除非'n >> k'？ – badroit 2010-09-28 22:10:11

歡呼聲清除。 – badroit 2010-09-29 00:34:52

澄清：這似乎是[水庫採樣]（http://en.wikipedia.org/wiki/Reservoir_sampling），它執行_uniform_選擇。如果我正確理解OP，他對top-k元素感興趣，這是完全不同的東西。 – bluenote10 2013-12-20 14:28:15

您可以爲此使用TreeSet。見減速類此的Hadoop例如：

https://trac.declarativity.net/browser/hadoop-0.19.2/src/examples/org/apache/hadoop/examples/TopK.java?rev=4870#L152

來源

2010-09-29 00:40:42

是的，這是一個*稍微*更昂貴的堆方法形式...需要「重新堆積」，根據麥克塞繆爾對另一個答案的評論。更高效地檢查你是否應該在插入它之前添加它。 – badroit 2010-09-29 02:37:31

@badroit：你重新堆積了一組k元素，因爲k是一個常數，所以這將花費很少的時間。 – 2010-09-29 16:24:39

在Java中維護top-k

回答

相關問題