com.google.common.collect.MinMaxPriorityQueue#add ( )源码实例Demo

public void findKBest(int k,
                      float threshold,
                      MinMaxPriorityQueue<Pair<Float, Integer>> heap,
                      Vector hidden,
                      Vector output) {
  computeOutputSoftmax(hidden, output);
  for (int i = 0; i < osz; i++) {
    if (output.data[i] < threshold) continue;
    if (heap.size() == k && stdLog(output.data[i]) < heap.peekFirst().first()) {
      continue;
    }
    heap.add(new Pair<>(stdLog(output.data[i]), i));
  }
  while (heap.size() > k) {
    heap.pollLast();
  }
}
 

public CachedPostingListCounter rebuildCache() {
    MinMaxPriorityQueue<Entry> mostExpensive = MinMaxPriorityQueue
            .maximumSize(32).expectedSize(32).create();
    synchronized (this) {
        for (ObjectLongPair<int[]> p : frequency.keyValuesView()) {
            mostExpensive.add(new Entry(p.getOne(), p.getTwo()));
        }
    }
    ObjectIntHashMap<int[]> postingListMapping = new ObjectIntHashMap<>();
    int[] bitVector = new int[nDocuments];
    int length = mostExpensive.size();
    for (int i = 0; i < length; i++) {
        Entry e = mostExpensive.removeFirst();
        int[] docIds = e.docIds;
        postingListMapping.put(docIds, i);
        for (int docId : docIds) {
            bitVector[docId] |= (1 << i);
        }
    }
    return new CachedPostingListCounter(postingListMapping, bitVector);
}
 

/**
 * Used when the cache is growing past its max size to clone in a single pass.
 * Removes least recently used tables to get size of cache below its max size by
 * the overage amount.
 */
public PTableCache cloneMinusOverage(long overage) {
    assert(overage > 0);
    int nToRemove = Math.max(MIN_REMOVAL_SIZE, (int)Math.ceil((currentByteSize-maxByteSize) / ((double)currentByteSize / size())) + 1);
    MinMaxPriorityQueue<PTableRef> toRemove = BUILDER.expectedSize(nToRemove).create();
    PTableCache newCache = new PTableCache(this.size(), this.maxByteSize, this.timeKeeper);
    
    long toRemoveBytes = 0;
    // Add to new cache, but track references to remove when done
    // to bring cache at least overage amount below it's max size.
    for (PTableRef tableRef : tables.values()) {
        newCache.put(tableRef.table.getKey(), new PTableRef(tableRef));
        toRemove.add(tableRef);
        toRemoveBytes += tableRef.estSize;
        if (toRemoveBytes - toRemove.peekLast().estSize > overage) {
            PTableRef removedRef = toRemove.removeLast();
            toRemoveBytes -= removedRef.estSize;
        }
    }
    for (PTableRef toRemoveRef : toRemove) {
        newCache.remove(toRemoveRef.table.getKey());
    }
    return newCache;
}
 

@Override
public List<LinkRelevance> getSelectedLinks() {
    List<LinkRelevance> links = new ArrayList<>();
    while (links.size() < numberOfLinks && !topkLinksPerDomain.isEmpty()) {
        // adds the URL with max score of each domain
        MinMaxPriorityQueue<LinkRelevance> topk = newPriorityQueue(numberOfLinks);
        Iterator<Entry<String, MinMaxPriorityQueue<LinkRelevance>>> it = topkLinksPerDomain.entrySet().iterator();
        while (it.hasNext()) {
            MinMaxPriorityQueue<LinkRelevance> domain = it.next().getValue();
            topk.add(domain.poll());
            if (domain.isEmpty()) {
                it.remove();
            }
        }
        for(LinkRelevance link : topk) {
            links.add(link);
        }
    }
    this.topkLinksPerDomain = null; // clean-up reference
    return links;
}
 

/**
 * Used when the cache is growing past its max size to clone in a single pass.
 * Removes least recently used tables to get size of cache below its max size by
 * the overage amount.
 */
public PMetaDataCache cloneMinusOverage(long overage) {
    assert(overage > 0);
    int nToRemove = Math.max(MIN_REMOVAL_SIZE, (int)Math.ceil((currentByteSize-maxByteSize) / ((double)currentByteSize / size())) + 1);
    MinMaxPriorityQueue<PTableRef> toRemove = BUILDER.expectedSize(nToRemove).create();
    PMetaDataCache newCache = new PMetaDataCache(this.size(), this.maxByteSize, this.timeKeeper, this.tableRefFactory);
    
    long toRemoveBytes = 0;
    // Add to new cache, but track references to remove when done
    // to bring cache at least overage amount below it's max size.
    for (PTableRef tableRef : this.tables.values()) {
        newCache.put(tableRef.getTable().getKey(), tableRefFactory.makePTableRef(tableRef));
        toRemove.add(tableRef);
        toRemoveBytes += tableRef.getEstimatedSize();
        while (toRemoveBytes - toRemove.peekLast().getEstimatedSize() >= overage) {
            PTableRef removedRef = toRemove.removeLast();
            toRemoveBytes -= removedRef.getEstimatedSize();
        }
    }
    for (PTableRef toRemoveRef : toRemove) {
        newCache.remove(toRemoveRef.getTable().getKey());
    }
    return newCache;
}
 

