Эффективный подсчет элементов в списке записей

Question

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

Если я заранее знаю авторов, я могу просто создать переменные для каждого автора и увеличить их без поиска, а затем, наконец, создатькарта, как только я закончу читать входные данные.Однако я знаю только нескольких авторов в данных.

Заранее спасибо.

Answer 1

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

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

Answer 2

Вы можете найти TObjectIntHashMap более эффективным, чем HashMap, но оба будут довольно эффективными. Вы должны быть в состоянии отсканировать 100К записей за несколько миллисекунд. Если это не достаточно быстро, вы можете сохранить Карту подсчетов при добавлении / обновлении / удалении записи, чтобы вы могли просто посмотреть это.

Answer 3

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

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

Answer 4

Среднее значение для поиска с помощью Java HashMap будет O (1) , что означает, что оно не приведет к значительному увеличению времени выполнения.

Если вы не действительно пытаетесь выжать из этого все, вы, вероятно, просто чрезмерно оптимизируете.