Complexity of enum.values()

Question

I have a very simple Enum as follows:

public enum Colour { RED, BLUE, GREEN; }

Here I've put three colours, but it may have a undefined size.

This Enum will be used in a class which can have an undefined number of instances (hundreds, thousands or even millions).

In this class I have a method that must return a random Colour.

I have two options for this.

private Colour[] colours;

public Datastructure() {

    colours = Colour.values();
}

public Colour getRandomColour() {
     return colours[rand.nextInt() % colours.length];
}

Or I can keep calling Colour.values() instead of creating the colours list.

public Colour getRandromColour() {
     return Colour.values()[rand.nexInt() % Colour.values().length]

In the first option, an extra array is created. Keep in mind that this class may have many instances, so it could be considered a waste of memory, and may have a impact on running time as well (instantiating the array). Especially when there are a lot of class instances.

In the second option, Colour.values() is called a few times (in this simple example it is only a few times but in my project it's bit more complex and has more calls) so this can be considered a waste of CPU usage.

I would prefer using the second option, but I'm curious about the complexity of the Colour.values() method, which I fear may be linear O(n). n being the number of Colours in the enum. This would be horrible when there are a lot of colours.

Or would it just be a weigh off and choose the best of two evils?

tl;dr What is the complexity of Enum.values()?

You're wasting your time trying to micro optimize something totally irrelevant. — Kayaman, Nov 23 '14 at 13:27
Modulo is an expensive operation. You'd be much better of calling `rand.nextInt(values().length)`. — Boris the Spider, Nov 23 '14 at 13:29
@BoristheSpider how is that obvious? Or even true? It can't just give you a reference to an existing array, because arrays are not read-only. — harold, Nov 23 '14 at 13:30
@Kayaman I don't really agree on the micro-optimizing. As I said, there may be a LOT of Colours and/or class instances. So this micro-optimizing might end up to be a big improvement. — Auberon, Nov 23 '14 at 13:32
@BoristheSpider Thank you for pointing out the modulo part. Could you explain why .values() is O(1)? — Auberon, Nov 23 '14 at 13:36
On closer inspection, @harold is right - I'm an idiot. [This SO answer](http://stackoverflow.com/a/1163121/2071828) reckons that `values()` is implemented as `array.clone()`. — Boris the Spider, Nov 23 '14 at 13:39
@Auberon how many is your "lots of colors"? Because I suspect that if you really did have a large amount of colors, you'd use a database to store it and not an enum. — Kayaman, Nov 23 '14 at 13:39
@Kayaman Undefined. Could be two, could be a million. I have no knowledge of databases as of yet. So I won't be considering a database as an option. — Auberon, Nov 23 '14 at 13:45
@Auberon Then consider [this link](http://stackoverflow.com/questions/4468388/maximum-number-of-enum-elements-in-java) which would give the maximum number of enum elements as 65535. — Kayaman, Nov 23 '14 at 13:58

JB Nizet · Accepted Answer · 2014-11-23T13:52:55.720

4

The array returned by Colour.values() always contains the same elements, but values() creates a new array every time it's called (so it's O(n) where n is the number of enum values). And you never modify that array. So calling the method every time you need it is a waste of time. And storing an array in every instance of your DataStructure class is a waste of time and memory. I would simply call the method once and cache that array in a constant:

private static final Colour[] COLOURS = colour.values();

public Colour getRandomColour() {
    return COLOURS[rand.nextInt(COLOURS.length)];
}

Just make sure this array is never exposed outside of the class.

Also note the usage of Random.nextInt(limit) which does exactly what you want, is probably faster, and expressed the intent more clearly than using a modulo.

edited Nov 23 '14 at 13:52

answered Nov 23 '14 at 13:39

JB Nizet

678,734
91
1,224
1,255

Thank you. Kind of weird I didn't think of this. Could you modify your answer so it mentions the things pointed out by @BoristheSpider? (Modulo is expensive + .values() is ~equivalent~ to .clone(), which is O(n)) – Auberon Nov 23 '14 at 13:48
@Auberon answer modified. – JB Nizet Nov 23 '14 at 13:53
Personally, I'd do all this inside the enum class itself (define `rand` and `COLORS` as private static members thereof, and `getRandomColour` as public static). Keeps `Colour` related functions encapsulated in `Colour`. – RealSkeptic Nov 23 '14 at 14:13
@RealSkeptic it's of course a valid option. It mainly depends on how you consider `getRandomColour()`: is it a method that is useful in general and that many classes will need to call, or is it something that is useful only in a specific use-case and that should not pollute the public API of the enum? – JB Nizet Nov 23 '14 at 14:17

score 0 · Answer 2 · answered Nov 23 '14 at 13:51

0

Why not just put the cached array in a static field of Colour enum itself. then provide a method in the Colour enum to return a random entry.

It makes sense for the Colour enum to own this piece of data/method anyway.

answered Nov 23 '14 at 13:51

MeBigFatGuy

28,272
7
61
66

Complexity of enum.values()

2 Answers2

Linked