Can you beat our solutions for the raindrops exercise?

General Usage Performance
1

So, @cmcaine, @SaschaMann, @tomerarnon and I have been discussing the raindrops exercise in Exercism and solutions to it.

The Exercise

Create a function raindrops, which will return a string given a number as follows:

Start with an empty string. If the number

  • has 3 as a factor, add ‘Pling’ to the result.
  • has 5 as a factor, add ‘Plang’ to the result.
  • has 7 as a factor, add ‘Plong’ to the result.
  • does not have any of 3, 5, or 7 as a factor, the result should be the digits of the number.

Can any of you find more performant solutions? There are two categories.

1. Fastest solution

In this category you just have to find the fastest possible solution. Our best so far is:

Tree of if / else solution 
function raindrops(number)
    f3 = number % 3 == 0
    f5 = number % 5 == 0
    f7 = number % 7 == 0

    if f3
        if f5
            if f7
                "PlingPlangPlong"
            else
                "PlingPlang"
            end
        else
            if f7
                "PlingPlong"
            else
                "Pling"
            end
        end
    else
        if f5
            if f7
                "PlangPlong"
            else
                "Plang"
            end
        else
            if f7
                "Plong"
            else
                string(number)
            end
        end
    end
end

2. Fastest concatenating solution

In this category you must make use of the concatenating logic of the problem. So you can only have "Pling", "Plang", "Plong" as literal strings in your solution.

Compact concatenating solution 
function raindrops(number)
    s = ""
    number % 3 == 0 && (s = "Pling")
    number % 5 == 0 && (s *= "Plang")
    number % 7 == 0 && (s *= "Plong")
    isempty(s) && (s = string(number))
    return s
end

A third category may be solutions which use a macro to generate the tree / lookup table. If somebody has a clean way to do that, that would be interesting as well.

Benchmarks

I’m measuring the solutions with this benchmark.

@btime mapreduce(raindrops, (a, b) -> b, 1:1000)

Have a look at this, to see some of the solutions we’ve experimented with so far.

2

The reason we were looking into this was to improve our mentoring notes for this exercise on exercism. The notes show a variety of ways to solve the problem and try to explain the trade-offs. Here’s a link and an excerpt in a spoiler for anyone interested.

Spoiler

Link: https://github.com/exercism/website-copy/blob/e44841e44f4b869a74b357c15f1cc9241a71a8e3/tracks/julia/exercises/raindrops/mentoring.md

You can solve this exercise a great number of ways!
The fastest solutions avoid constructing new strings unless they have to and instead return one of several statically allocated strings when n is divisible by 3, 5, or 7.
Simpler or more flexible solutions construct strings through concatenation.

The example solutions below are roughly in run time order (fastest first), but all of them are satisfactory solutions to the problem.
If you’re a performance enthusiast, you might like to check out the benchmarking notes below because it’s easy to measure the wrong thing.

Aside: benchmarking raindrops

When benchmarking code, we generally take the minimum time from several runs of the code.
We can do that with:

using BenchmarkTools

# Thing we want to benchmark
foo(x) = x * x + x

# Benchmark a specific value
# Wrapped in $() to stop the compiler cheating
@btime foo($(100))

# Benchmark on some randomly selected small integers
@btime foo(v) setup=(v = rand(1:1000))

That’s a good default, but if you supply a random value as input to a function that takes a very different amount of time per value (as several of the solutions below do), then the minimum will be the time of the “happy path”, rather than a time that represents the time taken for a randomly selected input value.

If you’re interested in the average time, but still want to avoid issues with outliers, it’s a good idea to apply your function to many inputs in each benchmark trial:

# One fast branch, one slow branch
bar(x) = x < 10 ? 10 : log(x)

# Tell us the minimum time it takes to call `bar` once on each of 1:1000.
@btime foreach(bar, $(1:1000))

# If the benchmark is suspiciously quick, the compiler could be eliding the for loop.
# In that case you can force it to do the work with a simple reduction.
@btime mapreduce(bar, (a, b) -> b, $(1:1000)) # A do-nothing reduction
@btime maximum(bar, $(1:1000))

If you want to benchmark lots of variants of the same function, you can define them as raindrops1, raindrops2, etc. and do some simple code generation like this:

for i in 1:8
   print("$i: ")
   @btime foreach($(Symbol(:raindrops, i)), 1:1000)
end

1:   20.100 μs (914 allocations: 42.84 KiB)
2:   85.000 μs (4457 allocations: 233.03 KiB)
3:   27.800 μs (1256 allocations: 53.53 KiB)
4:   24.300 μs (914 allocations: 42.84 KiB)
5:   21.600 μs (914 allocations: 42.84 KiB)
6:   35.700 μs (1457 allocations: 59.81 KiB)
7:   47.600 μs (1589 allocations: 63.94 KiB)
8:   86.500 μs (4457 allocations: 233.03 KiB)

