Как посчитать одинаковые пары за 1 проход (самая быстрая версия!)

• Можно ли быстрее?
•   За счет чего будем ускорять?
• Хеш-таблица
•   Псевдокод с хеш-таблицей
•   Накладные расходы
•   Код на java с хеш-таблицей
• Инвертированный массив
•   Смещение
•   Псевдокод с доп массивом
•   Код на java
• Выводы
• Все реализации

Можно ли быстрее?

В предыдущей части этой задачи мы рассмотрели сначала квадратичный алгоритм O(N^2), потом ускорили его до линейно-алгорифмичного O(N*Lg(N)).
Давайте поразмыслим напоследок - а можно ли еще быстрее?!
А быстрее это получается уже линейно, т.е. за 1 или несколько проходов по всей последовательности (или массиву), без каких-либо вложенных циклов или рекурсий на каждом шаге.
А в свою очередь получается без сортировки, т.к. только на нее уходит линейно-алгорифмичное время (N*Lg(N)), т.е. без какой-либо сортировки полной или частичной и тд...

Как уже обсуждали - очевидно что нет.

За счет чего будем ускорять?

Но без сортировки - что еще можем сделать?
Правильно - может задействовать какие-то дополнительные структуры данных, но какие и для чего?

Нам же нужно что - "посчитать пары", т.е. в конечном итоге это просто подсчет, поэтому что если в цикле пройтись по массиву и просто посчитать все одинаковые элементы?
Таким образом после этого как и после сортировки мы будем знать какие там одинаковые числа и по скольку раз они повторяются!
Ну а далее понятно что для каждых повторяющихся чисел мы можем применить ту же сокращенную формулу подсчета комбинаций!

Но только какую структуру мы можем для взять для этого подсчета?

Хеш-таблица

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

Хеш-таблица, по другому hash-table или HashMap - структура позволяющая сопоставлять любой Ключ с любым Значением, т.е. можем сохранять туда любые пары ключ-значение. 
2 основные операции Хеш-таблицы которые нам понадобятся: get(Ключ0)  - вернуть Значение по Ключу0 и put(Ключ0, Значение0) - сохранить Значение0 для Ключа0.
И самое ценное что эти самые операции (get/put) благодаря свойствам хеш-таблицы выполняются моментально в большинстве случаев, т.о. не зависят от размерности N и практически занимают константное время ~O(1).

Отлично и как это поможет для нашей задачи? Что мы сможем хранить как ключ а что как значение и что это нам даст?

Поскольку нам сначала нужно просто подсчитать повторения всех чисел во входной последовательности - то очевидно само число можем сохранять как Ключ а сколько раз оно повторяется - хранить как Значение по этому ключу!

Отлично, т.е. мы можем идти в цикле по входным числам и добавлять в нашу Хеш-таблицу это число как Ключ а единицу как Значение НО если там такое уже есть - то просто увеличивать Значение по этому ключу на единицу.
В итоге у нас получится Хеш-Таблица где Ключи - все уникальные числа из входной последовательности а значения - кол-во их повторений, т.е. Значение 1 - если число не повторяется, иначе больше единицы и тд.

Итак, числа подсчитали, ну а дальше - проходимся уже по нашей заполненной Хеш-таблице и для каждого Ключа у которого Значение больше 1 применяем формулу перестановок и увеличиваем итоговое количество Пар.

Псевдокод с хеш-таблицей

Получаем примерно так:

input=<исходный массив N чисел>
countTable = new HashTable
 
// Проходимся по всем числам и сохраняем их кол-во
for (i = 1...N-1) do:
  count = countTable.get(input[i]) // смотрим есть ли уже что по этому числу
  if count is empty? then: // Число еще не добавлено в Таблицу
    count = 0 
 
  count = count + 1
  countTable.put(input[i], count) // Сохраняем текущее число с его количеством
 
// далее проходимся по таблице и по формуле складываем ко-во пар
result = 0
for each key=>value from countTable do:
  if (value > 1) then:
    result = result + (value - 1) * value / 2
 
return result // возвращаем искомое количество

Накладные расходы

Однако следует учитывать что Хеш-таблица как отдельная структура потребляет дополнительную память для хранения своих элементов внутри и ее размер зависит напрямую от размера исходного массива, т.е. дополнительной памяти она потребляет примерно еще на ~O(N), где N - размер входной последовательности.

