Задача: Как посчитать одинаковые пары за 1 проход (самая быстрая версия!)
Исходник: Параллельная реализация подсчета одинаковых пар чисел через доп массив, язык: java [code #805, hits: 42]
автор: this [добавлен: 06.02.2022]
  1. import java.util.Arrays;
  2. import java.util.OptionalInt;
  3.  
  4. class EqualPairCounter {
  5. int numberOfEqualPairsLinearWithExtraArrayAndStreams(int[] input) {
  6. int max = input[0];
  7. int min = input[0];
  8. for (int v : input) {
  9. max = Math.max(max, v);
  10. min = Math.min(min, v);
  11. }
  12. int shift = min;
  13. int[] countArr = new int[max - min + 1];
  14. for (int v : input) {
  15. int countIdx = v - shift;
  16. countArr[countIdx]++;
  17. }
  18.  
  19. OptionalInt res = Arrays.stream(countArr)
  20. .parallel()
  21. .filter(count -> count > 1)
  22. .map(n -> (n - 1) * n / 2)
  23. .reduce(Integer::sum);
  24.  
  25. return res.orElse(0);
  26. }
  27.  
  28. public static void main(String[] args) {
  29. int[] input = {1, 2, 4, 1, 2, 1, 2, -3, 4, 5, 1, 2, 4, 5, 1, -5, 2 ,5, 6, 7, -3, 7, 8, 2, 1, 2, -3, 4, 5};
  30. int pairCount = new EqualPairCounter().numberOfEqualPairsLinearWithExtraArrayAndStreams(input);
  31. System.out.println("Res: " + pairCount); // => 52
  32. }
  33. }
Многопоточная версия быстрого алгоритма для подсчета одинаковых пар чисел в массиве за линейное время O(n).
Расходуем еще примерно O(n) дополнительной памяти на вспомогательный массив для хранения промежуточных результатов, размер которого всегда меньше (либо равно) длине исходной последовательности/массива.
На конечном этапе подсчета по формуле удалось распараллелить суммарный подсчет путем активации режима parallel() встроенного в Стримы java.
Тестировалось на: java-11-openjdk-amd64 @ubuntu20LTS

+добавить реализацию