Блог пользователя ValenKof

Java map
Автор ValenKof, 12 лет назад, По-русски

В процессе изучения Java возник вопрос касательно TreeMap/HashMap. Вот пример кода:

Scanner in = new Scanner(System.in);
int n = in.nextInt();
Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
for (int i = 0; i < n; ++i) {
    int key = in.nextInt();
    Integer value = map.get(key);
    map.put(key, 1 + (value == null ? 0 : value));
}

Правильно ли я понимаю, что здесь проиходит 2 поиска в Map при каждом обновлении? Если да, то как реализовать такое за 1 поиск. Интересует работа именно с Map, т.к. задачи могут быть другие, это просто пример.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Можно ускорить с помощью mutable-Integer (AtomicInteger ниже только как пример, лучше самому написать класс MutableInteger с методами get/increment):

Scanner in = new Scanner(System.in);
int n = in.nextInt();
Map<Integer, AtomicInteger> map = new TreeMap<Integer, AtomicInteger>();
for (int i = 0; i < n; ++i) {
	int key = in.nextInt();
	AtomicInteger value = map.get(key);
	if (value == null) {
		value = new AtomicInteger(0);
		map.put(key, value);
	}
	value.incrementAndGet();
}

Есть ещё такой метод java.util.concurrent.ConcurrentMap.putIfAbsent(K, V), но это уже синхронизированные map'ы, которые по-идее работают медленнее.

→ Ответить
»
12 лет назад, # |
← Rev. 6   Проголосовать: нравится +1 Проголосовать: не нравится

Map.entrySet

Map.Entry.setValue

Не знаю насколько юзабельно — только что нагуглил.

→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

В мапе значения — это ссылки на объекты. Соответственно если получить от туда значение и в объекте его поменять — поменяется значение и в мапе.

Но я ни разу не встречался с тем, что нужны были подобные оптимизации...

class Int {
      int value;

      public Int(int value) {
         this.value = value;
      }
   }

   void solve() {
      TreeMap<Integer, Int> map = new TreeMap<Integer, Int>();
      for (int i = 1; i < 10; i++) {
         map.put(i, new Int(i));
      }
      for (int i = 1; i < 10; i++) {
         Int key = map.get(i);
         key.value++;
      }
      for (int key : map.keySet()) {
         out.println(key + " " + map.get(key).value);
      }
   }
→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Ну с этим понятно уже все. Интересовало, есть ли какой способ для immutable классов. Так по сути любой класс можно завернуть и использовать, но более красивого способа нет?

    P.S. Нашел то, что искал:

    Scanner in = new Scanner(System.in);
Map<Integer, AtomicReference<Integer> > map = new TreeMap<Integer, AtomicReference<Integer> >();
int n = in.nextInt();
for (int i = 0; i < n; ++i) {
    int key = in.nextInt();
    AtomicReference<Integer> value = map.get(key);
    if (value == null) {
        value = new AtomicReference<Integer>(0);
        map.put(key, value);
    }
    value.set(value.get() + 1);
}
for (Map.Entry<Integer, AtomicReference<Integer>> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}
    → Ответить