Но не стоит сильно волноваться поскольку при больших размерностях(N) Хеш-таблица достаточно компактно упаковывает элементы внутри себя и может занимать на порядок меньший размер: например положили туда всего N чисел, а вся хеш-таблица как структура создала внутри себя N/100 или даже N/1000 звеньев (на самом деле там внутри Связный список).

Код на java с хеш-таблицей

На java код довольно простой т.к. имеется встроенная версия хеш-таблицы - это HashMap, и также есть метод getOrDefault который как раз удобно использовать тут:

import java.util.HashMap;
import java.util.Map;
 
class EqualPairCounter {
    int numberOfEqualPairsLinearWithExtraMap(int[] input) {
        int res = 0;
        Map<Integer, Integer> vMap = new HashMap<>();
 
        for (final int v : input) {
            int count = vMap.getOrDefault(v, 0);
            vMap.put(v, ++count);
        }
 
        for(final int v : vMap.keySet()) {
            if (vMap.get(v) > 1) {
                int pairs = vMap.get(v);
                res += (pairs - 1) * pairs / 2;
            }
        }
        return res;
    }
 
    public static void main(String[] args) {
        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};
        int pairCount = new EqualPairCounter().numberOfEqualPairsLinearWithExtraMap(input);
        System.out.println("Res: " + pairCount); // => 52
    }
}

А можем пойти еще дальше и оптимизировать финальный цикл через Стримы (Streams) которые добавили с 8й версии java, также добавим еще режим параллельного выполнения(parallel())  и в результате получим реализацию которая на мощном компьютере с несколькими процессорами будет работать намного быстрее:

import java.util.Arrays;
import java.util.OptionalInt;
 
class EqualPairCounter {
    int numberOfEqualPairsLinearWithExtraArrayAndStreams(int[] input) {
        int max = input[0];
        int min = input[0];
        for (int v : input) {
            max = Math.max(max, v);
            min = Math.min(min, v);
        }
        int shift = min;
        int[] countArr = new int[max - min + 1];
        for (int v : input) {
            int countIdx = v - shift;
            countArr[countIdx]++;
        }
 
        OptionalInt res = Arrays.stream(countArr)
            .parallel()            
            .filter(count -> count > 1)
            .map(n -> (n - 1) * n / 2)
            .reduce(Integer::sum);
 
        return res.orElse(0);
    }
 
    public static void main(String[] args) {
        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};
        int pairCount = new EqualPairCounter().numberOfEqualPairsLinearWithExtraArrayAndStreams(input);
        System.out.println("Res: " + pairCount); // => 52
    }
}

Воу-воу, отлично! С этим подходом через Хеш-таблицу разобрались, довольно несложно получилось, спасибо такой замечательной структуре данных как говорится!
Но что если у нас какой-то экзотический язык программирования где нет встроенных хеш-таблиц, либо какие-то проблемы с их реализациями?
Возможно ли реализовать данный подход без Хеш-таблицы?
Ну, в целом зависит от исходных данных...

Инвертированный массив

Если в исходном массиве у нас только целые числа, то как вариант - инвертированный массив (или по-другому "реверсивный", также будем дальше называть его "массив подсчета"), где индексы соотв-ют элементам а значения - их количеству в исходной последовательности, но только - какого размера он будет?
Ну если последний элемент там будет соответствовать максимальному в исходной последовательности - то и размер будет равен значению этого максимума, т.е. для этого сначала в цикле нужно пройтись по всем исходным элементам просто чтобы посчитать максимальный и определить размер инвертированного массива где будем хранить подсчет.

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

Смещение

Да, именно: с отрицательными числами случится проблемка т.к. индекс массива всегда начинается от нуля и не может быть отрицательным.
Но если немного подумать - это же элементарно решить используя смещение индекса: т.е. будем располагать элементы в реверс-массиве по индексу со смещением начиная с самого минимального отрицательного. Т.е. минимальный отрицательный будет вначале по нулевому индексу а остальные - с аналогичным смещением.
Т.е. величина этого смещения будет равна - чему?

Правильно - размеру минимального отрицательного элемента в нашем массиве, т.е. минимальное отрицательное число будет по нулевому индексу, а остальные элементы - с таким же смещением. 
Например: если у нас -111 минимальное число в нашем массиве, то reverse[0] = -111 а все остальные будут смещены на 111 элементов вперед и таким образом число например 10 будет там по индексу 10+111=121, а число -3 по индексу -3+111=108 и тд. 
А в случае если все числа положительные то смещение можно не использовать, т.е. считать его равным нулю.
При этом минимум найдем в том же начальном цикле вместе в максимумом.

