Самый эффективный способ подсчета событий?

Question

Я рассчитываю вычислять энтропию и взаимную информацию огромное количество раз в критичном к производительности коде. В качестве промежуточного шага мне нужно посчитать количество вхождений каждого значения. Например:

uint[] myArray = [1,1,2,1,4,5,2];
uint[] occurrences = countOccurrences(myArray);
// Occurrences == [3, 2, 1, 1] or some permutation of that.
// 3 occurrences of 1, 2 occurrences of 2, one each of 4 and 5.

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

Существует ли какой-нибудь умный алгоритм, позволяющий сделать это более эффективно, чем предложит хеш-таблица или «стандартный» алгоритм сортировки, такой как реализация ассоциативного массива, которая в значительной степени предпочитает обновления над вставками, или алгоритм сортировки, который светится, когда ваши данные много связей?

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

Answer 1

Хеширование обычно более масштабируемо, как указывает другой ответ. Тем не менее, для многих возможных распределений (и многих реальных случаев, когда подмассивы оказываются часто отсортированными, в зависимости от того, как был собран весь массив), timsort часто "сверхъестественно хорош" O (N), чем O (N log N)) - я слышал, что он, вероятно, станет стандартным / стандартным алгоритмом сортировки в Java при некоторых достаточно близких будущих данных (это был стандартный алгоритм сортировки в Python в течение многих лет).

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

Answer 2

Пожалуйста, расскажите больше о ваших данных.

• Сколько там предметов?
• Каково ожидаемое соотношение уникальных предметов к общему количеству предметов?
• Каково распределение фактических значений ваших целых чисел? Они обычно достаточно малы, чтобы использовать простой счетный массив? Или они сгруппированы в достаточно узкие группы? И т.д.

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

То есть вы работаете не с числами, а с парами (число, частота) (вы можете использовать для этого какое-нибудь умное представление с эффективным использованием памяти, например, два массива вместо массива пар и т. Д.).

Вы начинаете с [(x1,1), (x2,1), ...] и выполняете сортировку слиянием, как обычно, но когда вы объединяете два списка, которые начинаются с одинакового значения, вы помещаете значение в вывод список с их суммой совпадений. На вашем примере:

[1:1,1:1,2:1,1:1,4:1,5:1,2:1]
Split into [1:1, 1:1, 2:1] and [1:1, 4:1, 5:1, 2:1]
Recursively process them; you get [1:2, 2:1] and [1:1, 2:1, 4:1, 5:1]
Merge them: (first / second / output)
[1:2, 2:1] / [1:1, 2:1, 4:1, 5:1] / [] - we add up 1:2 and 1:1 and get 1:3
[2:1] / [2:1, 4:1, 5:1] / [1:3] - we add up 2:1 and 2:1 and get 2:2
[] / [4:1, 5:1] / [1:3, 2:2]
[1:3, 2:2, 4:1, 5:1]

Это может быть значительно улучшено с помощью некоторых хитрых трюков для первоначального сокращения массива (получения массива значений: пары вхождений, которые намного меньше, чем исходные, но сумма «вхождений» для каждого «значения») равно числу вхождений 'value' в исходном массиве). Например, разбить массив на непрерывные блоки, значения которых отличаются не более чем на 256 или 65536, и использовать небольшой массив для подсчета вхождений внутри каждого блока. На самом деле этот прием можно применить и на более поздних этапах слияния.

Answer 3

С массивом целых чисел, как в примере, наиболее эффективным способом было бы иметь массив int s и индексировать его на основе ваших значений (как вы, похоже, уже делаете).

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

(Обратите внимание, что сортировка и подсчет асимптотически медленнее (O (n * log (n))), чем при использовании решения на основе хеш-карты (O (n)).)