Самый эффективный способ считать случаи?
Я надеюсь вычислять энтропийную и взаимную информацию огромное количество раз в критическом по отношению к производительности коде. Как промежуточный шаг, я должен считать количество случаев каждого значения. Например:
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.
Конечно, очевидные способы сделать это или использует ассоциативный массив или путем сортировки входного массива с помощью "стандартного" алгоритма сортировки как быстрая сортировка. Для маленьких целых чисел, как байты, код в настоящее время специализируется для использования простого массива.
Там какой-либо умный алгоритм должен сделать это более эффективно, чем хеш-таблица или "стандартный" алгоритм сортировки предложат, такие как реализация ассоциативного массива, которая в большой степени способствует обновлениям по вставкам или алгоритму сортировки, который сияет, когда Ваши данные имеют много связей?
Примечание: Нередкие целые числа являются всего одним примером возможного типа данных. Я надеюсь реализовывать довольно универсальное решение здесь, хотя, так как целые числа и структуры, содержащие только целые числа, являются общими падежами, я интересовался бы решениями, характерными для них, если они чрезвычайно эффективны.
3 ответа
Пожалуйста, расскажите подробнее о ваших данных.
- Сколько всего предметов?
- Каково ожидаемое отношение количества уникальных предметов к общему количеству предметов?
- Каково распределение фактических значений ваших целых чисел? Являются ли они обычно достаточно маленькими, чтобы использовать простой счетный массив? Или они сгруппированы в достаточно узкие группы? И т.д.
В любом случае, я предлагаю следующую идею: mergesort, модифицированный для подсчета дубликатов.
То есть вы работаете в терминах не чисел, а пар (число, частота) (вы можете использовать для этого какое-нибудь умное представление, экономящее память, например, два массива вместо массива пар и т.д.).
Вы начинаете с [(x1,1), (x2,1), ...] и выполняете mergesort как обычно, но когда вы объединяете два списка, которые начинаются с одного и того же значения, вы помещаете значение в выходной список с их суммой встречаемости. На вашем примере:
[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, и используйте небольшой массив для подсчета повторений внутри каждого блока. На самом деле этот трюк можно применить и на более поздних этапах объединения.
Хеширование, как правило, более масштабируемое, как другой ответ указывает. Однако для многих возможных распределений (и многих реальных случаев, когда подмассивы часто сортируются, в зависимости от того, как был собран весь массив), timsort часто «сверхъестественно хорош» (ближе к O (N), чем O (N log N)) - я слышал, что он, вероятно, станет стандартным / стандартным алгоритмом сортировки в Java в некоторых достаточно близких будущих данных (это был стандартный алгоритм сортировки в Python в течение многих лет).
Нет действительно хорошего способа решить такие проблемы, кроме как провести сравнительный анализ выборки случаев, которые являются репрезентативными для реальной рабочей нагрузки, которую вы ожидаете испытывать (с очевидным риском, что вы можете выбрать образец, который на самом деле оказался предвзятый / непредставительный - это немалый риск, если вы пытаетесь создать библиотеку, которая будет использоваться многими внешними пользователями вне вашего контроля).
Для массива целых чисел, как в примере, наиболее эффективным способом было бы иметь массив int s и индексировать его на основе ваших значений ( как вы, кажется, уже делаете).
Если вы не можете этого сделать, я не могу придумать лучшей альтернативы, чем хэш-карта. Вам просто нужен алгоритм быстрого хеширования. Вы не можете добиться производительности лучше, чем O (n), если хотите использовать все свои данные. Можно ли использовать только часть имеющихся у вас данных?
(Обратите внимание, что сортировка и подсчет асимптотически медленнее (O (n * log (n))), чем при использовании решения на основе хэш-карты (O (n)) .)