NSSet how to extract object randomly?

Question

I am not sure about how NSSet's anyObject work. What does it mean that "The object returned is chosen at the set’s convenience" (from the NSSet class reference) ?

Further, how can I best extract objects randomly from a NSSet? I was thinking about getting allObjects in an array and then myArray[arc4random_uniform(x)] where x is the number of objects in the array.

Scrofula

Are you ok with repeats? – Dirt

Rather curious about that myself, I guess you could call anyObject a random number of times but your array solution sounds better. – Nedra

I guess converting NSArray to NSSet back and forth won't be a good way to shuffle. – Weigela

Answer 1

Usually, NSSet instances are created with a CFHash backing, so they almost always return the first object in that hash, as it is the fastest to look up. The reason it says

The object returned is chosen at the set’s convenience—the selection is not guaranteed to be random.

Is because you don't always know it will have a backing array. For all you know, the NSSet instance you have has a NSDictionary backing it, or some other similar data structure.

So, in conclusion, if you need a random object from a NSSet, don't use -anyObject, instead use allObjects: and then shuffle that array.

Necrophobia

Yes! I think this puts me at the rep cap for today! – Necrophobia

Actually, NSSet is created with a CFBasicHash backing. Making assumptions based on the idea that the set is array-backed is just as unsafe as making assumptions based on the idea that it is randomly sorted. – Manganate

See CFSet.c for the implementation of NSSet (whose concrete subclasses are equivalent to CFSet instances.) – Manganate

Answer 2

Quote from NSSet Class Reference:

The object returned is chosen at the set’s convenience—the selection is not guaranteed to be random.

For "randomness", convert the NSSet to an NSArray using [theSet allObjects].
Next, pick any object randomly using arc4random_uniform().

Firer

Lets be fair here, you will also need to initialize the randomizer differently each startup for it truly to be random, and even then, it is pseudorandom :-) +1 – Gwenn

Answer 3

The documentation reads that anyObject returns

One of the objects in the set, or nil if the set contains no objects. The object returned is chosen at the set’s convenience—the selection is not guaranteed to be random.

Most likely there is some deterministic algorithm at work.

The most reliable thing to do would be, as you suggest, to create an NSArray using the NSSet method allObjects, and then choose a random element from that with arc4random() % N where N is the count of the NSArray.

Tryck

Better to use arc4random_uniform instead just using the modulo operator, as fabio suggested in his question, to avoid modulo bias. – Tion

Answer 4

I use arc4random() and two mutable arrays to get a random and unique set of objects:

NSMutableArray *selectionPool = ...;

int numberOfObjectsToSelect = x;

NSMutableArray *selectedObjects = [[NSMutableArray alloc] initWithCapacity:numberOfObjectsToSelect];

int modulus = selectionPool.count - 1;

for (int i = 0; i < numberOfObjectsToSelect; i++) {

    int j = arc4random() % (modulus--);
    [selectedObjects addObject:[selectionPool objectAtIndex:j]];
    [selectionPool removeObjectAtIndex:j];

}

I'm not sure how efficient it would be for large collections, but it's worked for me with collections that number in the low 100s of objects.

Hamman

would get division by zero exception if numberOfObjectsToSelect == selectionPool.count – Madson