@Test
public void comparatorTest() throws Exception {

  MinMaxPriorityQueue<DimensionValueMetricPair> testQueue = MinMaxPriorityQueue.maximumSize(2).create();

  DimensionValueMetricPair d1 = new DimensionValueMetricPair("d1", 1);
  DimensionValueMetricPair d2 = new DimensionValueMetricPair("d2", 2);
  DimensionValueMetricPair d3 = new DimensionValueMetricPair(30, 3);
  DimensionValueMetricPair d4 = new DimensionValueMetricPair("d4", 4);

  testQueue.add(d1);
  testQueue.add(d2);
  testQueue.add(d3);
  testQueue.add(d4);

  for (DimensionValueMetricPair pair : testQueue) {
    Assert.assertEquals(pair.getMetricValue().intValue() > 2, true,
        "Incorrect comparator for DimensionValueMetricPair, queue must retain highest metric values");
  }

}
 

public void dfs(int k,
                float threshold,
                int node,
                float score,
                MinMaxPriorityQueue<Pair<Float, Integer>> heap,
                Vector hidden) {
  if (score < stdLog(threshold)) return;
  if (heap.size() == k && score < heap.peekLast().first()) {
    return;
  }
  if (tree[node].left == -1 && tree[node].right == -1) {
    heap.add(new Pair<>(score, node));
    if (heap.size() > k) {
      Pair<Float, Integer> p = heap.pollLast();
    }
    return;
  }
  float f;
  if (quant && args.getQOut()) {
    f = qwo.dotRow(hidden, node - osz);
  } else {
    f = wo.dotRow(hidden, node - osz);
  }
  f = 1f / (1f + (float) Math.exp(-f));
  dfs(k, threshold, tree[node].left, score + stdLog(1.0f - f), heap, hidden);
  dfs(k, threshold, tree[node].right, score + stdLog(f), heap, hidden);
}
 

@Override
public void evaluateLink(LinkRelevance link) {
    if (link.getRelevance() > minRelevance) {
        String domainName = link.getTopLevelDomainName();
        MinMaxPriorityQueue<LinkRelevance> domainQueue = topkLinksPerDomain.get(domainName);
        if (domainQueue == null) {
            domainQueue = newPriorityQueue(MAX_LINKS_PER_DOMAIN);
            topkLinksPerDomain.put(domainName, domainQueue);
        }
        domainQueue.add(link);
    }
}
 

@Override
protected void cleanup(Context context) throws IOException, InterruptedException {

  for (String dimension : dimensionNames) {

    LOGGER.info("{} records passed metric threshold for dimension {}", thresholdPassCount.get(dimension), dimension);

    // Get top k
    TopKDimensionToMetricsSpec topkSpec = topKDimensionToMetricsSpecMap.get(dimension);
    if (topkSpec != null && topkSpec.getDimensionName() != null && topkSpec.getTopk() != null) {

      // Get top k for each metric specified
      Map<String, Integer> topkMetricsMap = topkSpec.getTopk();
      for (Entry<String, Integer> topKEntry : topkMetricsMap.entrySet()) {

        String metric = topKEntry.getKey();
        int k = topKEntry.getValue();
        MinMaxPriorityQueue<DimensionValueMetricPair> topKQueue = MinMaxPriorityQueue.maximumSize(k).create();

        Map<Object, Number[]> dimensionToMetricsMap = dimensionNameToValuesMap.get(dimension);
        for (Entry<Object, Number[]> entry : dimensionToMetricsMap.entrySet()) {
          topKQueue.add(new DimensionValueMetricPair(entry.getKey(), entry.getValue()[metricToIndexMapping.get(metric)]));
        }
        LOGGER.info("Picking Top {} values for {} based on Metric {} : {}", k, dimension, metric, topKQueue);
        for (DimensionValueMetricPair pair : topKQueue) {
          topkDimensionValues.addValue(dimension, String.valueOf(pair.getDimensionValue()));
        }
      }
    }
  }

  if (topkDimensionValues.getTopKDimensions().size() > 0) {
    String topkValuesPath = configuration.get(TOPK_PHASE_OUTPUT_PATH.toString());
    LOGGER.info("Writing top k values to {}",topkValuesPath);
    FSDataOutputStream topKDimensionValuesOutputStream = fileSystem.create(
        new Path(topkValuesPath + File.separator + ThirdEyeConstants.TOPK_VALUES_FILE));
    OBJECT_MAPPER.writeValue((DataOutput) topKDimensionValuesOutputStream, topkDimensionValues);
    topKDimensionValuesOutputStream.close();
  }
}
 

@Test
public void givenMinMaxPriorityQueue_whenAddElementToFull_thenShouldEvictGreatestItem() {
    //given
    MinMaxPriorityQueue<CustomClass> queue = MinMaxPriorityQueue
            .orderedBy(Comparator.comparing(CustomClass::getValue))
            .maximumSize(10)
            .create();

    //when
    IntStream
            .iterate(10, i -> i - 1)
            .limit(10)
            .forEach(i -> queue.add(new CustomClass(i)));

    //then
    assertThat(queue.peekFirst().getValue()).isEqualTo(1);
    assertThat(queue.peekLast().getValue()).isEqualTo(10);


    //and
    queue.add(new CustomClass(-1));


    //then
    assertThat(queue.peekFirst().getValue()).isEqualTo(-1);
    assertThat(queue.peekLast().getValue()).isEqualTo(9);

    //and
    queue.add(new CustomClass(100));
    assertThat(queue.peekFirst().getValue()).isEqualTo(-1);
    assertThat(queue.peekLast().getValue()).isEqualTo(9);

}