CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Бинарный поиск в массиве и его разновидности. (159884 hits)
#Поразрядная сортировка, общий принцип. (124009 hits)
#Преобразование сумм из цифрового представления в строковое. (168576 hits)
#Простая быстрая сортировка. (108182 hits)
#Рисование полусферы. (26056 hits)
#Счетчик времени с точностью до микросекунд. (122642 hits)
#Шейкер-сортировка. (67500 hits)
#Вычисление минимального / максимального значения. (71370 hits)
#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (138486 hits)
#"Липкие" окна. (29313 hits)
#Косинус. (37281 hits)
#Подключение. (24152 hits)
#Логирование в GUI. (29705 hits)
#Сортировка вставкой. (107914 hits)
#Летающие, крутящиеся шарики. (41840 hits)
#Динамическая очистка выпадающего списка (select) на javascript. (86384 hits)
#Рисование множества Мандельброта. (41401 hits)
#Преобразование целых чисел в битовый массив. (34794 hits)
#Код. (173423 hits)
#Поверхностное клонирование. (25366 hits)


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

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

Aвтор:
Дата:
Просмотров: 444
реализации(java: 4шт...) +добавить

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

В предыдущей части этой задачи мы рассмотрели сначала квадратичный алгоритм 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 применяем формулу перестановок и увеличиваем итоговое количество Пар.

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

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

 псевдокод: Линейная версия подсчета одинаковых пар с помощью Хеш-таблицы  ссылка
  1. input=<исходный массив N чисел>
  2. countTable = new HashTable
  3.  
  4. // Проходимся по всем числам и сохраняем их кол-во
  5. for (i = 1...N-1) do:
  6. count = countTable.get(input[i]) // смотрим есть ли уже что по этому числу
  7. if count is empty? then: // Число еще не добавлено в Таблицу
  8. count = 0
  9.  
  10. count = count + 1
  11. countTable.put(input[i], count) // Сохраняем текущее число с его количеством
  12.  
  13. // далее проходимся по таблице и по формуле складываем ко-во пар
  14. result = 0
  15. for each key=>value from countTable do:
  16. if (value > 1) then:
  17. result = result + (value - 1) * value / 2
  18.  
  19. return result // возвращаем искомое количество

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

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

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

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

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

 Как посчитать количество пар чисел за ЛИНЕЙНОЕ(!) время с помощью Хеш-таблицы [java]  ссылка
  1. import java.util.HashMap;
  2. import java.util.Map;
  3.  
  4. class EqualPairCounter {
  5. int numberOfEqualPairsLinearWithExtraMap(int[] input) {
  6. int res = 0;
  7. Map<Integer, Integer> vMap = new HashMap<>();
  8.  
  9. for (final int v : input) {
  10. int count = vMap.getOrDefault(v, 0);
  11. vMap.put(v, ++count);
  12. }
  13.  
  14. for(final int v : vMap.keySet()) {
  15. if (vMap.get(v) > 1) {
  16. int pairs = vMap.get(v);
  17. res += (pairs - 1) * pairs / 2;
  18. }
  19. }
  20. return res;
  21. }
  22.  
  23. public static void main(String[] args) {
  24. 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};
  25. int pairCount = new EqualPairCounter().numberOfEqualPairsLinearWithExtraMap(input);
  26. System.out.println("Res: " + pairCount); // => 52
  27. }
  28. }
Полный код...

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

 Как максимально быстро посчитать одинаковые пары чисел, параллельное выполнение алгоритма [java]  ссылка
  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. }
Полный код...

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

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

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

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

Смещение

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

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

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

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

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

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

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

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

 псевдокод: Линейный алгоритм подсчета одинаковых пар через доп массив  ссылка
  1. input=<исходный массив N чисел>
  2. // сначала ищем максимальный элемент
  3. max = input[0]
  4. min = input[0]
  5. for (i = 1...N-1) do:
  6. if (input[i] > max) then:
  7. max = input[i]
  8.  
  9. if (input[i] < min) then:
  10. min = input[i]
  11.  
  12. // определяем смещение
  13. shift = min
  14.  
  15. // создаем реверс-массив
  16. countArrSz = max - min + 1
  17. countArr = new array size of [countArrSz]
  18.  
  19. // заполняем его нулями на начальном этапе
  20. for (j = 0...countArrSz) do:
  21. countArr[j] = 0
  22.  
  23. // далее проходимся по всем числам и подсчитываем одинаковые
  24. for (i = 0...N-1) do:
  25. v = input[i]
  26. countIndex = v - shift
  27. countArr[countIndex] = countArr[countIndex] + 1
  28.  
  29. // В конце по формуле перестановок считаем
  30. result = 0
  31. for (j = 0...countArrSz) do:
  32. count = countArr[j]
  33. if (count > 1) then:
  34. result = result + (count - 1) * count / 2
  35.  
  36. return result // возвращаем искомое количество

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

Код на java

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

 Как посчитать количество пар чисел за ЛИНЕЙНОЕ(!) время O(N) [java]  ссылка
  1. class EqualPairCounter {
  2. int numberOfEqualPairsLinearWithExtraArray(int[] input) {
  3. int max = input[0];
  4. int min = input[0];
  5. for (int v : input) {
  6. max = Math.max(max, v);
  7. min = Math.min(min, v);
  8. }
  9. int shift = min;
  10. int[] countArr = new int[max - min + 1];
  11. for (int v : input) {
  12. int countIdx = v - shift;
  13. countArr[countIdx]++;
  14. }
  15.  
  16. int res = 0;
  17. for(int count : countArr) {
  18. if (count > 1) {
  19. res += (count - 1) * count / 2;
  20. }
  21. }
  22.  
  23. return res;
  24. }
  25.  
  26. public static void main(String[] args) {
  27. 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};
  28. int pairCount = new EqualPairCounter().numberOfEqualPairsLinearWithExtraArray(input);
  29. System.out.println("Res: " + pairCount); // => 52
  30. }
  31. }
Полный код...

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

Выводы

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

Реализации:

java(4)   +добавить

1) Самый быстрый подсчет одинаковых пар чисел через Хеш-таблицу на java, code #802[автор:this]
2) Параллельная реализация подсчета одинаковых пар чисел через доп массив на java, code #805[автор:this]
3) Параллельная реализация для подсчета одинаковых пар чисел через Хеш-таблицу на java, code #804[автор:this]
4) Один из самых быстрых способов посчитать одинаковые пар чисел за O(n) на java, code #801[автор:this]