nl_tokens: Quickselects the top k elements from the 2k elements in the buffer . O ( k ) expected time O ( k log k ) worst case .
pl_tokens: private void trim ( ) { int left = 0 ; int right = 2 * k - 1 ; int minThresholdPosition = 0 ; // The leftmost position at which the greatest of the k lower elements // -- the new value of threshold -- might be found. int iterations = 0 ; int maxIterations = IntMath . log2 ( right - left , RoundingMode . CEILING ) * 3 ; while ( left < right ) { int pivotIndex = ( left + right + 1 ) >>> 1 ; int pivotNewIndex = partition ( left , right , pivotIndex ) ; if ( pivotNewIndex > k ) { right = pivotNewIndex - 1 ; } else if ( pivotNewIndex < k ) { left = Math . <mask> ( pivotNewIndex , left + 1 ) ; minThresholdPosition = pivotNewIndex ; } else { break ; } iterations ++ ; if ( iterations >= maxIterations ) { // We've already taken O(k log k), let's make sure we don't take longer than O(k log k). Arrays . sort ( buffer , left , right , comparator ) ; break ; } } bufferSize = k ; threshold = buffer [ minThresholdPosition ] ; for ( int i = minThresholdPosition + 1 ; i < k ; i ++ ) { if ( comparator . compare ( buffer [ i ] , threshold ) > 0 ) { threshold = buffer [ i ] ; } } }