Почему метод, основанный на потоках, так долго длится до 1000 *? - PullRequest
Новая
       77

Почему метод, основанный на потоках, так долго длится до 1000 *?

2 голосов
/ 17 января 2020

Я проводил некоторые практические тесты в HackerRank и в какой-то момент решил решить его, используя только потоки (как личный вызов). Я это сделал. Программа работает в общем. Однако, когда дело доходит до больших объемов данных , для которых требуется go больше, программе требуется long время, чтобы сделать это. Из-за этого, в конечном итоге, я не решил тест из-за «Завершено из-за тайм-аута :(». И я полностью согласен. Когда я запускаю эту программу на своем собственном P C, не только долго sh, но температура моего процессора взлетела во время работы ...

Вот код, который я создал: 

List<Integer> duplicatesCount = arr.stream()
        .map(x -> Collections.frequency(arr, x))
        .collect(Collectors.toList());
OptionalInt maxDuplicate = duplicatesCount.stream().mapToInt(Integer::intValue).max();
Set<Integer> duplicates = arr.stream()
        .filter(x -> Collections.frequency(arr, x) == maxDuplicate.getAsInt())
        .collect(Collectors.toSet());
OptionalInt result = duplicates.stream().mapToInt(Integer::intValue).min();
return result.getAsInt();

Может кто-нибудь объяснить мне это? сильная нагрузка на процессор? Или это только эта программа?

PS. Данные, о которых я упоминал выше (те, которые эта программа не может обработать) имели 73966 цифр от 1 до 5. Если это важно или кого-то интересует ...

1 Ответ

8 голосов
/ 18 января 2020

duplicatesCount подсчитывается путем итерации всего массива для каждого элемента в массиве, то есть это квадратичное значение c.

Итак, для обработки массива из 73 966 элементов вы выполняете 5 470 969 156 сравнений. Это довольно много. 

Map<Integer, Long> freqs = arr.stream().collect(groupingBy(a -> a, counting()))

будет гораздо более эффективным способом подсчета частоты каждого элемента. Это примерно так же, как: 

Map<Integer, Long> freqs = new HashMap<>();
for (Integer i : arr) {
  freqs.merge(i, 1L, Long::sum);
}

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

Затем, похоже, что вы ищете наименьшее число с максимальная частота: 

int minNum = 0;
long maxFreq = 0;
for (Entry<Integer, Long> e : freqs.entrySet()) {
  if (e.getValue() > maxFreq) {
    minNum = e.getKey();
    maxFreq = e.getValue();
  } else if (e.getValue() == maxFreq) {
    minNum = Math.min(minNum, e.getKey());
  }
}
return minNum;

Вы можете сделать это и с лямбдами: 

return Collections.max(freqs.entrySet(),
    Comparator.<Entry<Integer, Long>>comparingLong(Entry::getKey).thenComparing(Comparator.<Entry<Integer, Key>>comparingInt(Entry::getValue).reversed())).getKey();

, но я думаю, что императивный путь более ясен.

Это все работает за линейное время .

...