javax.annotation.OverridingMethodsMustInvokeSuper#com.google.common.collect.MinMaxPriorityQueue源码实例Demo

private void predict(List<Integer> words, List<FastTextPrediction> predictions, int k, float threshold) {
  if (!words.isEmpty()) {
    Vector hidden = new Vector(args.getDimension());
    Vector output = new Vector(dict.nLabels());
    MinMaxPriorityQueue<Pair<Float, Integer>> modelPredictions = MinMaxPriorityQueue
      .orderedBy(new Model.HeapComparator<Integer>())
      .expectedSize(dict.nLabels())
      .create();
    int[] input = Ints.toArray(words);
    if (words.isEmpty()) {
      return;
    }
    model.predict(input, k, threshold, modelPredictions, hidden, output);
    while (!modelPredictions.isEmpty()) {
      Pair<Float, Integer> pred = modelPredictions.pollFirst();
      predictions.add(new FastTextPrediction(dict.getLabel(pred.last()), pred.first()));
    }
  }
}
 

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");
  }

}
 

@Override
public ResultEntry peek() {
    if (mergedQueue == null) {
        mergedQueue = MinMaxPriorityQueue.<ResultEntry> orderedBy(
                comparator).maximumSize(queues.size()).create();
        for (MappedByteBufferPriorityQueue queue : queues) {
            try {
                IndexedResultEntry next = queue.getNextResult();
                if (next != null) {
                    mergedQueue.add(next);
                }
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }
    if (!mergedQueue.isEmpty()) {
        IndexedResultEntry re = mergedQueue.peekFirst();
        if (re != null) {
            return re;
        }
    }
    return null;
}
 

protected Map<String, Long> getTopElements(Map<String, Long> countMap) {
    MinMaxPriorityQueue<Map.Entry<String, Long>> topQueue = MinMaxPriorityQueue
            .orderedBy(Comparator.comparing((Function<Map.Entry<String, Long>, Long>) Map.Entry::getValue).reversed())
            .maximumSize(topSize)
            .create(countMap.entrySet());

    return topQueue.stream().collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
}
 

public void predict(int[] input,
                    int k,
                    float threshold,
                    MinMaxPriorityQueue<Pair<Float, Integer>> heap,
                    Vector hidden,
                    Vector output) {
  Preconditions.checkArgument(k > 0);
  computeHidden(input, hidden);
  if (args.getLoss().equals(Args.LossName.HS)) {
    dfs(k, threshold, 2 * osz - 2, 0.0f, heap, hidden);
  } else {
    findKBest(k, threshold, heap, hidden, output);
  }
}
 

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);
}
 

protected Map<String, Long> getTopElements(Map<String, Long> countMap) {
    MinMaxPriorityQueue<Map.Entry<String, Long>> topQueue = MinMaxPriorityQueue
            .orderedBy(Comparator.comparing((Function<Map.Entry<String, Long>, Long>) Map.Entry::getValue).reversed())
            .maximumSize(topSize)
            .create(countMap.entrySet());

    return topQueue.stream().collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
}
 

public MonoReilSolver(final IInstructionGraph instructionGraph,
    final AnalysisDirection analysisDirection, final ILattice<LatticeElementType> lattice) {
  m_graph = Preconditions.checkNotNull(instructionGraph,
      "Error: instruction graph argument can not be null");
  m_direction = Preconditions.checkNotNull(analysisDirection,
      "Error: analysis direction argument can not be null");
  m_lattice = Preconditions.checkNotNull(lattice, "Error: latice argument can not be null");

  m_workList = MinMaxPriorityQueue.expectedSize(m_graph.size()).create();
}
 

@Override
protected List<ConfigIssue> init() {
  // Validate configuration values and open any required resources.
  List<ConfigIssue> issues = gcsOriginConfig.init(getContext(), super.init());
  minMaxPriorityQueue = MinMaxPriorityQueue.orderedBy((Blob o1, Blob o2) -> {
    int result = o1.getUpdateTime().compareTo(o2.getUpdateTime());
    if(result != 0) {
      return result;
    }
    //same modified time. Use generatedid (bucket/blob name/timestamp) to sort
    return o1.getGeneratedId().compareTo(o2.getGeneratedId());
  }).maximumSize(gcsOriginConfig.maxResultQueueSize).create();
  antPathMatcher = new AntPathMatcher();

  gcsOriginConfig.credentials.getCredentialsProvider(getContext(), issues)
      .ifPresent(p -> credentialsProvider = p);

  try {
    storage = StorageOptions.newBuilder()
        .setCredentials(credentialsProvider.getCredentials())
        .build()
        .getService();
  } catch (IOException e) {
    LOG.error("Error when initializing storage. Reason : {}", e);
    issues.add(getContext().createConfigIssue(
        Groups.CREDENTIALS.name(),
        "gcsOriginConfig.credentials.credentialsProvider",
        Errors.GCS_01,
        e
    ));
  }

  rateLimitElEval = FileRefUtil.createElEvalForRateLimit(getContext());
  rateLimitElVars = getContext().createELVars();
  errorBlobHandler = new GcsObjectPostProcessingHandler(storage, gcsOriginConfig.gcsOriginErrorConfig);
  return issues;
}
 

