Массово отсортированный список в зависимости от производительности очереди приоритетов в Java 8 - PullRequest
Новая
       53

Массово отсортированный список в зависимости от производительности очереди приоритетов в Java 8

0 голосов
/ 27 октября 2019

Я реализую алгоритм строчной линии в Java 8, в котором я просматриваю коллекцию объектов, отсортированных по числовому ключу (например, координата "xlo" прямоугольника). В настоящее время я реализую это с помощью PriorityQueue<item>( key-extractor ). Тем не менее, я понимаю, что на самом деле я не использую полную функциональность PriorityQueue (возможность чередовать добавления, удаления и просмотра / опроса), а только добавляю элементы в начале выполнения, а затем перехожу к просмотру / опросу. их позже (без дальнейших вставок или удалений). Поэтому я подумываю заменить PriorityQueue простым Queue<item>, заполнить его, отсортировать, а затем посмотреть / опросить элементы спереди.

Я собираюсь попытаться изменить свой код в соответствии с этим, но прежде чем я это сделаю, я задаюсь вопросом, сколько я мог бы ожидать сэкономить путем замены. Формально кажется, что сложность двух подходов эквивалентна, но я подозреваю, что константа существенно отличается. Предложения

1 Ответ

1 голос
/ 27 октября 2019

Спасибо, @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 ) );
    }
}
...