Forem: Dave Saunders

What is the DRY principle?

Dave Saunders — Thu, 24 Mar 2022 10:25:59 +0000

.. and why it is NOT about duplicating code!

(originally sent to the :BaseClass Newsletter)

Why should I care?

The 'DRY' Principle - or 'Don't Repeat Yourself' is one of the most commonly quoted, but most commonly misunderstood pieces of guidance in programming.

While the premise is simple, it can lead to over-abstraction and hard to maintain code when misinterpreted.

Don't Repeat Yourself

The DRY principle was introduced in the book The Pragmatic Programmer in 1999.

The original definition is:

Every piece of knowledge must have a single, unambiguous, authoritative representation within a system.

So what does that mean?

Let's start with what it does not mean...

Misunderstanding the DRY principle

DRY is commonly used as an argument against writing the same line of code twice.

That's understandable. If we have to copy/paste some code we've already used, we immediately want to move it into a common abstraction - it's in our nature as programmers!

But writing the same line of code twice is not necessarily bad, and it is not what DRY is talking about.

Here's what one of the authors of the book that coined the term - Dave Thomas - said in a podcast interview:

DRY has come to mean “Don’t cut and paste”, but the original “Don’t repeat yourself” was nothing to do with code, it was to do with knowledge.

The perils of over-abstraction

There are some valid reasons to write the same block of code twice; the code might do the same thing but for different reasons or in different contexts.

Next time you're tempted to abstract two areas that look similar, ask yourself:

Do these sections of code have different reasons to change in future?

If so, abstraction might not be the right choice.

Once you've abstracted that code, you can't change one area without affecting the other - they are now coupled.

Maybe that's the right decision, and you might choose to abstract them anyway, but DRY doesn't insist that you should.

DRY is about 'knowledge'

DRY is about ensuring that any change to the functionality of your code happens in one place only.

We've all worked on code where a simple functional change needs far too many code changes.

If I want to change the way we format a user's name, I have to change it on the profile page, the confirmation emails, the invoice generator, the administration dashboard... you get the idea.

This is what DRY is warning against; there should be one place to make this change. The knowledge of how to format a user's name should be contained in
just one area of your code.

Next time I need to make that change, I know exactly where to go. Otherwise, it's only a matter of time before I forget one of the many areas I need to change and cause a bug.

Want to know more?

Check out these links:

What is Dynamic Programming?

Dave Saunders — Wed, 09 Mar 2022 15:57:09 +0000