public MappedByteBufferResultEntryPriorityQueue(int index,
        int thresholdBytes, int limit, Comparator<ResultEntry> comparator) {
    super(index, thresholdBytes, limit >= 0);
    this.results = limit < 0 ? 
            MinMaxPriorityQueue.<ResultEntry> orderedBy(comparator).create()
          : MinMaxPriorityQueue.<ResultEntry> orderedBy(comparator).maximumSize(limit).create();
}
 

private void initMergedQueue() {
    if (mergedQueue == null && currentIndex >= 0) {
        mergedQueue = MinMaxPriorityQueue.<MappedByteBufferSegmentQueue<T>> orderedBy(
                getSegmentQueueComparator()).maximumSize(currentIndex + 1).create();
        for (MappedByteBufferSegmentQueue<T> queue : getSegmentQueues()) {
            T re = queue.peek();
            if (re != null) {
                mergedQueue.add(queue);
            }
        }
    }        
}
 

@Override
public void startSelection(int numberOfLinks) {
    this.topkLinks = MinMaxPriorityQueue
            .orderedBy(LinkRelevance.DESC_ORDER_COMPARATOR)
            .maximumSize(numberOfLinks) // keep only top-k items
            .create();
}
 

@Override
public void startSelection(int numberOfLinks) {
    links = MinMaxPriorityQueue
        .orderedBy(new Comparator<RandomLink>() {
            @Override
            public int compare(RandomLink o1, RandomLink o2) {
                return Double.compare(o1.relevance, o2.relevance);
            }
        })
        .maximumSize(numberOfLinks) // keep only top-k items
        .create();
}
 

@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);
    }
}
 

public List<TranslationCandidate> alignDistributional(TermService sourceTerm, int nbCandidates,
		int minCandidateFrequency) {
	Queue<TranslationCandidate> alignedCandidateQueue = MinMaxPriorityQueue.maximumSize(nbCandidates).create();
	ContextVector sourceVector = sourceTerm.getContext();
	if(sourceVector == null)
		return new ArrayList<>();
	ContextVector translatedSourceVector = translateVector(
			sourceVector,
			dico,
			TRANSLATION_STRATEGY_MOST_SPECIFIC,
			targetTermino);
	ExplainedValue v;
	int nbVectorsNotComputed = 0;
	int nbVectorsComputed = 0;
	for(TermService targetTerm:targetTermino.terms().filter(TermService::isSingleWord).collect(Collectors.toList())) {
		if(targetTerm.getFrequency() < minCandidateFrequency)
			continue;
		if(targetTerm.getContext() != null) {
			nbVectorsComputed++;
			v = distance.getExplainedValue(translatedSourceVector, targetTerm.getContext());
			TranslationCandidate candidate = new TranslationCandidate(
					AlignmentMethod.DISTRIBUTIONAL,
					targetTerm, 
					v.getValue(), 
					sourceTerm,
					v.getExplanation());
			alignedCandidateQueue.add(candidate);
		}
	};
	if(nbVectorsNotComputed > 0) {
		LOGGER.warn(MSG_SEVERAL_VECTORS_NOT_COMPUTED, nbVectorsComputed, nbVectorsNotComputed);	
	}
	
	// sort alignedCandidates
	List<TranslationCandidate> alignedCandidates = Lists.newArrayListWithCapacity(alignedCandidateQueue.size());
	alignedCandidates.addAll(alignedCandidateQueue);
	normalizeCandidateScores(alignedCandidates);
	return Lists.newArrayList(alignedCandidateQueue);
}
 

public static SizeAwareQueue<ResultEntry> newSizeBoundResultEntrySortedQueue(
        Comparator<ResultEntry> comparator, Integer limit, long maxSizeBytes) {
    limit = limit == null ? -1 : limit;
    MinMaxPriorityQueue<ResultEntry> queue =
            limit < 0 ? MinMaxPriorityQueue.<ResultEntry> orderedBy(comparator).create()
                    : MinMaxPriorityQueue.<ResultEntry> orderedBy(comparator).maximumSize(limit)
                            .create();
    return new SizeBoundQueue<ResultEntry>(maxSizeBytes, queue) {
        @Override
        public long sizeOf(org.apache.phoenix.iterate.OrderedResultIterator.ResultEntry e) {
            return ResultEntry.sizeOf(e);
        }

    };
}
 

