Advent Of Code 2020 – Day 1 Performance

Advent Of Code 2020 – Day 1 Performance

A Need For Speed

Following on from yesterday post about solving Part 1 for Day 1 (found:https://nerdrays.azurewebsites.net/?p=37)

In yesterday’s post, we looked at the first day of Advent Of Code 2020 challenge. Today we’re going to look at my optimised code that was implemented to improve performance. But what are the actual results and is the payoff worth it? 

Again we shall be looking at the following languages: PowerShell, Python, JavaScript & C#. My technique to improve the scripts is the same for each solution. We will look at the original code and the time it took then we will look at the optimised code and the time that is taken to run. 

Once we’ve got all our results we’ll look at the overall results to see if there are any differences from the different solutions. 

For each set, I ran it 3 times to get the average time taken to complete the task. 

Day 1 – Part 1

Given the input find two numbers that add up to 2020 with these numbers multiply them.

PowerShell

This was my original solution, we loop through the file and for each input, we loop the file again and check to see if each number matches with the original input matches 2020 then multiply them together.

foreach ($one in $input) {
        foreach ($two in $input) {
            if ($two -ne $one) {
                $counted = [int]$two + [int]$one
                if ($counted -eq "2020") {
                    $results = [int]$i * [int]$one
                }
            }
        }
}

Results: 258ms

To improve performance the script was amended to run through the numbers once, instead of looping through the same list for each number again, we know the final number we require so we can minus out the current number from 2020 and see if those results exist within our list.

foreach ($i in $content) {
        $tofind = 2020 - [int]$i
        if ($content.Contains($tofind)) {
            $results = [int]$i * [int]$tofind
            break
        }
}

Results: 9.6ms

This shows a 77% increase in performance in changing the method; let’s see how the other scripts stack up.

C#

foreach (int item in content)
{
        foreach (var item2 in content)
        {
          int value = item + item2;
          if (value == 2020)
          {
              int results = item * item2;
              return results;
          }
         }
}

Results: 0.0047014ms

foreach (int item in content)
{
     int toFind = 2020 - item;
     if (content.Contains(toFind))
     {
           int results = item * toFind;
           return results;
     }
}

Results: 0.0034611ms

Compared to PowerShell our first run without being optimised was running a lot faster. Again we saw an increase in performance between the initial design and the improved design. Though this isn’t as big a gap as seen within the PowerShell script.

JavaScript

for (let element of array) { 
    for (let element2 of array) { 
        var value = parseInt(element) + parseInt(element2)
        if (value == 2020) { 
                results = parseInt(element) * parseInt(element2)
        }
    }
}

Results: 13ms

for (let element of array) { 
      var toFind = 2020 - parseInt(element)
      if (array.includes(`${parseInt(toFind)}`)) {
             results = parseInt(element) * parseInt(toFind)
      }
}

Results: > 1ms

JavaScript has a fantastic performance boost as well between the two versions beating out the PowerShell script as well.

Python

for a in lines:
    for b in lines:
        c = a + b
        if c == 2020:
            results = a * b
            end_Time = time.time()
            final_Time = end_Time - start_Time
            break

Results: 0.00316ms

for a in lines:
        toFind = 2020 - a
        if toFind in lines:
            resultsa = a * toFind
            end_Time = time.time()
            final_Time = end_Time - start_Time            
            break

Results: 0.00499ms

Python ran similar to C# with had a fantastic performance in both the original and the optimised, although we do see a speed reduction over the runs for Python on the improved script.

As we can clearly see not all languages act the same. But things become more interesting when you start to look at Part 2 of the first day for Advent of Code 2020. 

This time we need 3 digits to make up the sum of 2020. So now we’re going to look through the array at least twice to find the third matching number, but this is where we show our biggest gains. PowerShell made the biggest gain difference when we optimise on a heavier load. 

If continuing the logic and including another foreach loop to find 3 numbers out results take 1:13s to complete.

But if we combine 2 loops and a contains we bring that same result down to 300ms, this only shows to potential increase required for each loop. 

All other languages took less than a second or two to complete the actions even without the optimisation. 

Looking at the results, although all languages are able to complete the task, the best languages to use were between C# and Python, JavaScript was a close second and PowerShell was by far the slowest. It does show that planning when writing your solution can change the outcome and time drastically.

Have you completed this challenge from Advent Of Code? If so what language did you complete it in? Did you get better times than what I’ve seen above? Leave a comment below.

Leave a Reply

Your email address will not be published.