if / else tree

function raindrops(number)
    f3 = number % 3 == 0
    f5 = number % 5 == 0
    f7 = number % 7 == 0

    if f3
        if f5
            if f7
                "PlingPlangPlong"
            else
                "PlingPlang"
            end
        else
            if f7
                "PlingPlong"
            else
                "Pling"
            end
        end
    else
        if f5
            if f7
                "PlangPlong"
            else
                "Plang"
            end
        else
            if f7
                "Plong"
            else
                string(number)
            end
        end
    end
end

Lookup

A lookup table is another good option.

function raindrops(number)
    i = 0
    i |= (number % 3 == 0)       # 001
    i |= (number % 5 == 0) << 1  # 010
    i |= (number % 7 == 0) << 2  # 100

    if i == 0
        return string(number)
    else
        return @inbounds (
            "Pling",            # 001
            "Plang",            # 010
            "PlingPlang",       # 011
            "Plong",            # 100
            "PlingPlong",       # 101
            "PlangPlong",       # 110
            "PlingPlangPlong",  # 111
        )[i]
    end
end

Switch

A slightly slower version formatted as a single switch rather than a tree of ifs.

function raindrops(number)
    f3 = number % 3 == 0
    f5 = number % 5 == 0
    f7 = number % 7 == 0

    if f3 & f5 & f7
        "PlingPlangPlong"
    elseif f3 & f5 & !f7
        "PlingPlang"
    elseif f3 & !f5 & f7
        "PlingPlong"
    elseif f3 & !f5 & !f7
        "Pling"
    elseif !f3 & f5 & f7
        "PlangPlong"
    elseif !f3 & f5 & !f7
        "Plang"
    elseif !f3 & !f5 & f7
        "Plong"
    else
        string(number)
    end
end

The following three solutions are slower but make use of concatentaion so as to be more concise, readable or extendable.

Compact

This solution is short, easy to read and almost as fast in the average case as the solutions above!
It is fast because it avoids one string concatenation in the common case that number is divisible by 3
and when number is divisible by 3, but not 5 and 7, the statically allocated string “Pling” is returned almost instantly.

function raindrops(number)
    s = ""
    # The first equals here lets us avoid
    # dynamically allocating a string in the
    # case that number is only divisible by 3.
    number % 3 == 0 && (s = "Pling")
    number % 5 == 0 && (s *= "Plang")
    number % 7 == 0 && (s *= "Plong")
    isempty(s) && (s = string(number))
    return s
end

Try changing s = "Pling" to s *= "Pling" and benchmarking with 3, 14, and 15 to see what’s going on.

Expected benchmark results and explanation

raindrops3a is the version with s *= "Pling".

using BenchmarkTools

@btime raindrops3($(3))         # 0 allocations
@btime raindrops3a($(3))        # 1 allocation

# 14 is not divisible by 3, so there's no difference here.
@btime raindrops3($(14))        # 1 allocation
@btime raindrops3a($(14))       # 1 allocation

# 15 is divisible by 3 and 5 and we can still avoid the first allocation.
@btime raindrops3($(15))        # 1 allocation
@btime raindrops3a($(15))       # 2 allocations

Extendable

cmcaine’s solution

A solution (over?)designed to be easily extended or changed if the noises spec changed. Some similar solutions use a Dict rather than a tuple, but a tuple of pairs is simpler and more efficient if you do not want to look up values by key.

function raindrops(n)
    noises = (3 => "Pling", 5 => "Plang", 7 => "Plong")
    acc = ""
    for (factor, noise) in noises
        n % factor == 0 && (acc *= noise)
    end
    isempty(acc) ? string(n) : acc
end

IOBuffer

Using an IOBuffer to create a string on the fly is a common pattern in julia. However, in this case, it tends to be rather slow compared to the other solutions.

function raindrops(number)
    buf = IOBuffer(sizehint=15)

    number % 3 == 0 && write(buf, "Pling")
    number % 5 == 0 && write(buf, "Plang")
    number % 7 == 0 && write(buf, "Plong")

    if position(buf) == 0
        return string(number)
    else
        return String(take!(buf))
    end
end
4

Ok… this is what I want to submit now

function raindrops(number)
    a=  (number%3 == 0 ? "Pling" : "")*(number%5 == 0 ? "Plang" : "")*(number%7 == 0 ? "Plong" : "")  
    isempty(a) && return string(i)
    a
end

julia> @btime mapreduce(raindrops, (a, b) -> b, 1:1000)
  59.015 μs (1457 allocations: 59.81 KiB)

