Java 8 中的批量排序列表与优先级队列性能

Question

我在Java 8中实现了扫描线算法，其中我遍历按数字键(例如，矩形的"xlo"坐标)排序的对象集合。 目前，我正在使用PriorityQueue<item>( key-extractor )实现这一点。 不过，我意识到我并没有真正使用PriorityQueue的全部功能(穿插添加、删除和窥视/投票的能力)，而只是在执行开始时添加项目，然后继续查看/轮询它们稍后(没有进一步的插入或删除)。 因此，我正在考虑用一个简单的Queue<item>替换PriorityQueue，填充它，对其进行排序，然后从前面查看/轮询项目。

我将尝试按照这些思路修改我的代码，但在我这样做之前，我想知道我可以通过替换节省多少。 从形式上讲，这两种方法的复杂性似乎是等效的，但我怀疑常数存在显着差异。 建议？

Answer 1

谢谢，@pjs，你的建议。 我使用一个简单的类Number来强制 排序以像我的应用程序一样使用访问器方法。 以下是 1000 次试验的结果 添加/排序/检索各种数量的Number使用PriorityQueue<Number>、一个ArrayList<Number>(具有显式排序)和一个Numbers数组(显式排序);数字以秒为单位：

For 1000 trials    PriorityQueue   ArrayList    Array
n=100              0.021           0.024        0.033
n=1000             0.220           0.203        0.205
n=10000            3.157           2.772        2.751

所以，答案是"视情况而定"。 对于收藏中的少数Number，PriorityQueue是赢家。 对于较大的数字，数组是赢家。

这是我使用的代码;请注意，我重复了所有试验两次，以使 JIT 发挥其魔力，并报告了第二次重复的时间。

public class Benchmark {
static private final int n = 10000;  // Number of Numbers
static private final int r = 1000; // Number of repetitions
static private Random rand = new Random();
static private class Number {
private int i;
public Number( int i ) { this.i = i; }
public int getNumber() { return i; }
}
static private PriorityQueue< Number > 
sortedNumbersPQ = new PriorityQueue< Number >( Comparator.comparing( Number::getNumber ) );
static private List< Number > sortedNumbersAL = new ArrayList<>();
static private Number[] sortedNumbersAR = new Number[ n ];
static private int usePriorityQueue( int[] numbers ) {
int sum = 0;
for ( int i = 0; i < numbers.length; i++ )
sortedNumbersPQ.add( new Number( numbers[ i ] ) );
while ( ! sortedNumbersPQ.isEmpty() )
sum += sortedNumbersPQ.poll().getNumber();
return sum;
}
static private int useArrayList( int[] numbers ) {
int sum = 0;
sortedNumbersAL.clear();
for ( int i = 0; i < numbers.length; i++ )
sortedNumbersAL.add( new Number( numbers[ i ] ) );
Collections.sort( sortedNumbersAL, Comparator.comparing( Number::getNumber ) );
for ( int i = 0; i < numbers.length; i++ )
sum += sortedNumbersAL.get( i ).getNumber();
return sum;
}
static private int useArray( int[] numbers ) {
int sum = 0;
for ( int i = 0; i < numbers.length; i++ )
sortedNumbersAR[ i ] = new Number( numbers[ i ] );
Arrays.sort( sortedNumbersAR, 0, numbers.length, Comparator.comparing( Number::getNumber ) );
for ( int i = 0; i < numbers.length; i++ )
sum += sortedNumbersAL.get( i ).getNumber();
return sum;
}
static public void main( String args[] ) {
int[] numbers = new int[ n ];
for ( int i = 0; i < n; i++ )
numbers[ i ] = rand.nextInt( 1000000 );
long start = System.currentTimeMillis();
for ( int i = 0; i < r; i++ )
usePriorityQueue( numbers );
System.err.println( "Using PriorityQueue for " + r + " repeats of " + n + " items: " + 
0.001 * ( System.currentTimeMillis() - start ) );
start = System.currentTimeMillis();
for ( int i = 0; i < r; i++ )
useArrayList( numbers );
System.err.println( "Using ArrayList for " + r + " repeats of " + n + " items: " + 
0.001 * ( System.currentTimeMillis() - start ) );
start = System.currentTimeMillis();
for ( int i = 0; i < r; i++ )
useArray( numbers );
System.err.println( "Using Array for " + r + " repeats of " + n + " items: " + 
0.001 * ( System.currentTimeMillis() - start ) );
start = System.currentTimeMillis();
for ( int i = 0; i < r; i++ )
usePriorityQueue( numbers );
System.err.println( "Using PriorityQueue for " + r + " repeats of " + n + " items: " + 
0.001 * ( System.currentTimeMillis() - start ) );
start = System.currentTimeMillis();
for ( int i = 0; i < r; i++ )
useArrayList( numbers );
System.err.println( "Using ArrayList for " + r + " repeats of " + n + " items: " + 
0.001 * ( System.currentTimeMillis() - start ) );
start = System.currentTimeMillis();
for ( int i = 0; i < r; i++ )
useArray( numbers );
System.err.println( "Using Array for " + r + " repeats of " + n + " items: " + 
0.001 * ( System.currentTimeMillis() - start ) );
}
}