Итак со смещением и размерами разобрались, далее надо  собственно создать этот инвертированный массив и инициировать его нулями, т.е. выделить примерно еще O(N) памяти.
А далее - пройтись еще раз по всем числам и посчитать их все через инвертированный массив, т.е. по каждому числу добавлять в "инверт"-массив единицу по индексу равному этому числу если там ноль, иначе - увеличивать на единицу количество по этому индексу.

Ну а далее, подсчитав повторения всех чисел - дальше уже можно применить частный случай формулы перестановок и быстро посчитать все пары.

Псевдокод с доп массивом

Итак, наш алгоритм разбивается на несколько этапов:

1. Пройтись по всем числам чтобы найти минимум/максимум
2. Рассчитать смещение и длину инверт-массива, создать/инициировать его (нулями)
3. Пройтись 2й раз по всем исходным числам, записывая их количество в инверт-массив подсчета
4. Пройтись финально по инверт-массиву и там где значения >1 посчитать по формуле перестановок.

Т.о. получаем примерно такой псевдокод:

input=<исходный массив N чисел>
// сначала ищем максимальный элемент
max = input[0]
min = input[0]
for (i = 1...N-1) do:
  if (input[i] > max) then:
    max = input[i]
 
  if (input[i] < min) then:
    min = input[i]
 
// определяем смещение 
shift = min
 
// создаем реверс-массив
countArrSz = max - min + 1
countArr = new array size of [countArrSz]
 
// заполняем его нулями на начальном этапе
for (j = 0...countArrSz) do:
  countArr[j] = 0
 
// далее проходимся по всем числам и подсчитываем одинаковые
for (i = 0...N-1) do:
  v = input[i]
  countIndex = v - shift
  countArr[countIndex] = countArr[countIndex] + 1
 
// В конце по формуле перестановок считаем 
result = 0
for (j = 0...countArrSz) do:
  count = countArr[j]
  if (count > 1) then:
    result = result + (count - 1) * count / 2
 
return result // возвращаем искомое количество

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

Код на java

Итого на языке программирования Java код реализации будет выглядеть как:

class EqualPairCounter {
    int numberOfEqualPairsLinearWithExtraArray(int[] input) {
        int max = input[0];
        int min = input[0];
        for (int v : input) {
            max = Math.max(max, v);
            min = Math.min(min, v);
        }
        int shift = min;
        int[] countArr = new int[max - min + 1];
        for (int v : input) {
            int countIdx = v - shift;
            countArr[countIdx]++;
        }
 
        int res = 0;
        for(int count : countArr) {
            if (count > 1) {
                res += (count - 1) * count / 2;
            }
        }
 
        return res;
    }
 
    public static void main(String[] args) {
        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};
        int pairCount = new EqualPairCounter().numberOfEqualPairsLinearWithExtraArray(input);
        System.out.println("Res: " + pairCount); // => 52
    }
}

Аналогично финальный подсчет можно переписать через  Java Стримы (Streams) где присутствует встроенная опция параллельности (.parallel()) и в итоге получаем многопоточную версию из без того Быстрого алгоритма подсчета пар.

Выводы

Мы рассмотрели 2 варианта самого быстрого алгоритма подсчета одинаковых пар за линейное время O(n), оба потребляют дополнительную память для хранения промежуточных результатов, первый - на основе эффективной структуры данных Хеш-таблица, которая обеспечивает почти всегда моментальный доступ к элементам, позволяет работать с любыми входными данными и немного экономит расход дополнительной памяти, второй же - на основе самописного инверт (реверс) массива выполняющего туже задачу самым примитивным образом но который поддерживает только целые числа в качестве входных данных.

Реализации:

заполните необходимые поля!

название:
uri-имя*:
заголовок окна:
ЯП:	[другой...] pseudojavajavascriptpythonC++C#CphpGoqbasicrailsrubysmartytsqlvbnetvisualfoxproxmlactionscriptplsqlpascaloracle8sqlvbfortransmalltalkasmcssdelphigroovylispperlmysqlmatlab
код (double click - редактирование) (Esc - предпросмотр)
описание:
автор:	email:
пароль:	[для последующего редактирования]
	подписаться на комментарии**

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей