E. Choroba

Two Approaches

This blog post was inspired by the Task 1 of Weekly Challenge 396. Let’s start with the actual wording of the task:

You are given two arrays of integers, @order and @friends.
The @order (size n) contains every integer from 1 to n exactly once. The @friends contains IDs sorted in strictly increasing order.
Write a script to return the array containing IDs in finishing order.

Not clear? Let’s look at an example:

Input: @order = (3, 1, 4, 2, 5)
       @friends = (1, 2, 4)
Output: (1, 4, 2)

ID 1 finished 2nd.
ID 4 finished 3rd.
ID 2 finished 4th.

We want to sort the numbers in @friends in the same way as they’re sorted in @order. Therefore, my idea was to associate each ID with its order and then sort the IDs by the associated numbers:

sub finishing_order($order, $friends) {
    my %place = reverse %$order[0 .. $#$order];
    return sort { $place{$a} <=> $place{$b} } @$friends
}

So far, nothing really interesting going on. Well, we’ve used the index/value array slice to extract the indices and values from the array, but that was new in Perl 5.20 (released in 2014).

What surprised me was Mohammad’s solution to the task, published on the following Monday with Challenge 397.

sub finishing_order($order, $friends) {
    my %f = map { $_ => 1 } @$friends;
    return [grep {  $f{$_} } @$order];
}

No sorting is involved. We select @friends from the already sorted list by using a hash to distinguish them.

Naturally, my immediate thought was: “Which approach is faster?”

Benchmarking

I tried running both the implementation against various arrays of different lengths. I also always checked that their results are the same.

In the end, I saved the results of the benchmark for @order of sizes 2, 4, 8, 16, …, 2097152, with friends being 1, 5, 10, 20, 25, 33, 50, 66, 75, 80, 90, 95, and 100 percent of them. I used Benchmark to compare them, so a typical output was something like this:

1048576 25
     Rate   ch    m
ch 1.15/s   -- -25%
m  1.53/s  34%   --

To visualise the results, I selected the percentage on the “ch” line (i.e. -25 in this case) and plotted it into a 3D graph in gnuplot. The green area corresponds to combinations of sizes that make Mohammad’s solution faster, the red area is my winning territory, while the blue ribbon denotes we were even-stevens. You can see that for small friend groups, Mohammad’s algorithm is more favourable, but when everybody is friends with anyone else, my algorithm becomes faster.