Этот вопрос может считаться слишком простым, но его часто задают на форумах. В этом посте я расскажу об одном способе, который ищет только ключ в Map ONCE .
Давайте сначала посмотрим на пример. Скажем, я создаю список частоты строк, используя карту , где каждый ключ является строкой , которая подсчитывается, а значением является целое число, которое увеличивается каждый раз при добавлении строки . Прямой способ достижения этого
|
1
2
|
int count = map.containsKey(string) ? map.get(string) : 0;map.put(string, count + 1); |
Этот фрагмент кода выполняется довольно медленно, потому что он содержит три потенциально дорогостоящих операции на карте, а именно содержит K.Key () , get () и [put ()] (http://docs.oracle.com/javase/7/docs/ api / java / util / Map.html # put (K, V)) . Каждый требует поиска ключа на карте. Теперь давайте проведем рефакторинг кода для повышения производительности.
Целое число против MutableInteger против AtomicInteger
Одна важная причина, по которой мы должны вызвать три дорогостоящие операции, — это использование Integer для подсчета. В Java Integer является неизменным . Это не позволяет нам изменять целочисленное значение после построения. Поэтому, чтобы увеличить счетчик, мы должны сначала получить целое число из карты, затем создать другое новое целое число, добавив его, и вернуть его обратно на карту.
Чтобы сделать счетчик изменчивым, есть несколько способов. Один из них — просто создать свой собственный MutableInteger , как показано ниже.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
|
public class MutableInteger { private int val; public MutableInteger(int val) { this.val = val; } public int get() { return val; } public void set(int val) { this.val = val; }} |
Другим способом может быть использование AtomicInteger в Java, который используется в приложениях, таких как счетчики с атомным приращением. Но основной выбор для AtomicInteger — если вы хотите добиться безопасности потоков с помощью операций с целым числом. Поэтому его нельзя использовать в качестве замены для целого числа. Исходя из этого, если потокобезопасность не является серьезным фактором для вашего проекта, я не рекомендую использовать AtomicInteger .
Поиск ключа только один раз
После использования MutableInteger мы можем изменить приведенный выше код на
|
1
2
3
4
5
6
|
if (map.containsKey(string)) { MutableInteger count = map.get(string); count.set(count.get() + 1);} else { map.put(string, new MutableInteger(1));} |
или же
|
1
2
3
4
5
6
|
MutableInteger count = map.get(string);if (count != null) { count.set(count.get() + 1);} else { map.put(string, new MutableInteger(1));} |
В худшем случае, когда ключ не был виден раньше, код будет искать ключ дважды: один для получения, другой для установки. Это намного лучше, чем предыдущий. Но мы НЕ должны быть удовлетворены прямо сейчас и остановиться. Если вы проверили метод [Map.put ()] (http://docs.oracle.com/javase/7/docs/api/java/util/Map.html#put (K, V)) в документе Java, вы обнаружите, что этот метод вернет the previous value associated with key . Это означает, что мы можем объединить получение и настройку в одно. Однако вы можете задаться вопросом: если мы не получим счетчик первым, как мы можем установить новый счетчик? Теперь мы наконец-то коснемся самой сложной части этого поста: мы можем упростить установку счетчика нулевой частоты !
|
1
2
3
4
5
6
7
8
9
|
public int incrementCount(K key, int count) { MutableInteger tmpCount = new MutableInteger(0); MutableInteger oldCount = map.put(key, tmpCount); if (oldCount != null) { count += oldCount.get(); } tmpCount.set(count); return count; } |
Еще один счетчик
Похоже, что помещение всех необходимых операций в класс будет полезным для будущего использования. Поэтому я создаю класс Counter и делаю его общедоступным. Счетчик определяет коллекцию, которая подсчитывает, сколько раз объект появляется в коллекции. Предположим, у вас есть счетчик, который содержит {a, a, b, c} . Вызов getCount () для «a» вернет 2, в то время как вызов keySet () вернет {a, b, c} . Этот класс работает как Map , но с различными методами для простого получения / установки / увеличения количества объектов и вычисления различных функций с помощью счетчика. Конструктор Counter и метод addAll () могут использоваться для копирования содержимого другого Counter. Класс Counter изменяется в соответствии с IntCounter и AbstractMapBag .
Некоторые выделенные операции на счетчике включают
- incrementCount () и decmentCount () : Добавляет / вычитает данное количество к текущему числу для данного ключа. Если ключ не был виден раньше, предполагается, что он имеет счетчик 0, и, таким образом, метод приращения установит его счетчик на заданную сумму. Для декремента будет установлено значение -1.
- getCount () : возвращает текущий счетчик для данного ключа, который равен 0, если его раньше не видели.
- keysAt () , keysAbove () и keysBelow () : возвращает набор ключей, число которых равно , выше или ниже заданного порогового значения. Этот набор может иметь 0 элементов, но не будет нулевым.
- argmin () и argmax () : находит и возвращает ключ в этом счетчике с наименьшим / наибольшим числом. Если имеется несколько минимальных / максимальных значений, возвращается случайное значение. Возвращает ноль, если этот счетчик пуст.