private void initMergedQueue() {
    if (mergedQueue == null && currentIndex >= 0) {
        mergedQueue = MinMaxPriorityQueue.<BufferedSegmentQueue<T>> orderedBy(
                getSegmentQueueComparator()).maximumSize(currentIndex + 1).create();
        for (BufferedSegmentQueue<T> queue : getSegmentQueues()) {
            T re = queue.peek();
            if (re != null) {
                mergedQueue.add(queue);
            }
        }
    }        
}
 

public BufferedResultEntryPriorityQueue(int index,
        long thresholdBytes, int limit, Comparator<ResultEntry> comparator) {
    super(index, thresholdBytes, limit >= 0);
    this.results = limit < 0 ? 
            MinMaxPriorityQueue.<ResultEntry> orderedBy(comparator).create()
          : MinMaxPriorityQueue.<ResultEntry> orderedBy(comparator).maximumSize(limit).create();
}
 

@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();
  }
}
 

public MappedByteBufferPriorityQueue(int index, int limit, int thresholdBytes,
        Comparator<ResultEntry> comparator) throws IOException {
    this.index = index;
    this.limit = limit;
    this.thresholdBytes = thresholdBytes;
    results = limit < 0 ? 
            MinMaxPriorityQueue.<ResultEntry> orderedBy(comparator).create()
          : MinMaxPriorityQueue.<ResultEntry> orderedBy(comparator).maximumSize(limit).create();
}
 

@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);

}
 

public void predict(int[] input, int k, float threshold, MinMaxPriorityQueue<Pair<Float, Integer>> heap) {
  predict(input, k, threshold, heap, hidden, output);
}
 

CellNoDynamicProgram(int nbest) {
	this.entries = MinMaxPriorityQueue.maximumSize(nbest).create();
}
 

@Override
public SearchResultBatch search(String searchTerm, int maxResults) {
    Stopwatch stopwatch = Stopwatch.createStarted();

    ParsedDocument searchDocument = searchTermParser.parseDocument(new Document(searchTerm, new Object()));
    Set<ParsedDocument> documentsToScanSet = getRelevantDocuments(searchDocument);

    if (searchDocument.isEmpty() || documentsToScanSet.isEmpty()) {
        return buildResultBatch(new ArrayList<SearchResult>(), stopwatch, 0);
    }

    // do scan
    final Collection<SearchResult> resultsP = new ConcurrentLinkedQueue<>();

    List<ParsedDocument> documentsToScan = new ArrayList<>(documentsToScanSet);
    final ParsedDocumentMetrics pdm = new ParsedDocumentMetrics(corpus, searchDocument, termToPostings);
    List<Future> futures = new ArrayList<>();

    for (final List<ParsedDocument> partition : Lists.partition(documentsToScan, THREAD_POOL_SIZE)) {

        Future future = executorService.submit(new Runnable() {
            @Override
            public void run() {
                for (ParsedDocument doc : partition) {
                    double cosine = computeCosine(pdm, doc);

                    SearchResult result = new SearchResult();
                    result.setRelevanceScore(cosine);
                    result.setUniqueIdentifier(doc.getUniqueId());
                    resultsP.add(result);
                }
            }
        });

        futures.add(future);
    }

    for (Future f : futures) {
        try {
            f.get();
        } catch (Exception ex) {
            throw new RuntimeException(ex);
        }
    }

    int heapSize = Math.min(resultsP.size(), maxResults);

    MinMaxPriorityQueue<SearchResult> maxHeap = MinMaxPriorityQueue.
            orderedBy(new Comparator<SearchResult>() {
                @Override
                public int compare(SearchResult o1, SearchResult o2) {
                    if (o1.getRelevanceScore() <= o2.getRelevanceScore()) {
                        return 1;
                    } else {
                        return -1;
                    }
                }
            }).
            maximumSize(heapSize).
            expectedSize(heapSize).create(resultsP);


    // return results
    ArrayList<SearchResult> r = new ArrayList<>();
    while (!maxHeap.isEmpty()) {
        SearchResult rs = maxHeap.removeFirst();
        r.add(rs);
    }

    return buildResultBatch(r, stopwatch, documentsToScan.size());
}
 

private MinMaxPriorityQueue<LinkRelevance> newPriorityQueue(int maxSize) {
    return MinMaxPriorityQueue
            .orderedBy(LinkRelevance.DESC_ORDER_COMPARATOR)
            .maximumSize(maxSize)
            .create();
}