Самый эффективный способ обновления ArrayList

Question

У меня есть ArrayList, который будет обновляться один раз в секунду, чтобы выполнить некоторые основные проверки и поддерживать список игроков, которые в настоящее время выполняют множество условий.

Мне интересно, какой наивысший способ сделать это - у меня есть 2 предложенных решения.

public void update() { 
    for (Player player : Bukkit.getOnlinePlayers()) { 
     if (!playersOnLadder.contains(player)) { 
      if (checkPlayerOnLadder(player)) { 
       playersOnLadder.add(player); 
      } 
     } else { 
      if (checkPlayerOnLadder(player)) { 
       playersOnLadder.remove(player); 
      } 
     } 
    } 
} 

public void update() { 
      playersOnLadder.clear(); 

    for (Player player : Bukkit.getOnlinePlayers()) { 
     if (checkPlayerOnLadder(player)) { 
      playersOnLadder.add(player); 
     } 
    } 
} 

Было бы около 75 участников в этом списке массивов в любой момент времени. «Проверка игрока на методе лестничного выглядит следующим образом:

private boolean checkPlayerOnLadder(Player player) { 
    int ladderAbsolute = this.getX()+this.getZ(); 
    int playerAbsolute = (int) player.getLocation().getX()+ (int) player.getLocation().getZ(); 

    //If the player is within 4 blocks (2 in each direction) of the ladder then return true. 
    if (ladderAbsolute == playerAbsolute || (ladderAbsolute-2 > playerAbsolute && ladderAbsolute+2 < playerAbsolute)) { 
     return true; 
    } else { 
     return false; 
    } 
} 

EDITED преобразуется в HashSet

Answer 1

Если ограничивается этими двумя вариантами, то я бы с опционной номером 2 в качестве высшего решения исполнительской

.

В варианте 1 операция remove в ArrayList равна O (n), так как она должна найти игрока, O (n), и удалить игрока, если он найден, перемещая всех дальше вниз на O (n). весь список игроков - O (n^2).

Вариант 2 просто очищает список для начала с помощью O (n). Операцией add является O (1) (если не требуется изменение размера), поэтому их добавление также равно O (n). Вариант 2 - общий O (n).

Замена вашей ArrayList с HashSet (и реализующей hashCode и equals на Player) может быть вариант. Операциями хеширования являются O (1), поэтому петля над всеми игроками и выполнение этих операций также O (n). Если вам нужно быстро найти нужный Player, перейдите к HashSet, потому что contains - это O (1) в HashSet, но O (n) в ArrayList.

Answer 2

Пожалуйста, используйте структуру данных типа словаря для такого рода бухгалтерского учета. HashSet (убедитесь, что вы правильно используете hashCode!), Скорее всего, вы хотите. Семантически и результативно.

Я не понимал вашу лестницу и сопровождающий алгоритм.

Answer 3

Лучший способ, вероятно, использовать HashSet, но Playerdoesn't override hashCode, так HashMap<int, Player> будет работать, используя Игрока entityId.

Что-то вроде этого:

HashMap<int, Player> playersOnLadder; /* make sure to initialize this */ 

public void update() { 
    for (Player player : Bukkit.getOnlinePlayers()) { 
     if (checkPlayerOnLadder(player)) { 
      playersOnLadder.put(player.getEntityId(), player); 
     } else { 
      playersOnLadder.remove(player.getEntityId()); 
     } 
    } 
} 

Потому что это HashMap, put ИНГ несколько раз отлично, и HashMap.remove безопасно звонить, если данное obejct не в карте (она будет возвращать null, но в этом случае нет необходимости проверять это).

---

Даже лучше, чем это было бы изменить свой код, чтобы использовать events. Похоже, что PlayerJoinEvent и PlayerQuitEvent могут быть вам полезны, и какая бы то ни было ваша функция checkPlayerOnLadder может быть выполнена в ответ на событие.

Answer 4

"75 игроков" + "раз в секунду" => двигаться дальше!

Вы можете быть в состоянии получить несколько наносекунд каждый второй, который может сделать ваш код несколько 0,0000001% быстрее ...

Теперь быстрее вариант, вероятно, будет это (выделение, как правило, дешевле, чем очистка):

public void update() { 
    // pre sizing the list saves unnecessary resizing operations. 
    playersOnLadder = new ArrayList<>(Bukkit.getOnlinePlayers()); 
    for (Player player : Bukkit.getOnlinePlayers()) { 
     if (checkPlayerOnLadder(player)) { 
      playersOnLadder.add(player); 
     } 
    } 
}