Как выполнить асимптотический анализ кода, использующего API потоков JDK? - PullRequest
Новая
       4

Как выполнить асимптотический анализ кода, использующего API потоков JDK?

0 голосов
/ 13 октября 2018

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

Но, более конкретно, этот код истекает на конкурентном сайте программирования.

Это находитчастота появления чисел от 0 до 100 в потоке.Числа в массиве находятся между 0 и 100. 

    // Times out with int[] array containing 100000 elements.

    List<Integer> l = new ArrayList<>();
    for( int i = 0 ; i < array.length ; i ++){
        l.add(array[i]);
    }

    int[] counts = new int[100];
    Arrays.stream(array).forEach( i -> counts[i] = Collections.frequency( l, i));

Что такое анализ Big-O для этого кода?Я предполагаю, что виновником является то, как я использую Streams API.

Ответы [ 2 ]

0 голосов
/ 13 октября 2018

Что такое анализ Big-O для этого кода?

  • Нет оснований полагать, что стоимость Arrays.stream() сама по себе масштабируется в зависимости от размера проблемы..
  • Stream.forEach() ограничен n * K , где n - размер массива и K - асимптотическая сложность лямбды.Ваше конкретное использование не приведет к сокращению итерации, поэтому нет оснований ожидать более жесткой границы
  • Сложность лямбды определяется Collections.frequency(), который линейно масштабируется с размером коллекции, также n , потому что он должен сканировать все это.

В общем, это означает, что O ( n 2 ).

Потеря здесь при сканировании всей коллекции для каждого элемента массива.Поскольку вы ожидаете, что в среднем будет 1000 появлений каждого значения, это очень дорого, и оно масштабируется с количеством элементов массива.Я подозреваю, что вы намеревались вместо этого сканировать только один раз для каждой позиции в count, но даже это было бы довольно расточительно.Можете ли вы придумать способ сбора всех частот за один проход?Подсказка: не задумывайтесь над этим.

0 голосов
/ 13 октября 2018

Вы перебираете все элементы array (размер 100000), в то время как все, что вам нужно сделать, это найти частоту чисел от 0 до 100 (при условии эксклюзивности) в списке, который вы создали, поэтому переберите 100в два раза эффективнее, чем: 

int[] counts = new int[100];
IntStream.range(0,100).forEach(i -> counts[i] = Collections.frequency(l,i));

Кстати, если вы, возможно, итерируете весь массив, чтобы преобразовать его в список, более простой способ сделать это - подсчитать вхожденияэлементы в том же цикле. 

int[] counts = new int[100];
for( int i = 0 ; i < array.length ; i ++){
    counts[array[i]]++; // same asssumption (array[i] < 100)
}

или в виде потоков 

Arrays.stream(array).forEach(i -> counts[i]++);
...