Edit: now it works ;(

5

Not sure if preallocating the strings is allowed, but if so this is even faster:

function make_str()
    a =fill(" ",7)
    for i in 1 :7
        if i & 1 ==1
            a[i] = a[i]*"Pling"
        end
        if i & 2 ==2
            a[i] = a[i]*"Plang"
        end
        if i & 4 ==4
            a[i] = a[i]*"Plong"
        end
    end
    a
end
const str = make_str()
const nums = string.(1:1000)

function raindrops(i::Int)
    j=(i%3 == 0 && 1)|(i%5 == 0 && 2)|(i%7 == 0 && 4)
    j ==0  && return nums[i]
    return str[Int(j)]  
end

julia> @btime mapreduce(raindrops, (a, b) -> b, 1:1000)
  8.078 μs (0 allocations: 0 bytes)

Edit:
Ok now i see that realy a String should be returned, so one has to preallocate the numbers as well
Edit2: Fixes

6

I think this is faster if you avoid the conditionals in computing j

function raindrops(i)
    j=(i%3 == 0) + (i%5 == 0)<<1 + (i%7 == 0)<<2
    j == 0 && return nums[i]
    return str[j]  
end
6 Likes
7

Yes you are right… almost 2x

8

Nice little game for us optimization junkies. I wonder if it’s possible to improve on malacrois solution.

9

You can do a little better by using @inbounds. Note that I added return 0 < i <= 1000 ? nums[i] : string(i) so that the function could actually handle any positive integer, even if we’re only benchmarking up to 1000.

I don’t quite understand why an array is faster than a tuple here. I thought this discussion concluded that tuples rule for these kind of small lookups.

I also think it’s interesting that the lookup is faster when you statically create the number strings, but the if tree is faster when you don’t. I’m not sure why that is.

Results

const str = [
    "Pling",            # 001
    "Plang",            # 010
    "PlingPlang",       # 011
    "Plong",            # 100
    "PlingPlong",       # 101
    "PlangPlong",       # 110
    "PlingPlangPlong",  # 111
]

const nums = string.(1:1000)

# MatFi
function raindrops7(i::Int)
    j=(i%3 == 0 && 1)|(i%5 == 0 && 2)|(i%7 == 0 && 4)
    j == 0  && return i <= 1000 ? nums[i] : string(i)
    return str[Int(j)]
end

# malacroi
function raindrops8(i)
    j=(i % 3 == 0) + (i % 5 == 0) << 1 + (i % 7 == 0) << 2
    j == 0 && return i <= 1000 ? nums[i] : string(i)
    return str[j]
end

# lookup 2
function raindrops9(number)
    i = (number % 3 == 0) + (number % 5 == 0) << 1 + (number % 7 == 0) << 2
    i == 0 && return 0 < number <= 1000 ? @inbounds(nums[number]) : string(number)
    return @inbounds str[i]
end

# tuple lookup
function raindrops10(number)
    i =  (number % 3 == 0) + (number % 5 == 0) << 1 + (number % 7 == 0) << 2
    i == 0 && return 0 < number <= 1000 ? @inbounds(nums[number]) : string(number)
    return @inbounds (
        "Pling",            # 001
        "Plang",            # 010
        "PlingPlang",       # 011
        "Plong",            # 100
        "PlingPlong",       # 101
        "PlangPlong",       # 110
        "PlingPlangPlong",  # 111
    )[i]
end

With these results:

julia> titles = (
    "tree", "IOBuffer", "compact", "switch", "lookup", "ScottPJones", "MatFi", "malacroi",
    "lookup 2", "tuple"
)

julia> for (i, name) in zip(7:10, titles[7:10])
           print(name, ": ")
           @btime mapreduce($(Symbol(:raindrops, i)), (a, b) -> b, 1:1000) samples=10_000_000
       end
MatFi:   5.686 μs (0 allocations: 0 bytes)
malacroi:   3.981 μs (0 allocations: 0 bytes)
lookup 2:   3.611 μs (0 allocations: 0 bytes)
tuple:   4.706 μs (0 allocations: 0 bytes)
1 Like
10

Call it cheating but:

const str = [
    "Pling",            # 001
    "Plang",            # 010
    "PlingPlang",       # 011
    "Plong",            # 100
    "PlingPlong",       # 101
    "PlangPlong",       # 110
    "PlingPlangPlong",  # 111
]
const nums = string.(1:1000)
function raindrops9(number)
    i = (number % 3 == 0) + (number % 5 == 0) << 1 + (number % 7 == 0) << 2
    i == 0 && return 0 < number <= 1000 ? @inbounds(nums[number]) : string(number)
    return @inbounds str[i]
end
const lookup =map(raindrops9,1:1000)

function raindrops11(number)
    lookup[number]
end

julia> @btime mapreduce(raindrops11, (a, b) -> b, 1:1000)
   611.203 ns (0 allocations: 0 bytes)
4 Likes
11

If I call this cheating, I have to call all the solutions which use const nums = string.(1:1000) cheating, too. So, we should probably avoid const nums = string.(1:1000) and call it all cheating.

Anyways, nobody has found a better solution to the second category, where the strings have to concatenated at run time to some extent. That category is really what I’m more interested in anyway.

1 Like
12

Avoiding concatenating with the empty string seems to help

function raindrops(i)
    s = i%3==0 ? "Pling" : ""
    i%5==0 && (s = isempty(s) ? "Plang" : s*"Plang")
    i%7==0 && (s = isempty(s) ? "Plong" : s*"Plong")
    isempty(s) && (s=string(i))
    return s
end
1 Like
13

Damn, that’s fast. Hats off to you good sir.

On my machine:

tree:   19.720 μs (914 allocations: 42.84 KiB)  # best using literal values
compact:   31.287 μs (1256 allocations: 53.53 KiB) # best concatenation so far
malacroi2:   26.092 μs (1046 allocations: 46.97 KiB) # malacroi's new solution using concatenation
14

This feels a bit like cheating to the benchmark, but if we expect most input will fit in 32 bits and we’re working on 64 bit architecture, we can avoid the division of (%3, %5, and %7).

const b3 = Int64(gcdx(3,Int128(2)^64)[2])
const b5 = Int64(gcdx(5,Int128(2)^64)[2])
const b7 = Int64(gcdx(7,Int128(2)^64)[2])

function raindrops(i)
    if(i==i&0xffffffff)
        s = (i==(i*b3 % Int32)*3) ? "Pling" : ""
        i==(i*b5 % Int32)*5 && (s = isempty(s) ? "Plang" : s*"Plang")
        i==(i*b7 % Int32)*7 && (s = isempty(s) ? "Plong" : s*"Plong")
    else
        s = i%3==0 ? "Pling" : ""
        i%5==0 && (s = isempty(s) ? "Plang" : s*"Plang")
        i%7==0 && (s = isempty(s) ? "Plong" : s*"Plong")
    end
    isempty(s) && (s=string(i))
    return s
end

This would be slower if the test was run on larger integer inputs.

2 Likes
15

I’ve been able to do a bit better. Technically my solution is cheating since I have the literal value "PlingPlang", but I feel it’s still very much within the spirit of the rules.

# malacroi+
function raindrops8(n)
    f3 = n % 3 == 0; f5 = n % 5 == 0; f7 = n % 7 == 0
    f3 && (s = "Pling")
    f5 && (s = f3 ? "PlingPlang" : "Plang")
    f7 && (s = f3 | f5 ? string(s, "Plong") : "Plong")
    f3 | f5 | f7 && return s
    return string(n)
end

with results:

tree:   18.833 μs (914 allocations: 42.84 KiB)
compact:   31.504 μs (1256 allocations: 53.53 KiB)
malacroi2:   25.664 μs (1046 allocations: 46.97 KiB)
malacroi+:   22.369 μs (980 allocations: 44.91 KiB)
16

I tried continuing this format (see below), but the performance benefits are marginal and I think when I have two if statements in a line or the literal "PlingPlangPlong" in my solution, I really can’t pretend this is in the same category as the other solutions. At that point I might as well replace the last string(s, "Plong") with one more if and I’d have the tree solution, just a less readable version.

# malacroi++
function raindrops9(n)
    s = ""
    (f3 = n % 3 == 0) && (s = "Pling")
    (f5 = n % 5 == 0) && (s = f3 ? "PlingPlang" : "Plang")
    (f7 = n % 7 == 0) && (s = f3 ? f5 ? "PlingPlangPlong" : "PlingPlong" : string(s, "Plong"))
    f3 | f5 | f7 && return s
    return string(n)
end
17

If you have fun at this, you might enjoy my code golf challenge code golf - Cantor's unspeakable numbers - Code Golf Stack Exchange

18

Cleanest, fastest so far (aside from using an if tree with literal values).

function raindrops(n)
    (f3 = n % 3 == 0) && (s = "Pling")
    (f5 = n % 5 == 0) && (s = f3 ? "PlingPlang" : "Plang")
    (f7 = n % 7 == 0) && (s = f3 | f5 ? string(s, "Plong") : "Plong")
    return f3 | f5 | f7 ? s : string(n)
end

Thank you @malacroi and @MatFi for your creative solutions!

4 Likes