Faster shuffle! for small arrays?

General Usage
1

I have some simulation code that I’m trying to speed up. @code_warntype didn’t suggest any type instability, so I turned to profiling. The core of the simulation code is essentially:

function core_of_simulation()
    choices = get_choices()
    shuffle!(choices)
    for c in choices
        success = attempt_choice!(c)
        if success
            return true
        end
    end
    return false
end

(It’s a customer choice model simulation which computes which discrete choices are optimal for the customer, then the customer chooses randomly from these good choices. I shuffle and then go one-by-one rather than just randomly selecting since some of the options may not be feasible choices for the customer.)

About half of simulation time is spent in the call to shuffle!. Almost always the list of choices being shuffled has length <10, and usually <5. Maybe there’s no efficiency gain to be had here, but it seems a little surprising that the simulation would have to spend more than half its time shuffling very short lists. Knowing that a list is short, is there a more efficient technique? I played around a bit but unsurprisingly was unable to beat the built-in shuffle!.

There is also the option of not shuffling at all but rather first filtering the list of choices to only feasible choices, and then selecting one at random. Checking choice feasibility is a bit expensive so if the shuffling can be sped up that seems preferable.

Many thanks for the help.

2

You could try something like this (untested code).

function core_of_simulation()
    choices = get_choices()
    n = length(choices)
    while n > 0
        i = rand(1:n)
        if attempt_choice!(choices[i])
            return true
        end
        choices[i], choices[n] = choices[n], choices[i]
        n -= 1
    end
    return false
end

It can be restructured a bit for more efficiency when n==1 but you get the idea.

1 Like
3

you could try randperm, and access items randomly instead of shuffling. but if your bottleneck is the rng, it won’t help. hard to tell without actual times and types.