(If you like this, you'll also like the BaseClass newsletter!)

What is it, and why should I care?

Dynamic programming is the process of breaking down a larger problem into smaller problems.

By using the answers to those smaller problems, we can find the overall solution more efficiently.

We'll also learn about the term 'memoization', and how it relates to dynamic programming.

How does it work?

The usual example of dynamic programming is the Fibonacci Sequence. It's a good example, so we'll use it here too.

If you're already familiar with the Fibonacci Sequence (and calculating it using recursion), then feel free to skip this next section.

If you're not sure what that means, or you want a quick refresher, read on...

This is a sequence of numbers, where each number is calculated by adding the previous two together:

Imagine I ask you to programmatically calculate the 6th number in the sequence (which is 8, as shown above).

How would you calculate it?

Here's some JavaScript code for a function that does just that:

function f(n) {
    // The first and second values are always 1
    if (n == 1 || n == 2)
      return 1;

    // Calculate the previous two values in the sequence
    // using this same function
    return f(n-1) + f(n-2)
  }

  // Calculate the 6th value in the sequence
  let answer = f(6)

This will work fine, but it's slow.

You can see that the function calls itself; it is recursive.

To calculate the 6th Fibonacci number, we first need to calculate the 4th and 5th Fibonacci numbers.

Each of those then have to calculate their previous numbers, and this repeats all the way down to the beginning of the sequence.

Here's what that looks like if we draw it out as a graph.

You can see that there's a lot of duplication here. For example, the 2nd value in the sequence is calculated 5 times!

For small numbers in the sequence, this isn't too bad, but it quickly gets worse. For later numbers in the sequence, this would soon become impractical, even on a modern computer.

So how do we do better?

Dynamic programming and memoization

One way we could improve this function is to store the results of our previous calculations as we go along.

That way, we only need to calculate each number in the Fibonacci sequence once.

This is the essence of dynamic programming:

Dynamic programming is breaking the larger problem into smaller problems, and using those to get to the answer.

Because we're achieving this by storing the previous results for later, we're also using 'Memoization':

Memoization is storing the result of a previous calculation so that we can use it later, to make the overall algorithm more efficient.

We could implement these concepts on the recursive approach above, but it's easier to follow if we use a 'bottom up' approach.

Let's look at the code first, and then we can discuss why this is called a 'bottom up' algorithm:

  function f(n) {
    // The first and second values are always 1
    if (n == 1 || n == 2)
      return 1

    let result = 0

    // Used to store the previous two results
    let lastButOneValue = 1
    let lastValue = 1

    // Work from item 3 of the sequence (items 1 and 2 are a 
    // special case, see above), calculate each value in turn
    for (let i = 3; i <= n; i++) {
      // Calculate this number by adding together the 
      // previous two
      result = lastValue + lastButOneValue

      // Update the values of the 
      // previous two items in the sequence
      lastButOneValue = lastValue
      lastValue = result
    }

    return result
  }

  // Calculate the 6th value in the sequence
  let answer = f(6)

Here, we calculate the Fibonacci sequence in order - all the way from the beginning - until we get to the number in the sequence that we need.

As we go along, we store the results of the previous value, and the one before that.

Getting the next value is then trivial.. just add those two together.

Here's the graph from the original (inefficient) algorithm again, but we've highlighted only the calculations we're making in this new version:

You can see that this time, rather than starting from the answer and working backwards, we work forwards until we reach the
value we need.

When we visualise it, we're working from the bottom of the graph upwards - hence a 'bottom up' approach.

This algorithm is much more efficient, there's no duplication at all!

We learned some new terms here, so let's recap:

Recap

Our latest algorithm uses dynamic programming, because we're breaking the bigger problem into smaller problems, and using their results
to get to the overall answer.

It also uses memoization, because we're storing the results of the previous step to avoid re-calculating them again later.

It was a 'bottom up' approach, because when we visualize the problem as a graph, we're working from the base of the graph upwards (rather than top-down, as in the less efficient algorithm).

Want to know more?

Check out these links:

What is TCP?

Dave Saunders — Wed, 23 Feb 2022 08:27:31 +0000

(my newsletter subscribers received this first)

TCP (Transmission Control Protocol) is a protocol for machines to communicate over a network, and is the foundation on which the internet is built.

One of the most useful characteristics of TCP is that it is 'resilient', which means it can cope with an unreliable network without losing any data.

This is possible because the machine receiving the data 'acknowledges' that it has received it. If the sender doesn't get this acknowledgement, it knows to re-send the data.

How does it work?

When we send data over a network, we normally group that data into 'packets':

At the beginning of each packet is the 'header'; a section of meta-data used to describe what is in the packet:

The TCP header has a special block called the 'Sequence Number'.

The Sequence Number is used to keep track of how many bytes have been sent and received by the two machines talking to each other.

The machine sending the data sets the Sequence Number to the number of bytes that have been sent in total during this conversation. It then sends the next block of data.
The machine receiving 'acknowledges' receipt of the data by adding the number of bytes it has received to the Sequence Number, and passing it back to the sender. It does this by setting a value in another part of the TCP header; the 'Acknowledgement Number'.

This simple mechanism allows us to detect when data has gone missing; if the sender sends 20 bytes, but the receiver only acknowledges 10, we know that some data has not been received.

There are various mechanisms for dealing with this, but the simplest is for the sender to simply re-send the data.

Randomising the Sequence Number

For security reasons, we don't want the Sequence Number to be predictable. If it was, it would be possible to 'hijack' the communication.

So, even though the Sequence Numbers track how many bytes have been exchanged, they don't start from 0. Instead, both parties generate random starting values for their Sequence Number.

But if these numbers are random, how do both clients agree on them?

This is where the 'TCP Handshake' comes in...

The TCP Handshake

When a connection is started, the first machine decides on its random 'Sequence Number' and sends it to the other party.

This transmission is called the SYN, because it is intended to 'SYNchronise' the Sequence Number.

The other side knows this is a SYN request, because we turn on a special bit in the packet header when sending it.

In this example, we've chosen 1234 as the random 'Sequence Number'.

The other party must now ACK or 'ACKnowledge' the Sequence Number.

It does this by adding 1 to it, and passing it back in the 'Acknowledgement Number' section of the header (it also sets a special ACK bit in the header).

It now generates its own random Sequence Number and sends it back to the other machine.

In this example, it generated 5678 as its Sequence Number:

Finally, the original party acknowledges the other machine's Sequence Number, also by adding 1 to it and sending it back in the 'Acknowledgement Number' section of the header:

The Handshake is now complete, and the clients can start communicating.

You might also see the TCP Handshake written as SYN, SYN/ACK, ACK, referring to the order the handshake packets are sent in.

Want to know more?

Check out these links:

What is Depth-First Search?

Dave Saunders — Sun, 20 Feb 2022 13:28:15 +0000

(my newsletter subscribers received this first)

In the last issue, we talked about 'Breadth-First Search' and 'Depth-First Search' as two of the most common algorithms we use when working with graphs.

Last time, we looked at Breadth-First Search (BFS).

Today, we'll cover the other, Depth-First Search (DFS).

Why should I care?

A lot of algorithms are implemented for you as part of your chosen language. That means that they are interesting to learn about, but that you'll
rarely write them yourself.

Graph traversal algorithms are different.

We use graphs all the time, from linking related products in an e-commerce application to mapping relationships between people in a social network.

Searching a graph is something that is not only useful in theory, but that you will almost certainly need to do in practice too.

In 5 minutes or less:

Here's a graph data structure:

The 'nodes' in the graph (A-F) are called 'vertices'. Each vertex is connected to one or more others with 'edges', which are the lines between the nodes.

But a graph is only useful if we can do something with it; we might want to find out whether a certain element is stored in our graph, or how many 'hops' it takes to get between two elements.

These kinds of problems are called 'graph traversal', and 'Depth-First Search' (or 'DFS') is one algorithm to do this.

Let's take a look...

How Depth-First Search works

In this issue, we looked at the 'stack' data structure.

You'll recall that it is a 'First In Last Out' data structure; the first item to be added to the stack will be the last item to be removed:

The stack is the basis for Depth First Search.

Here's a summary of the algorithm:

Pick any unvisited connected node, add it to the stack, and mark it as 'visited'
From the node we just picked, do the same thing again.
Repeat until we end up at a node with no unvisited connections
Pop the top item from the stack, and repeat the whole process again from the next item down
When the stack is empty, we're done!

This sounds much more confusing than it is in practice, so let's walk through an example...

Implementing DFS

We start by picking a place to start, we'll choose A.

The first step is to add A to the stack and mark it as 'visited':

Now, we need to repeat the following steps:

Pick any unvisited connected node, add it to the stack, and mark it as 'visited'

From the node we just picked, do the same thing again.

Repeat until we end up at a node with no unvisited connections

So, let's pick a connected node and get started.

Both B and C are connected to A. We haven't visited either, so we can pick either one to visit next. Let's pick B.

From B, we can either visit A, D or E. We've already visited A, so we ignore that one. Let's pick D.

We add D to the stack and mark it as 'visited', just like we did before:

From D there are no unvisited nodes to visit. It's only connected to B, and we've just been there.

So, now it's time to do this:

Pop the top item from the stack, and repeat the whole process again from the next item down

We'll pop D off of the stack and go back to the node underneath it.. which is B.

Now we're back at B, we'll just do the same thing all over again...

There's one unvisited node - E - so we'll visit it and add it to the stack:

E has no unvisited neighbours. When we pop that off of the stack we'll see that neither does B, so we pop that one off too:

That has brought us right back up the top of the graph again, to A.

I'm sure you have the hang of this by now; we'll keep picking an unvisited connected vertex and adding it to the stack.

After adding C and F in that way, this is what the stack looks like:

Since F has no unvisited connections, we pop it off of the stack. The same will apply to the next item down - C - and then A.

That leaves us an empty stack, meaning we're done!

Applications of DFS

The DFS algorithm is useful when we are looking for an item that we know is likely to be at the bottom of the graph. Unlike Breadth-First search, DFS dives straight to the bottom of the graph, before working its way back up.

Imagine we have a family tree, and we're looking for the youngest member. We know they're going to be at the bottom of the tree, so DFS might be a better choice in that case.

In cases where the item you are searching for is likely to be at the top of the graph, consider 'Breadth-First search'. When the item is likely to be nearer to the bottom, consider 'Depth-First search'

Want to know more?

Check out these links:

What is Breadth-First Search?

Dave Saunders — Thu, 03 Feb 2022 18:26:45 +0000

(my newsletter subscribers received this first)

Breadth-First Search and Depth-First Search are two of the most common algorithms we use when working with graphs.

Here we'll look at the first of those, Breadth-First Search.

Why should I care?

A lot of algorithms are implemented for you as part of your chosen language. That means that they are interesting to learn about, but that you'll
rarely write them yourself.

Graph traversal algorithms are different.

We use graphs all the time, from linking related products in an e-commerce application to mapping relationships between people in a social network.

Searching a graph is something that is not only useful in theory, but that you will almost certainly need to do in practice too.

In 5 minutes or less:

Here's a graph data structure:

The 'nodes' in the graph (A-F) are called 'vertices'. Each vertex is connected to one or more others with 'edges', which are the lines between the nodes.

But a graph is only useful if we can do something with it; we might want to find out whether a certain element is stored in our graph,
or how many 'hops' it takes to get between two elements.

These kinds of problems are called 'graph traversal', and 'Breadth-First Search' (or 'BFS') is one algorithm to do this.

Let's take a look...

How Breadth-First Search works

In the last issue, we looked at the 'queue' data structure.

You'll remember that it's a 'First In First Out' data structure; the first element to be added is the first element to be processed (or 'dequeued').
If you're last in the queue, you'll be processed last:

We'll use a queue to implement Breadth-First Search (BFS).

This is the BFS algorithm:

Pull the next 'vertex' from the queue
For each vertex connected to this one (that we haven't already visited) mark it as 'visited' and add it to the queue
Repeat until the queue is empty

By doing so, we're radiating outwards from our starting point; visiting all of the nodes directly connected to the starting point first. Then, visiting all
of the nodes connected to those, etc.

This will make more sense as we work through it...

Implementing BFS

We start by picking a place to start, we'll choose A.

So, the first step is to add A to the queue and mark it as 'visited':

You'll remember that the BFS algorithm requires us to repeat the following steps until the queue is empty:

Pull the next 'vertex' from the queue

For each vertex connected to this one (that we haven't already visited) mark it as 'visited' and add it to the queue

A is the first (and only) element in the queue.

A is connected to both B and C. We haven't visited either of those, so we'll add them to the queue and mark them as visited:

Now, we repeat the same thing again.

B is next in the queue.

B is connected to A, C, D and E. We've already visited A and C, so we only queue up D and E (and mark them as visited):

You can probably see where this is going...

Next, we dequeue C. It is connected to A, B and F. The only one we haven't already visited is F, so we add that to the queue and mark it as 'visited':

We now have F, E and D left in the queue...

We'll dequeue each of them in turn, looking for any connected vertices that we haven't visited yet - but we won't find any.

After we've checked each of those, the queue is empty and we're done - we've visited every node:

Applications of BFS

This is all very well, but what would we use it for?

Suppose we're building a social network like LinkedIn.

The 'graph' in this case would be the map of all connections between people.

If we wanted to find out whether 'Bob' knew 'Jennie' through one or more mutual friends, BFS would be a great choice.

We'd start at Bob, and radiate outwards until we found Jennie (or until we were far enough away from Bob that we've given up).

Or, the graph could be a map of a subway, and the 'how many mutual friends between Bob and Jennie' problem could instead be
'how many changes does it take to get between two stations'.

Once you learn about graphs and algorithms like Breadth-First Search, a lot of problems start to look like these.

Want to know more?

Check out these links:

What are Linear Data Structures?

Dave Saunders — Wed, 02 Jun 2021 19:58:14 +0000

(my newsletter subscribers received this first)

We say a data structure is 'linear' if the items inside it are stored in a sequence.

Arrays, linked lists, and stacks are all linear data structures.

Why should I care?

We use these data structures every day in programming.

Even if you're already familiar with them, it's helpful to recap them occasionally.

In 5 minutes or less:

As we said in the introduction, a data structure is 'linear' if the elements form a sequence.

That means that the data structure has a first and last element, and each element is connected to its previous and next element.

An 'array' is a linear data structure; the items are stores sequentially.
A 'graph' is not a linear data structure; any node can be linked to any other node in the graph - there is no fixed 'sequence'.

(if you're not familiar with graphs, don't worry - there's a newsletter coming up that explores them in detail).

Let's take a look at some common linear data structures...

Arrays

If you've done any programming, you're almost certainly familiar with the concept of arrays.

An array is like a bookcase; the items are stored next to each other, but we can jump to any item we like to read it.

The items in the array have an 'index' that allows us to reference them directly.

The ability to jump to any item we like to read its value is called 'random access', and is a huge advantage of an array.

We take this for granted, but this is not a property that many other 'linear data structures' have, as you'll see below.

When we allocate an array, we have to determine up-front how much space we need.

If we fill our array, we have to stop and allocate some more space. That means that while normal inserts into the array are very fast,
occasionally we have to pause for a short time to make the array bigger - which takes some time.

Linked Lists

A linked list is a data structure where each item points to the next. We can't jump to any element directly like we can with
an array. Instead, we have to access them in turn:

Linked lists are useful because, unlike an array, we don't need to decide up-front how much space we need. If we need to add a new item,
we simply add it to the end.

That means that adding the 200th item has the same cost as adding the 2nd item. This predictable performance is an advantage of a linked list.

It's also easy to add or remove an item from the middle of the linked list, by simply changing some 'next' pointers.

Here's how we'd remove an item from a linked list:

This would be more difficult to do in an array, as we'd have to shift all of the remaining items to account for the new or removed item.

A variant of the linked list is the 'doubly-linked list', where each element not only points to the next element, but also the
previous one.

This means we can traverse the data structure in either order, but still have the advantages of a linked list.

Queues

The queue is a 'First In First Out' (FIFO) data structure. That means that items are read in the same order that they are inserted.

This is just like the queue at the store, the first person to join the queue
is the first person to be served.

A printer queue is a good example of this data structure in use. The printer will print items in the order in which they were queued. If you
send your document to the printer last, it will be the last thing to be printed.

Queues are also useful as 'buffers'.

Suppose we have two separate systems, one that reads messages and one that processes them. We don't want the system
that reads messages to have to wait for each message to be processed before listening for another.

Putting a queue between them allows us to
'de-couple' those systems. The read process can keep adding items to the queue, safe in the knowledge the the processing side will pull the items
off of the queue and process them eventually - no waiting required.

Stacks

The stack is a 'Last In First Out' data structure; the last item to be added is the first item to be read.

You can think of this like a stack of plates, the last plate to be added to the pile is the first plate we'd take off again:

You might use a stack to implement 'undo' functionality, for example. The last task the user performed is the first one to be reversed when they click the 'undo' button.

The 'call stack' we see every day when running code is also a great example of a stack, but that's a topic for a future article!

Want to know more?

Check out these links:

What is Jaro-Winkler Similarity?

Dave Saunders — Fri, 14 May 2021 12:20:30 +0000

Jaro-Winkler similarity is a way of measuring how similar two strings are. It is fairly easy to understand and quick
to implement.

(this was originally sent to my newsletter subscribers)

Why should I care?

String similarity metrics have various uses; from user-facing search functionality to spell checkers.

There are a few common string similarity metrics. Knowing a little about each will help you to choose the right one,
should you ever need to implement something like this yourself.

Jaro Similarity, and the modified version - Jaro-Winkler - are two common ones.

In 5 minutes or less:

Imagine we're building the search functionality for an app store.

If a user misspells their search, we'd like to be able to suggest the app we think they were looking for.

For example; the user is searching for the 2009 viral hit farmville, but badly mistypes it as:

If we could compare this search string to all of the titles in our app store, we could show the user the apps that
most closely match what they typed.

This is where the Jaro Similarity metric comes in...

Jaro Similarity

Let's calculate the similarity between the user's search string and the correct app title:

Created by Matthew A. Jaro in 1989, the Jaro Similarity metric compares two strings and gives us a score that
represents how similar they are.

The result is a number between 0 and 1, where 0 means the strings are completely different and 1 means they match exactly.

The first step to calculating the Jaro similarity is to count the characters that match between the two strings.

But, to be considered a 'match', the characters do not need to be in the same place in both strings -
they just need to be near to each other.

This accounts for the common typing mistake where you accidentally enter some characters in the wrong order.

How near those characters need to be before we consider them a match is calculated as follows:

Both of our strings are 9 characters long. That gives us a result of 3.

That means that any two characters in our strings 'match' if they are either:

In the same place in both strings
No further than 3 characters away from each other

Here's what it looks like if we draw these matches:

If there were no matches, we wouldn't need to go any further - the Jaro Similarity would simply be 0.

We have 8 matching characters though, so the next step is to calculate the number of 'transpositions'.

Transpositions are the characters that match, but are in the wrong order. We count them, and then we half that number.

Our strings have 2 matching characters that are in a different order (the final e and l are backwards in the user's search term).
Halving this gives us 1 'transposition'.

Now all we have to do is plug these numbers into the following formula
(we use the term simj to mean 'Jaro Similarity' - the thing we're calculating):

This looks complex, but we really only need a few values:

|S1| and |S2| are the lengths of the two strings we are comparing (ours are both 9 characters long)
m is the number of matches - we have 8
t is the number of 'transpositions' - we have 1

Given those values, this is the Jaro Similarity for faremviel vs farmville:

Our strings have a similarity of 0.88, which means that they are very similar.

If we calculate the Jaro Similarity of the user's search term against other games in our app store,
it becomes clear what the user was intending to search for:

'faremviel' vs 'farmville': 0.88
'faremviel' vs 'farmville 2': 0.83
'faremviel' vs 'clash of clans': 0.46
'faremviel' vs 'minecraft': 0.31

Jaro-Winkler Similarity

This modification of Jaro Similarity was proposed in 1990 by William E. Winkler.

The 'Jaro-Winkler' metric takes the Jaro Similarity above, and increases the score if the characters at the start of both strings are the same.

In other words, Jaro-Winkler favours two strings that have the same beginning.

This is the formula for the 'Jaro-Winkler Similarity':

We need the following values to use it:

simj is the Jaro Similarity of our comparison above (0.88)
l is the number of characters that are the same at the start of both strings (up to a maximum of 4). Our strings both start with f a r, so we use a value of 3 for this.
p is the 'scaling factor'. 0.1 is usually used.

This is the Jaro-Winkler calculation for faremviel vs farmville:

Two strings with no matching characters at the start would keep the same score, but because our
strings have letters in common at the beginning, this version of the metric has boosted our score
from 0.88 up to 0.92.

Whether Jaro or Jaro-Winkler is the right choice depends on your specific use case. Try both (and other string similarity algorithms), and see what
works best for your data.

Want to know more?

Check out these links:

What Are Floating-point Numbers?

Dave Saunders — Fri, 30 Apr 2021 18:51:22 +0000

(from last week's BaseClass newsletter)

Floating-point is a way of storing numbers in binary. It allows us to store a very large range
of values using a fixed amount of space.

Why should I care?

Have you ever wanted to know:

Why 0.1 + 0.3 does not always equal 0.4?
How we store non-integer numbers in binary?

In 5 minutes or less:

You may be familiar with how we represent a number in binary.

Each bit represents a power of 2, and by combining them we can produce every whole number:

But what happens when we need to represent something that isn't an integer, like 2.5?

Let's split the 8 bits in half.

We'll use the 'left' half to represent the number before the decimal point (2 in our example),
and the 'right' half to represent the fraction after the decimal point (0.5, or ½ in this case).

In this system, 2.5 would be represented as 0 0 1 0 1 0 0 0:

We can represent fractions now, but we've lost a lot of range.

We can't represent 16.0 in this format, for example. There just aren't enough bits on the left of the point.

We could just keep adding more bits to store larger numbers, but this format is still quite limited.

Sometimes we want to store very large numbers, in which case we'd like more bits on the left. Other times, we'd
like to store very small fractions, in which case we would need fewer bits on the left, and more precision on the right,

This is what floating-point is; a way of storing numbers that allows the point to move to represent a larger
range of values.

The standard for float values is called 'IEEE 754', which defines both 32 and 64-bit floating-point (or 'float') values.

Each 32 or 64-bit float is split into 3 sections.

The first bit represents the 'sign'; 0 for a positive number, or 1 for a negative number
The next 8 bits are called the 'Exponent'
The final 23 bits are the 'Mantissa'

We use these 3 values in a formula, which gives us the number that the float represents:

You don't need to understand this formula, just know that this way of storing
numbers means we can represent a much larger range.

By making the 'exponent' value larger or smaller we can represent very small fractions, or very
large numbers.

That's why it's called 'floating-point', it doesn't have a fixed point like our original example. Instead, the
point 'floats', or moves, depending on the size of the 'exponent'.

Rounding errors

There are some numbers we can't represent exactly using our standard decimal system.

For example, we can't represent ⅓ exactly in decimal:

⅓ = 0.3333333...

This is also true of some numbers in binary; they cannot be represented exactly.

For example, let's try to represent 0.1 in binary.

Again, the values after the decimal point represent the fractions:

This is very close to 0.1 - and it's the best we can do in this example - but it is not exactly 0.1.

The fact that our point can 'move' means that we can add more precision to this fraction if we like,
but the fact remains that we just cannot represent some numbers exactly in binary.

This can lead to some interesting rounding errors.

If you try to calculate 0.2 + 0.1 in JavaScript, you'll get an answer of 0.30000000000000004:

This is very close to the correct answer, but it's not exactly the correct answer.

With this in mind, we usually compare floating-point numbers by checking the difference
between them.

For example, instead of
checking whether two numbers are equal, we would check that the difference between them is very small.

Math.abs(result1 - result2) < 0.001

This is a simplified example, of course. In reality, you would choose a tolerance appropriate to the calculation you are doing.

Want to know more?

Check out these links:

What is CAP Theorem?

Dave Saunders — Fri, 16 Apr 2021 08:14:38 +0000

CAP Theorem describes the decisions we have to make when building a distributed data store.

Let's take a look at CAP Theorem, in under 5 minutes...

(my newsletter subscribers received this first)

Why should I care?

Have you ever wanted to know:

How distributed databases handle network failures?
What tradeoffs we must make when designing distributed data stores?

In 5 minutes or less

Eric Brewer's CAP Theorem tells us that a distributed data store must choose no more than two of the following:

Consistency
Availability
Partition Tolerance.

What do those definitions mean, and why can't we have all three?

Let's imagine we're designing a distributed database.

For simplicity our database will have just two interconnected instances, or 'nodes':

Partition Tolerance

Partition Tolerance means that one or more nodes in our distributed system can be split up and unable to communicate with each other (partitioned), and the system can still function.

Only a complete network failure is allowed to cause the system to respond incorrectly, anything else must be tolerated.

If we have a single node then there can be no partitions. But, in a distributed system, faults are inevitable given enough time. Therefore we cannot sacrifice Partition Tolerance.

With that in mind, we can actually re-state the problem like this:

In the event of a Partition, should we choose either Consistency or Availability?

Imagine there's a fault in our system, and the connection to one of the nodes is broken. Our distributed database is now partitioned.

Somebody tries to update a record on one of the nodes.. What do we do now?

Choosing Consistency

'Consistency' in CAP Theorem means that I can update a record on one node, and somebody reading from another node will immediately see the
effect of my update.

(Note: this is specifically called 'linearizable consistency').

Obviously, instant communication isn't realistic in a distributed environment, so in practice, the goal is to reduce this to a level where we don't notice it.

This is a really useful property if you are a banking system. It would be a big problem if I could withdraw money from one ATM, then walk down the road to another ATM and withdraw the same amount again, because the database was not consistent across all nodes.

The nodes in our example database can no longer communicate, so we cannot reflect a change across all nodes 'instantly'.

So, if we want to make sure both nodes stay 'consistent', there are a few ways to handle this. We could shut down entirely, or refuse all updates and only allow reads, for example.

Because we can't accept the update request though, we are sacrificing availability...

Choosing Availability

'Availability' means that if we make a request to any working node, we must get a non-error response, regardless of any partitions in the system.

The data is allowed to be out of date, or 'stale', but it must be available.

Twitter is a good example of a system where we might choose Availability. If I 'like' a tweet, but the other nodes don't reflect that 'like' immediately, it's really not the end of the world.

In this case, it's more important for the system to be 'available' and accept the update than to be 'consistent'.

In our example scenario, we could continue to allow clients to read and write to nodes on both sides of the partition:

That would give us a system that is Available, but because there's no way for those nodes to keep their information in sync while partitioned, it's impossible for this to be (immediately) Consistent too.

This problem is the root of CAP Theorem. We cannot have both Consistency and Availability in the event of a partition (a loss of communication between nodes).. we must choose between the two.

Want to know more?

Check out these links:

Comparing strings in JavaScript

Dave Saunders — Tue, 13 Apr 2021 04:39:46 +0000

This is extracted from the much larger post: The Complete Guide to Working With Strings in Modern JavaScript

Equality

When you know you are comparing two string primitives, you can use either the == or === operators:

"abba" === "abba" // true
"abba" == "abba" // true

If you are comparing a string primitive to something that is not a string, == and === behave differently.

When using the == operator, the non-string will be coerced to a string. That means that JavaScript will try and make
it a string before comparing the values.

9 == "9"
// becomes 
"9" == "9" //true

For a strict comparison, where non-strings are not coerced to strings, use ===:

9 === "9" // false

The same is true of the not-equal operators, != and !==:

9 != "9" // false
9 !== "9" // true

If you're not sure what to use, prefer strict equality using ====.

When using String objects, two objects with the same value are not considered equal:
   new String("js") == new String("js") // false
   new String("js") === new String("js") // false

Case sensitivity

For case-insensitive comparisons, do not convert both strings to upper or lowercase and then compare them, as this is unreliable with some characters.

Instead use localeCompare:

let a = 'Résumé';
let b = 'RESUME';

// Incorrect: returns 'false'
a.toLowerCase() === b.toLowerCase()

// Correct: returns '1'
a.localeCompare(b, undefined, { sensitivity: 'accent' })

localeCompare is supported in the following browsers

Greater/less than

When comparing strings using the < and > operators, JavaScript will compare each character in 'lexicographical order'.

That means that they are compared letter by letter, in the order they would appear in a dictionary:

"aardvark" < "animal" // true
"gamma" > "zulu" // false

When comparing strings using < >, lowercase letters are considered larger than uppercase.

"aardvark" > "Animal" // true

This is because JavaScript is actually using each character's value in Unicode, where lowercase letters are after uppercase letters.

True or false strings

Empty strings in JavaScript are considered false when compared with the == operator
(but not when using ===)

("" == false)  // true
("" === false) // false

Strings with a value are 'true', so you can do things like this:

if (someString) {
    // string has a value
} else {
    // string is empty or undefined
}

What is Bubble Sort?

Dave Saunders — Fri, 02 Apr 2021 14:02:49 +0000

Originally sent to subscribers of the BaseClass newsletter

Probably the simplest of sorting algorithms, Bubble Sort is inefficient at scale but quick to write and works fine on a handful of elements.

It is an excellent introduction to more complex sorting algorithms.

In 5 minutes or less:

Let's sort this array into ascending order:

Step 1: Compare pairs of elements

We're going to loop through each pair of elements in turn.

If a pair of elements aren't in the right order, we'll swap them.

Let's go...

The first pair is already in the correct order, so we can ignore them.

On to the next pair. These elements are in the wrong order, so we'll swap them.

And finally, the last pair, which also need to be swapped:

We've now looped through all of the pairs, so our first pass through the array is done.

This is how the array looked at the beginning and end of this first pass:

Notice how the highest value, 9, moved up through the array and into the correct place:

It has 'bubbled up' to the correct position - hence 'Bubble Sort'.

Step 2: Repeat

Our first pass moved the highest element, 9, into the correct place.

Each time we repeat this loop, we move the next highest element into place.

Now, we repeat this process - comparing each pair in turn and swapping them if required - until the array is completely sorted.

We have 4 elements in the list, which means we'll need to repeat our loop 3 times.

Why 3? Because once 3 of the elements are in the correct place in the array, the remaining one must also be correct.

If the number of elements in our array is n, the number of loops we'll need is n-1.

Here's the state of our array after each pass. The sorted elements after each loop are highlighted.

Here's the JavaScript code for this algorithm:

  // We need to repeat the algorithm n-1 times
  for (let loop = 0; loop < array.length - 1; loop++) {

    // Loop through each pair of elements
    for (let pair = 0; pair < array.length - 1; pair++) {

      // Is this pair the wrong way around?
      if (array[pair] > array[pair + 1]) {   
        // Make the swap (using temporary variable)
        let tmp = array[pair]
        array[pair] = array[pair + 1]
        array[pair + 1] = tmp
      }      
    }
  }

We can improve on this basic algorithm though, with a couple of optimisations.

Optimisation #1

Remember how the first pass of the algorithm caused the 9 to bubble up into the correct position?

After that first pass, we know that the last element is correctly placed, so we can ignore it on our next loop. After the second pass, the second-to-last element is sorted, and so on.

We'll change our code to ignore the last element after the first loop, the last two after the second loop, and so on.

This will make our algorithm very slightly quicker.

Here's the updated code. Notice that the limit for the inner loop is now array.length - loop - 1:

for (let loop = 0; loop < array.length - 1; loop++) {
  for (let pair = 0; pair < array.length - loop - 1; pair++) {
    if (array[pair] > array[pair + 1]) {
      let tmp = array[pair]
      array[pair] = array[pair + 1]
      array[pair + 1] = tmp
    }
  }
}

Optimistion #2

Imagine our algorithm was passed an array like this:

This array is already sorted, doing three loops of our sorting algorithm is a complete waste of time.

This leads us to our next optimisation; if we ever complete a loop without swapping any elements, we know the array is sorted and we can stop early.

That could be a big time saving when the array is already sorted - or nearly sorted - before we even start our Bubble Sort.

With that code added, our final Bubble Sort algorithm looks like this:

  for (let loop = 0; loop < array.length - 1; loop++) {

    let hasSwapped = false;    

    for (let pair = 0; pair < array.length - loop - 1; pair++) {
      if (array[pair] > array[pair + 1]) {
        let tmp = array[pair]
        array[pair] = array[pair + 1]
        array[pair + 1] = tmp      
        hasSwapped = true;
      }
    }    

    if (!hasSwapped) {
      // No swaps, the array is now sorted
      break;
    }
  }

Want to know more?

Check out these links:

What is The Travelling Salesman Problem?

Dave Saunders — Sat, 13 Mar 2021 08:43:09 +0000

Originally sent to subscribers of the BaseClass newsletter

The Travelling Salesman Problem is a classic computer science problem, known for having no efficient solution.

Why should I care?

There are many real-life problems that are very similar to the Travelling Salesman Problem.

Learning about problems like this will help you to recognize when you're facing something equally difficult to solve.

In 5 minutes or less:

This is the 'Travelling Salesman Problem' (or TSP):

Given a list of cities, what is the shortest route that visits each city once and then returns to the origin city?

It sounds simple, but when we add enough cities it becomes impossible for a computer to solve in a realistic time frame.

Let's see why..

The 'brute force' approach.

There's only one way to find the shortest solution to the Travelling Salesman Problem, we have to try every possible option in turn.

We'll pick a simple example, four cities:

We'll start from A. We can go to either B, C or D next, Let's imagine that we go to B. From there, we have the option to visit either C or D. Once we get to either of those, we then travel to the remaining city before returning back to A.

To recap; from our first city we have 3 choices of where to go next. Once we pick one of those, we have 2 remaining cities to choose from. From there, there’s only 1 city left.

That means that the total number of routes we must try is 3 x 2 x 1 = 6.

Now let's add another city, 'E':

Once we pick a place to start, we now have a choice of 4 others cities to visit. From each of those, we have to pick one of the remaining 3 to visit next. From each of those, there are 2 cities to pick from.. you get the idea.

The number of possible permutations for five cities is 4 x 3 x 2 x 1 = 24. We've added one city, but there are now four times the number of options!

Some of these routes are duplicates (we travel the same route, but in reverse) so they can be discounted. That doesn't really help us though, as the number of possible routes will still grow very quickly.

With only 10 cities, there are 181,440 possible routes. Add one more and there are now over 1.8 million. By the time we get to just 15 cities, there are over 43 Billion possible routes!

With enough cities, the number of routes becomes so large that we just couldn't compute it in a reasonable timescale.

There is a relatively more efficient method to calculate all possible permutations using dynamic programming, but it doesn't matter - it still becomes too slow at scale.

'Solving' the TSP

Since we can't truly solve this problem, the best we can do is look for a good approximation.

One way to do this is using the Nearest Neighbor method:

Starting from a random city, pick the nearest city and go there. Keep picking the nearest city until you've been to all of them once, before returning back to the starting point.

This is the simplest algorithm to find an approximate solution, but there are other algorithms (with varying complexity) that can usually find shorter routes.

Until recently, the best has been an algorithm developed in 1976 by Nicos Christofides.

Christofides' algorithm is capable of finding solutions that are at most 50% longer than the 'perfect' trip.

In 2019, Karlin, Klein and Oveis Gharan proved that an algorithm originally developed in 2010 could actually beat Christofides' algorithm by a tiny fraction of a percent.

This may not sound significant, but it proves that it is possible to improve on that algorithm, and opens the door for more solutions.

The TSP in disguise

It's easy to dismiss the Travelling Salesman Problem as a purely academic problem, not applicable to every day development. It does, however, have real world implications.

'Last Mile Delivery' is the commonly used example. This is the process of delivering something from a transport hub to its final destination. For example, the Amazon truck delivering hundreds of parcels to individual houses.

When you look closer though, other problems start to look sightly like the TSP:

What is the quickest way to pick items in a warehouse to fulfill an order?
How can we schedule a bus route to visit all of the stops in the shortest time/distance?
What is the shortest way to route the wiring in an electrical component?

The Travelling Salesman Problem is in a class of problems called 'NP-hard'. We'll cover 'NP-hard' in another issue, but learning about NP-hard problems like the TSP will help you to recognise when you're facing something similar in your own work.

Need to calculate every possible permutation of things in a collection? That sounds a lot like the Travelling Salesman Problem.

Want to know more?

Check out these links: