Randomize Collection

I am making a minigame and i need to randomize Bukkit.getOnlinePlayers Collection so it isn't the way players logged in. How would i do it?

 

@MCMatters
I often add them all to a list, then put a while loop where you check if the list is not empty. Each time you remove a random player from the list (list.remove(Random#nextInt(list.size()))), and you do stuff with that player.

 

If it's only needed on occasion, just go with a clean and simple thing like suggested (Edit: see statement below...) below.

If you have many players and need randomization extremely often, you could also apply other techniques to get the randomization a bit faster, using less calls to create random numbers. But one should do a profiling for the simple method and see if it's actually needed, i assume it's not (probably not even with once per tick with 100 players).

 

or, y'know:

Code:java

List<Player> players = new ArrayList<>(Bukkit.getOnlinePlayers());
Collections.shuffle(players);

 

Oh right, forgot that one - the method to use will now depend on the number of players and how often it has to be done. For shuffling and using all entries in non-extreme ways, Collections.shuffle should clearly be best.

Edit: Beware of while loop...

Show Spoiler Hide Spoiler

In fact the while loop suggestion is somewhat problematic (algorithmically). If you have an ArrayList and remove a random element, this will lead to copying all following elements to close the gap, which can become expensive with a large number of players. A LinkedList would mean traversing the list elements until the index is found, same thing. The Algorithm used in Collections.shuffle clearly is favourable, and if you need to randomize an unknown number of players, you should actually rather implement/imitate that algorithm, e.g. copy the collection into an array right away, go from index 0 to the number of needed elements (-1), swap with a random element of the same array (no need to traverse all). But i think the task really was to get a shuffled thing of all players, so forget about this then.

 

ArrayLists do not resize upon removing/adding elements for every operation, that would be a CopyOnWriteArrayList. The biggest problem with the above example depends on how the random is retrieved.

 

Removing the middle element of an ArrayList of size n typically needs copying n/2 elements, because there can not stay a gap in the middle.

That's why using a while loop removing elements from an ArrayList would not be good, similar goes for a LinkedList because they have to iterate through elements to navigate to a certain index. Once the number of elements get large this might start hurting (O(n^2) runtime). The amount of random numbers to calculate doesn't change, but the runtime could cripple things.

Concerning the CopyOnWriteArrayList, that's copying the entire list each time it is changed, in order to provide a fast to read and iterate but thread-safe list version. Internally they're all array lists, which need copying if you remove elements in the middle (or if you add many elements, due to resizing the internal array).

Collections.shuffle will shuffle the entire list and also use as many random numbers as there are players. I was just pointing at an implementation for the case of excessively often needing a population of online players (not all, possible with changing size), then an optimized implementation may pay.

If it always is all players or if it is not excessive, Collections.shuffle should be the way to go (simplicity and efficiency).