Java：來自流源的前n個元素

假設您從「流」源讀取數據項和相關分數（即無法隨機訪問或多次傳遞可能）。Java：來自流源的前n個元素

什麼是最好的方式來保持，在任何時候，只有那些在內存中的重量最輕的目前遇到的。我會對「Java」的做法感興趣，成語越短越好，而不是算法（「使用搜索樹，插入新元素，如果超過大小刪除最大值」）。

下面是我提出的解決方案，但是我覺得它有點冗長，也有一些行爲可能是意想不到的（同一項目不同分數可能保持多次，而同一項目添加相同分數是隻保留一次）。我也覺得應該有這樣的東西存在。

import java.util.AbstractMap.SimpleEntry; 
import java.util.Map.Entry; 
import java.util.Comparator; 
import java.util.TreeSet; 

/** 
* Stores the n smallest (by score) elements only. 
*/ 
public class TopN<T extends Comparable<T>> { 
    private TreeSet<Entry<T, Double>> elements; 
    private int n; 

    public TopN(int n) { 
    this.n = n; 
    this.elements = new TreeSet<Entry<T, Double>>(
     new Comparator<Entry<T, Double>>() { 
      @Override 
      public int compare(Entry<T, Double> o1, Entry<T, Double> o2) { 
      if (o1.getValue() > o2.getValue()) return 1; 
      if (o1.getValue() < o2.getValue()) return -1; 
      return o1.getKey() == null ? 1 : o1.getKey().compareTo(o2.getKey()); 
      } 
    }); 
    } 

    /** 
    * Adds the element if the score is lower than the n-th smallest score. 
    */ 
    public void add(T element, double score) { 
    Entry<T, Double> keyVal = new SimpleEntry<T, Double>(element,score); 
    elements.add(keyVal); 
    if (elements.size() > n) { 
     elements.pollLast(); 
    } 
    } 

    /** 
    * Returns the elements with n smallest scores. 
    */ 
    public TreeSet<Entry<T, Double>> get() { 
    return elements; 
    } 
}

也有同樣的問題，但它不包括流源/內存要求： Find top N elements in an Array

來源

2012-03-06 benroth

使用「堆」數據結構。 Java有一個內置的：PriorityQueue。只需將您的比較器定義爲「最佳」，然後將所有來自數據流的數據送入優先隊列。

編輯：

要多一點顏色添加到這個答案，你可能需要做這樣的事情：

定義是相反的方式工作，以你想要的比較（即主張你想扔掉的物品） - 或者定義一個能正確工作的物品，然後將其包裝起來Collections.reverseOrder(...)
迭代你的數據並將每個元素放入pqueue中。
對於每個插入，如果pqueue的大小大於n，則使用poll()從堆中移除「top」元素 - 由於比較器的原因，它實際上將是「最差」的元素。

你留下的是一個有n個元素的pqueue，其中「最不好的」是。

來源

2012-03-06 10:01:23 dty

PriorityQueues是無界的，我認爲他需要只保留一定數量的在存儲器元件中的一個的時間。 – MahdeTo 2012-03-06 10:14:09

啊 - 我在編寫評論時似乎一直在編輯我的編輯。看我的編輯。 – dty 2012-03-06 10:16:45

看起來確實如此。幾乎與他具有相同的解決方案，但具有優先隊列而不是樹集。 – MahdeTo 2012-03-06 10:18:11

您可以番石榴的Comparators類獲得所需的結果。請參閱下面的示例，獲取前5位數字。 Api可以被發現here。

import java.util.Comparator; 
import java.util.List; 
import java.util.stream.Collector; 

import org.junit.Test; 

import com.google.common.collect.Comparators; 
import com.google.common.collect.Lists; 

public class TestComparator { 

    @Test 
    public void testTopN() { 
     final List<Integer> numbers = Lists.newArrayList(1, 3, 8, 2, 6, 4, 7, 5, 9, 0); 
     final Collector<Integer, ?, List<Integer>> collector = Comparators.greatest(5, 
       Comparator.<Integer>naturalOrder()); 
     final List<Integer> top = numbers.stream().collect(collector); 
     System.out.println(top); 
    } 

}

輸出：[9,8，7,6，5]

來源

2017-06-28 08:12:42

Java：來自流源的前n個元素

回答

相關問題