Каков самый быстрый способ подвести список Interger

Question

Я пытался выяснить, что самый быстрый способ подвести список целых чисел.

Прежде всего я создал метод, который обеспечивает SampleData:

public static List<Integer> getIntList(int size) { 
    LinkedList<Integer> sampleList = new LinkedList<>(); 
    Random rand = new Random(); 
    rand.ints(size).forEach((num)-> sampleList.add(num)); 
    return sampleList; 
} 

Тогда я судимое несколько различных способов, чтобы подвести итог списка. Прежде всего наихудшего:

public static void sumUpWithForLoop(List<Integer> data) { 
    System.out.println("For-loop:"); 
    long start = System.currentTimeMillis(); 
    int listLenght = data.size(); 
    int total = 0; 
    for (int i = 0; i < listLenght; i++) { 
     total += data.get(i); 
    } 
    long end = System.currentTimeMillis(); 
    System.out.println("Result: " + total); 
    System.out.println("Duration: " + (end - start) + "ms"); 
} 

После запуска этого класса я заметил, что это очень медленно, потому что он всегда использует get(index), который занимает довольно много времени.

Из-за этого я судимое подытожить список с итератора

public static void sumUpWithItterator(List<Integer> data) { 
    System.out.println("Iterator:"); 
    long start = System.currentTimeMillis(); 
    int total = 0; 
    for (Integer num : data) { 
     total += num; 
    } 
    long end = System.currentTimeMillis(); 
    System.out.println("Result: " + total); 
    System.out.println("Duration: " + (end - start) + "ms"); 
} 

Этот метод является самым быстрым способом подвести итог Integer-List до сих пор, но я до сих пор пытаются найти более быстрый один. Я также судимый использовать .stream() и .parallelStream():

public static void sumUpWithNormalStream(List<Integer> data) { 
    System.out.println("Stream"); 
    long start = System.currentTimeMillis(); 
    int total = data.stream().mapToInt(num -> num).sum(); 
    long end = System.currentTimeMillis(); 
    System.out.println("Result: " + total); 
    System.out.println("Duration: " + (end - start) + "ms"); 
} 
public static void sumUpWithParallelStream(List<Integer> data) { 
    System.out.println("ParallelStream"); 
    long start = System.currentTimeMillis(); 
    int total = data.parallelStream().mapToInt(num->num).sum(); 
    long end = System.currentTimeMillis(); 
    System.out.println("Result: " + total); 
    System.out.println("Duration: " + (end - start) + "ms"); 
} 

Нормальный stream почти так же быстро, как итератор, в то время как parallelStream гораздо медленнее, чем итератор. Я предполагаю, что это связано с накладными расходами на параллелизацию и тем фактом, что подведение итогов List - это операция, которая выполняется довольно быстро и не требует ждать таких операций, как операции с базами данных.

В целом мне все еще не нравится текущий метод, но я еще не нашел более быстрый. Есть ли у вас идеи, что может быть быстрее обычного Итератора для подведения итогов.

Благодарим вас за ваши предложения.

Answer 1

В вашем примере доступ к памяти, вероятно, является узким местом, поскольку добавление целого является очень быстрой операцией, но для доступа к следующему элементу связанного списка требуется два обращения к памяти (один для получения следующего узла и второй для доступа к целочисленному типу стирания типа невозможно для использования unboxed value). Имейте в виду, что связанный список, вероятно, разбросан по памяти, поэтому существует большая вероятность промаха в кэше.

Чтобы ускорить работу, вы должны уменьшить накладные расходы памяти. Переход от LinkedList к ArrayList приведет к удалению единого доступа (к случайному местоположению в памяти). Переход от ArrayList к необработанному массиву приведет к удалению второго, потому что в этом случае целые числа unboxed будут сохранены в памяти.

Таким образом, версия на основе int[] должна быть самой быстрой (однако менее гибкой, чем версия ArrayList<Integer>).

Answer 2

Использование ArrayList<Integer> вместо LinkedList<integer> скорее всего даст вам лучшие результаты. И поскольку доступ к элементам один за другим наиболее быстрый, когда эти элементы хранятся рядом друг с другом в ОЗУ, попробуйте использовать int[].

В целом, если вы хотите повысить производительность любой программы, попробуйте заменить любые вызовы функций или код высокого уровня с помощью итераций и кода низкого уровня. Это должно значительно повысить производительность.