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

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

Опишите ваши данные.

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

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

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

Вы начинаете с [(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] 

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

Answer 2

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

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

(Обратите внимание, что сортировка и подсчет асимптотически медленнее (О (п * журнала (п))), чем при использовании HashMap на основе решения (O (N)).)

Answer 3

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

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