DEV Community: Danny Adams

What is Polymorphism in C# - Explained with a Code Example

Danny Adams — Thu, 24 Oct 2024 16:26:20 +0000

The word polymorphism is derived from Greek, and means "having multiple forms":

Poly = many
Morph = forms

In programming, polymorphism is the ability of an object to take many forms.

To help you to understand polymorphism, we will first go through an example that doesn't use polymorphism. We will then discuss the issues with this solution, then refactor it to use polymorphism. This will give you a good understanding of what polymorphism is, and its ability to make software more flexible, extendable, testable, readable and elegant.

A bad example with no polymorphism:

public class Car
{
 public string Brand { get; set; }
 public string Model { get; set; }
 public int Year { get; set; }

 public int NumberOfDoors { get; set; }

 public void Start()
 {
   Console.WriteLine("Car is starting.");
 }

 public void Stop()
 {
   Console.WriteLine("Car is stopping.");
 }
}

public class Motorcycle
{
 public string Brand { get; set; }
 public string Model { get; set; }
 public int Year { get; set; }

 public void Start()
 {
   Console.WriteLine("Motorcycle is starting.");
 }

 public void Stop()
 {
   Console.WriteLine("Motorcycle is stopping.");
 }
}

Let’s say that we want to create a list of vehicles, then loop through it and perform an inspection on each vehicle:

// Create a list of objects
List<Object> vehicles = new List<Object>
    {
      new Car { Brand = "Toyota", Model = "Camry", Year = 2020, NumberOfDoors = 4 },
      new Motorcycle { Brand = "Harley-Davidson", Model = "Sportster", Year = 2021 }
    };


// Perform a general inspection on each vehicle
foreach (var vehicle in vehicles)
{
 if (vehicle is Car)
 {
   Car car = (Car)vehicle; // cast vehicle to a Car
   Console.WriteLine($"Inspecting {car.Brand} {car.Model} ({car.GetType().Name})");
   car.Start();
   car.Stop();
 }
 else if (vehicle is Motorcycle)
 {
   Motorcycle motorcycle = (Motorcycle)vehicle; // cast vehicle to a Motorcycle
   Console.WriteLine($"Inspecting {motorcycle.Brand} {motorcycle.Model} ({motorcycle.GetType().Name})");
   motorcycle.Start();
   motorcycle.Stop();
 }
 else
 {
   throw new Exception("Object is not a valid vehicle");
 }
}

Notice the ugly code inside the foreach loop! Because vehicles is a list of any type of object (Object), we have to figure out what type of object we are dealing with in each loop, then cast it to the appropriate object type before we can access any information on the object.

This code will continue to get uglier as we add more vehicle types. For example, if we extended our codebase to include a new Plane class, then we’d need to modify existing code – we’d have to add another conditional check in the foreach loop for planes, violating the Open/Closed SOLID Principle.

(By the way, if you're unfamiliar with the SOLID Principles and want to take your OOP skills to the next level, learning everything that you need to write elegant, maintainable, flexible and testable software -- then check out my book on Amazon Mastering Design Patterns in C#: A Beginner-Friendly Guide, Including OOP and SOLID Principles. It's also available on Gumroad.)

Now, back to our example...

Introducing: Polymorphism

Cars and motorcycles are both vehicles. They both share some common properties and methods. So, let’s create a parent class that contains these shared properties and methods:

public class Vehicle
{
 public string Brand { get; set; }
 public string Model { get; set; }
 public int Year { get; set; }

 public virtual void Start()
 {
   Console.WriteLine("Vehicle is starting.");
 }

 public virtual void Stop()
 {
   Console.WriteLine("Vehicle is stopping.");
 }
}

Car and Motorcycle can now inherit from Vehicle:

public class Car : Vehicle
{
 public int NumberOfDoors { get; set; }

 public override void Start()
 {
   Console.WriteLine("Car is starting.");
 }

 public override void Stop()
 {
   Console.WriteLine("Car is stopping.");
 }
}

public class Motorcycle : Vehicle
{
 public override void Start()
 {
   Console.WriteLine("Motorcycle is starting.");
 }

 public override void Stop()
 {
   Console.WriteLine("Motorcycle is stopping.");
 }
}

Car and Motorcycle both extend Vehicle, as they are vehicles. But what’s the point in Car and Motorcycle both extending Vehicle if they are going to implement their own versions of the Start() and Stop() methods? Look at the code below:

// Program.cs

// Create a list of vehicles
List<Vehicle> vehicles = new List<Vehicle>
     {
       new Car { Brand = "Toyota", Model = "Camry", Year = 2020, NumberOfDoors = 4 },
       new Motorcycle { Brand = "Harley-Davidson", Model = "Sportster", Year = 2021 }
     };

// Perform a general inspection on each vehicle
foreach (var vehicle in vehicles)
{
 Console.WriteLine($"Inspecting {vehicle.Brand} {vehicle.Model} ({vehicle.GetType().Name})");
 vehicle.Start();
 // Additional inspection steps...
 vehicle.Stop();
 Console.WriteLine();
}

In this example:

We have a list, vehicles, containing instances of both Car and Motorcycle.
We iterate through each vehicle in the list and perform a general inspection on each one.
The inspection process involves starting the vehicle, checking its brand and model, and stopping it afterwards.
Despite the vehicles being of different types, polymorphism allows us to treat them all as instances of the base Vehicle class. The specific implementations of the Start() and Stop() methods for each vehicle type are invoked dynamically at runtime, based on the actual type of each vehicle.

Because the list can only contain objects that extend the Vehicle class, we know that every object will share some common fields and methods. This means that we can safely call them, without having to worry about whether each specific vehicle has these fields or methods.

This demonstrates how polymorphism enables code to be written in a more generic and flexible manner, allowing for easy extension and maintenance as new types of vehicles are added to the system.

For example, if we wanted to add another vehicle, we don’t have to modify the code used to inspect vehicles (“the client code”); we can just extend our code base, without modifying existing code:

public class Plane : Vehicle
{
 public int NumberOfDoors { get; set; }

 public override void Start()
 {
   Console.WriteLine("Plane is starting.");
 }

 public override void Stop()
 {
   Console.WriteLine("Plane is stopping.");
 }
}

// Program.cs

// Create a list of vehicles
List<Vehicle> vehicles = new List<Vehicle>
      {
          new Car { Brand = "Toyota", Model = "Camry", Year = 2020, NumberOfDoors = 4 },
          new Motorcycle { Brand = "Harley-Davidson", Model = "Sportster", Year = 2021 },
          /////////// ADD A PLANE TO THE LIST:
          new Plane { Brand = "Boeing", Model = "747", Year = 2015 }
          ////////////////////////////////////
      };

The code to perform the vehicle inspections doesn’t have to change to account for a plane. Everything still works, without having to modify our inspection logic.

Conclusion

Polymorphism is the term that explains different types of objects can be treated the same way, allowing us to flexibly pass around different types of objects in our code. Polymorphism makes software flexible, extensible, testable (e.g. we can pass a dummy database class to an object so that we don't have to test with a real database) and readable.

And if you'd like to learn all of the tools that you need to become a great object-oriented programmer, including:

All 23 design patterns (“The Gang of Four Design Patterns”) with real world examples.
OOP principles: encapsulation, abstraction, inheritance, polymorphism, coupling, composition, composition vs inheritance, fragile base class problem.
The five SOLID principles: crucial for any developer that wants to work on OOP software and essential to know before diving into the design patterns.
Unified Modelling Language (UML): the standard way to model classes and the relationships between them.

Then check out my book on Amazon Mastering Design Patterns in C#: A Beginner-Friendly Guide, Including OOP and SOLID Principles. It's also available on Gumroad.

Hope this article was helpful!

Thanks,
Danny

How to Test HarperDB Custom Functions with Node Tap

Danny Adams — Tue, 29 Aug 2023 13:02:46 +0000

Intro

When making changes to an app, automated tests help to ensure that your new code hasn't broken any previously developed features. Tests help to save you time, as you won't have to always manually test everything out when adding new features or making changes to a codebase. This is especially important as your application grows larger.

In this article, I'm going to show you how to write some basic feature tests for a HarperDB custom functions (applications) project to ensure that the api routes are working as planned. We will also write a unit test to ensure that one of our individual functions is working correctly.

In case you're not familiar, HarperDB is a database, streaming broker, and application development platform. It has a flexible, component-based architecture, simple HTTP/S interface, and a high-performance single-model data store that accommodates any data structure.

Github repo

The complete code repository for this project: https://github.com/DoableDanny/HarperDB-Testing-Tutorial

(Don't forget to give it a star ⭐)

Installing HarperDB locally

I'm on Mac, so to install HarperDB I opened a terminal and entered:

npm install -g harperdb

This installed HarperDB instance on my Mac is located at the destination: /Users/danadams/hdb Server with:

Listening port: 9925
Username for HDB_ADMIN: HDB_ADMIN
Password: whatever_you_set_this_to_during_installation

We can now start HarperDB with the command:

harperdb

Now we can use HarperDB locally!

Creating a HarperDB custom functions project

Now we have HarperDB installed locally, we can create a new HarperDB custom functions project. Custom functions (also known as applications) are simply Fastify API routes that can very quickly access data from the HarperDB database. To create a new custom functions project, open up a new terminal and cd ("change directory") into the custom functions directory of your local HarperDB instance:

cd hdb
cd custom_functions

You can check that you're in the correct directory by entering pwd ("print working directory"). Currently, I'm here: /Users/danadams/hdb/custom_functions.

Now that we're in the right place, we need to actually create a new custom functions project. We could do all of this from scratch, or we can just clone HarperDB's custom functions starter template to get us going quickly: https://github.com/HarperDB/harperdb-custom-functions-template. So, let's clone this into our custom_functions folder:

git clone https://github.com/HarperDB/harperdb-custom-functions-template

If you now enter ls ("list files and directories"), you should see harperdb-custom-functions-template listed.

Let's rename this folder to testing-project-tutorial:

mv harperdb-custom-functions-template testing-project-tutorial

Alright, let's open up this project in VS Code:

code testing-project-tutorial

Setting up HarperDB Studio

Let's now set up HarperDB studio so we can easily view our database with a nice UI in the browser.

First, create an account with HarperDB.

Then we need to connect up our locally installed HarperDB instance by registering a user-installed instance:

Select "Register User-Installed Instance":

Then connect up the local HarperDB instance that you installed in the previous step:

Creating our Schema and Table in HarperDB Studio

In HarperDB studio, click on "Browse" in the nav bar, then create a new schema called testing_project_tutorial. Inside this schema, create a new table called posts with hash_attr of id (hash_attr are like HarperDB's version of primary keys).

Defining some useful constants for our project

Create the file config/constants.js in the project root. Add the following project constants:

export const HDB_URL = 'http://localhost:9926/testing-project-tutorial';

export const SCHEMA = 'testing_project_tutorial';

Creating our HarperDB Custom Function API routes

First, let's create a route where we can get a list of blog posts. In your HarperDB studio, go to the functions tab and go to your testing-project-tutorial project. Under the routes folder, create a file called posts:

Create a route that accepts a GET request, then fetches all the posts from the posts table:

// routes/posts.js

import { SCHEMA } from '../config/constants.js';

const POSTS_TABLE = 'posts';

export default async (server, { hdbCore, logger }) => {
    // GET: get list of posts
    server.route({
        url: '/posts',
        method: 'GET',
        handler: (request, reply) => {
            request.body = {
                operation: 'sql',
                sql: `SELECT * FROM ${SCHEMA}.${POSTS_TABLE}`,
            };
            return hdbCore.requestWithoutAuthentication(request);
        },
    });
};

Click the save button in HarperDB studio, then navigate to this new route:

http://localhost:9926/testing-project-tutorial/posts

We get back an empty array, as we currently have no posts:

So, let's create a route that accepts a POST request and some data related to a post. The posted data should be a JSON object with the fields username, title, and content.

// routes/posts.js

// POST: create a new post
  server.route({
    url: '/posts',
    method: 'POST',
    handler: (request, reply) => {
      const data = request.body;
      let validatedData;
      try {
        // validate the posted data using our custom validateCreateProductInput function.
        validatedData = validateCreatePostInput(data);
      } catch (error) {
        // posted data is invalid, so return the error message
        return reply.status(400).send({ message: error.message });
      }
      // data is all good, so insert it into the posts table
      request.body = {
        operation: 'insert',
        schema: SCHEMA,
        table: POSTS_TABLE,
        records: [
          {
            ...validatedData,
          },
        ],
      };


      return hdbCore.requestWithoutAuthentication(request);
    },
  });

But the above route won't work just yet, as we need to create the validateCreateProductInput() function. Above, we're wrapping this in a try/catch block as we want this validation function to throw errors if the posted data is not valid.

From HarperDB studio, create a new helper file called posts:

Then create the validation function:

// helpers/posts.js

export function validateCreateProductInput(input) {
    const { username, title, content } = input;
    if (!username || !title || !content) {
        throw Error('username, title and content are required');
    }
    if (username.length > 12) {
        throw Error('username must be less than 12 characters');
    }
    return {
        username: username.toLowerCase(),
        title,
        content,
    };
}

And, of course, let's import this function at the top of our routs/posts file:

// routes/posts.js

import { validateCreateProductInput } from '../helpers/posts.js';

Let's now use Postman to test out our routes. I've exported a Postman JSON collection file that you can simply import into Postman to quickly get you going: https://github.com/DoableDanny/HarperDB-Testing-Tutorial/blob/main/HarperDB%20Testing%20Tutorial.postman_collection.json

For the create post route, we can send our post data in a raw JSON body:

And the post was created successfully:

Let's check the posts table:

Perfect!

Now to check that our get posts route returns this new post:

Awesome!

Let's now write some tests to ensure our routes are working as planned!

Setting up our project for testing

For this part of the project, I'm going to begin working in VS Code, rather than coding directly into HarperDB studio, to make it easy to install some npm packages. First, let's install the testing framework node tap as a dev dependency:

npm i tap -D

Let's also create a script in package.json to run our tests:

// package.json

{
  "name": "testing-project-tutorial",
  "version": "2.0.0",
  "description": "An example HarperDB Custom Function",
  "type": "module",
  "author": "Danny Adams",
  "scripts": {
    "test": "tap"
  },
  "devDependencies": {
    "tap": "^16.3.8"
  }
}

All of our tests can now be ran with:

npm run test

Testing creating a post

Unit tests

First, we will write unit tests to check that our validateCreatePostInput() function is working correctly with different inputs.

When writing tests, it's important to not forget about testing the sad paths: what if some form input is invalid, or a url param is invalid. Do we get the correct status code, error message, redirect, view, etc.

It's often a good approach to start writing the sad tests first, as it gets you brainstorming about what can go wrong and how it should be handled. So, let's start by writing a unit test to check that our validateCreatePostInput() function throws an error with the correct message if we pass it invalid data.

In the project root, create the file tests/posts/createPost.test.js, and add the following code:

// tests/posts/createPost.test.js

import { test } from 'tap';
import { validateCreatePostInput } from '../../helpers/posts.js';


test('POST `/posts`', async (t) => {
  // Unit test -- sad path
  test('Test if error is thrown from validate post data function call', async (t) => {
    t.throws(
      () => {
        const input = {
          username: 'Danny Adams',
          title: 'This is the Title',
          // content: "This is the contents of the post. Blah blah etc.", // no content provided should throw error
        };
        validateCreatePostInput(input);
      },
      {
        message: 'username, title and content are required', // error message we expect
        // name: "ExpectedErrorName", // Optional: check error name if needed
      }
    );
  });
});

The test above is a "unit test", as we are only testing one piece of code – our validation function. Above, we're using node tap to test that the function throws an error with the correct message if we don't pass a content field.

After running the test with npm run test:

Our test passes!

How does Node Tap know which of our files to run as tests? It simply looks for files that end in .test.js.

Challenge: see if you can write a unit test to check what happens if we post a username that is too long.

Next, let's write the "happy path", where the input data is correct:

  // Unit test -- happy path
  test('Check post data is validated correctly', async (t) => {
    const input = {
      username: 'Danny Adams',
      title: 'This is the Title',
      content: 'This is the contents of the post. Blah blah etc.',
      naughtyKey: "This key shouldn't be here",
    };
    const validData = validateCreatePostInput(input);
    t.equal(validData.title, input.title);
    t.equal(validData.content, input.content);
    t.equal(validData.username, input.username.toLowerCase()); // username should be lowercased
    t.equal(validData.hasOwnProperty('naughtyKey'), false); // naughtyKey should not be returned from validateCreateProductInput()
  });

Above, we are simply checking that our validation function returns the validated data that we expect. Now that we have these tests, if we needed to modify our validation function in the future, these tests would tell us if the function is no longer behaving as it should.

Feature tests

Most of your tests should be feature tests, as they help to ensure that the application as a whole is working as expected. Let's test that our api route to create a new post is working correctly. We'll first write the unhappy paths to get us thinking about what could go wrong, then we'll write the happy path.

Unsuccessful post creation

First, create a helper function at the bottom of the createPost.test.js file that we can reuse to send a POST request to our api:

// tests/createPost.test.js

async function postThePost(input) {
  const response = await fetch(HDB_URL + "/posts", {
    method: "POST",
    headers: {
      "Content-Type": "application/json",
    },
    body: JSON.stringify(input),
  });
  const json = await response.json();
  return { response, json };
}

Now let's create two feature tests to check that our api returns the expected status codes and error message when we send invalid data:

// tests/createPost.test.js

test("POST `/posts`", async (t) => {

// …

  // Feature test: sad path
  test('Trying to create a post with username that is too long', async (t) => {
    const username = 'This username is just way to long...';
    const title = 'This is the Title';
    const content = 'This is the contents of the post. Blah blah etc.';


    const { response, json } = await postThePost({ username, title, content });


    t.equal(response.status, 400);
    t.equal(json.message, 'username must be less than 12 characters');
  });


  // Feature test: sad path
  test('Trying to create a post with no title', async (t) => {
    const username = 'Test User';
    const title = '';
    const content = 'This is the contents of the post. Blah blah etc.';


    const { response, json } = await postThePost({ username, title, content });


    t.equal(response.status, 400);
    t.equal(json.message, 'username, title and content are required');
  });

// …

Above, we're asserting that we get the correct error status codes (400 for "bad request") and that the error messages returned are as expected.

Create a post successfully

Now let's test what creating a post successfully should look like – the happy path!

First, at the bottom of the test file, create a deletePosts() helper function. We will use this to delete the test post that we create.

// tests/posts/createPost.js


async function deletePosts(postIdsArray) {
  const { response: deleteResponse, json: deleteJson } = await harperDbClient({
    operation: 'delete',
    schema: 'testing_project',
    table: 'posts',
    hash_values: postIdsArray,
  });
  console.log('Delete response:');
  console.log(deleteResponse, deleteJson);
  return { deleteResponse, deleteJson };
}

Let's also create a harperDbClient() function that we can reuse to interact with our HarperDB data:

// helpers/harperdb.js

export async function harperDbClient(body) {
  var myHeaders = new Headers();
  myHeaders.append('Content-Type', 'application/json');
  myHeaders.append('Authorization', process.env.HARPERDB_SECRET);

  var raw = JSON.stringify(body);

  var requestOptions = {
    method: 'POST',
    headers: myHeaders,
    body: raw,
    redirect: 'follow',
  };

  try {
    const response = await fetch('http://localhost:9925', requestOptions);
    const json = await response.json();
    return { response, json };
  } catch (error) {
    console.log(error);
  }
}

We also need to install the dotenv package to load in our environment variables:

npm i dotenv

Add your HarperDB secret into a .env file at your project root (your .env file should look like this), then load the variables at the top of the test file:

// tests/posts/createPost.js

import 'dotenv/config';

Here's how our successful post creation test will work:

Create a post by hitting our POST api endpoint with some valid data.
From the api's json response, get the "inserted_hashes". This is an array of the post ids that were just created. HarperDB automatically creates these ids when inserting a record.
Pass a callback to node tap's teardown() function to delete these test posts once the test is complete. The teardown function will run automatically when node tap detects that this test is complete.
Fetch the new post from the posts table so we can check that it was inserted correctly by comparing it to the original input data.
Run our assertions (e.g. t.equal()) to check status codes, messages, and data are all as expected.

Putting this into code:

tests/posts/createPost.js


import { HDB_URL, SCHEMA } from '../../config/constants.js';
import { harperDbClient } from '../../helpers/harperdb.js';


// …  


// Feature test: happy path
  test('Create a post successfully', async (t) => {
    // create some post data
    const username = 'Test User';
    const title = 'This is the Title';
    const content = 'This is the contents of the post. Blah blah etc.';


    // Hit our custom function api endpoint to create new post
    const { response, json } = await postThePost({ username, title, content });
    console.log('JSON R');
    console.log(json.inserted_hashes);
    const postIds = json.inserted_hashes;


    // Teardown => run callback once test is complete
    t.teardown(async () => {
      // Clean up: delete the test post from db
      const { deleteResponse } = await deletePosts(postIds);
      console.log('Deleted posts with status ', deleteResponse.status);
    });


    // Fetch this new post from the db
    const { response: dbResponse, json: dbJson } = await harperDbClient({
      operation: 'search_by_hash',
      schema: SCHEMA,
      table: 'posts',
      hash_values: postIds,
      get_attributes: ['id', 'username', 'title', 'content'],
    });
    const dbNewPost = dbJson[0];


    console.log('DB RESULT:');
    console.log(dbResponse, dbJson, dbNewPost);


    // Check status and response is correct from api
    t.equal(response.status, 200);
    t.equal(json.message, 'inserted 1 of 1 records');


    // Check the post was inserted correctly into the db
    t.equal(dbResponse.status, 200);
    t.equal(dbNewPost.username, username.toLowerCase()); // username should be lowercased
    t.equal(dbNewPost.title, title);
    t.equal(dbNewPost.content, content);
  });
});

Testing getting posts

To test our api endpoint to get all posts, we'll do the following:

Insert 3 test posts into the posts table
Use node tap's teardown function to delete these new posts once the test is complete
Fetch all posts by making a GET request to our /posts route
Check that one of the posts we got back is one of the new posts that we created and that it contains the correct data

// tests/posts/createPost.js

import { HDB_URL, SCHEMA } from '../../config/constants.js';
import { harperDbClient } from '../../helpers/harperdb.js';

// …  

// Feature test: happy path
  test('Create a post successfully', async (t) => {
    // create some post data
    const username = 'Test User';
    const title = 'This is the Title';
    const content = 'This is the contents of the post. Blah blah etc.';

    // Hit our custom function api endpoint to create new post
    const { response, json } = await postThePost({ username, title, content });
    console.log('JSON R');
    console.log(json.inserted_hashes);
    const postIds = json.inserted_hashes;

    // Teardown => run callback once test is complete
    t.teardown(async () => {
      // Clean up: delete the test post from db
      const { deleteResponse } = await deletePosts(postIds);
      console.log('Deleted posts with status ', deleteResponse.status);
    });

    // Fetch this new post from the db
    const { response: dbResponse, json: dbJson } = await harperDbClient({
      operation: 'search_by_hash',
      schema: SCHEMA,
      table: 'posts',
      hash_values: postIds,
      get_attributes: ['id', 'username', 'title', 'content'],
    });
    const dbNewPost = dbJson[0];

    console.log('DB RESULT:');
    console.log(dbResponse, dbJson, dbNewPost);

    // Check status and response is correct from api
    t.equal(response.status, 200);
    t.equal(json.message, 'inserted 1 of 1 records');

    // Check the post was inserted correctly into the db
    t.equal(dbResponse.status, 200);
    t.equal(dbNewPost.username, username.toLowerCase()); // username should be lowercased
    t.equal(dbNewPost.title, title);
    t.equal(dbNewPost.content, content);
  });
});

Things we could improve on in this project

There we have it; you now know how to run some unit and feature tests in a custom functions project. However, if this was a serious project, we'd definitely want to improve on a few things:

Currently, our tests are working with our main database. This is generally considered bad practice as it can result in our tests messing up our development data and get us in a mess. It would probably be better to work with a test schema with the same tables as the real schema.
It's usually a good idea to clear out all test data in each table after running each test, so that tests don't interfere with each other and cause unexpected issues. We would then have complete control over what is in each table at the beginning of each test, and so can test exactly what we expect to be in each table.
It could also be a good idea to create a separate environment for testing, e.g. .env.testing, then when running our tests we could specify the environment we want to use in the npm script. E.g.

// package.json

"scripts": {

"test": "NODE_ENV=test dotenv -e .env.test tap"

},

Thanks for reading!

If you enjoyed this article, it'd be awesome if you could give me a sub on YouTube. You could also follow me on Twitter.

Cheers!

How to Speed Up your Applications by Caching at the Edge with HarperDB

Danny Adams — Wed, 22 Mar 2023 17:39:15 +0000

Caching is a commonly used technique to speed up websites and applications. “Caching” simply means to save something (e.g. data or a web page) so that it can be accessed quickly in the future.

For example, WordPress websites heavily use caching to reduce the amount of server computing that has to be done. This reduces costs and allows web pages and blog posts to be served up quickly.

If a blog post wasn’t cached, then every time a page is requested, the post’s data (the title, excerpt, feature image, and content) would have to be fetched from the database and rendered into html. But if the page is cached (i.e. the resulting html is saved), then the page is just sitting on the server ready to go, and can be served up straight away without any database calls – speeding up the site.

In this article, we’re going to discuss a modern technique called "caching at the edge". We'll then create a simple caching project with HarperDB to cache the result of an API call. We'll then compare the speed of an un-cached api route vs a cached api route.

You'll see that caching the result of an api request will speed up subsequent requests, and also make it less likely that our app gets rate limited.

What is HarperDB and why is it a good option for caching?

HarperDB is a distributed application & database platform that allows you to lower latency and improve the performance of any dataset and any application.

“Distributed” means that the application and database are spread out around the globe. Traditionally, a web app and database sit on one server, but this causes a lot of latency (a fancy word for delay) if the user is located a long way from the server -- e.g., if the app is in New York, but the user is in Delhi.

If the app is distributed, then the app is sitting on multiple servers around the world, e.g. the user in Delhi could get the app served from a computer in Bangladesh, instead of New York.

What is Edge computing?

Traditionally, when you deploy a web app, you rent out a computer that lives in a physical data centre somewhere around the world – like “us-east-2” or “tt-west-4”. All the requests from around the world go to that same server. But the problem is that your users are scattered around the globe. The speed of light is fast, but not instant, so being physically closer to the server will give you a faster response from the server.

Web developers have been mitigating this problem for a long time by using CDNs (content delivery networks) to distribute, duplicate, or cache static files – such as HTML, CSS, or JavaScript on servers all around the world. This works great for static files, but doesn’t work for a dynamic server that needs to execute some server-side code on every request.

Wikipedia’s definition of edge computing:

“Edge computing is a distributed computing paradigm that brings computation and data storage closer to the sources of data. This is expected to improve response times and save bandwidth.”

So, edge computing is like a CDN for a full-blown server.

Vercel (a company that is famous for providing great Next.js hosting) provide edge functions that distribute your Next.js api routes around the globe, putting them closer to the user – wherever they are situated.

This sounds great on paper, but what if the database is sitting in a single location – say New York. If a user in Delhi makes a request to a distributed api route located in Bangladesh, but then that api route needs some data from the database located in New York, then the round trip becomes:

Dellhi -> Bangladesh -> New York -> Bangladesh -> New York.

That request takes even longer than if the app and data wasn’t distributed and just sat in New York, with a shorter round trip of:

Delhi -> New York -> Delhi.

So, if we are distributing our application, then (depending on your specific use case) it’s often going to be a good idea to distribute the data along with the app.

But distributed systems can be very complex to create and maintain. This is where HarperDB comes in. HarperDB lowers the latency of any dataset by distributing your api routes and data around the globe, putting your application (e.g. api routes) right next to your database, and your application and data closer to the end user.

This makes HarperDB a great candidate for edge caching: we can cache (save to our HarperDB database) data and distribute this cache all over the globe.

With HarperDB, the API server is integrated into the database itself (a feature known as “custom functions”), meaning that there is one less hop from the api to the database, further reducing latency and serving our users nice and fast.

For more on edge caching, check out Edge Caching Explained & Why You Should Be Using It.

Let’s now build a simple project to cache the result of an api request…

HarperDB caching project

What we’re going to build

We’re going to compare the speed difference of an un-cached api route vs a route that caches the result of an api call.

In the un-cached route, we will simply fetch a post by id from the JSONPlaceholder API, https://jsonplaceholder.typicode.com/posts/${id}, on every request, and return it to the user.

In the cached route, we will cache the result of each request to https://jsonplaceholder.typicode.com/posts/${id}.

The logic for the cached route is simple:

Get the post id from the url, and fetch the post from the HarperDB database.
If a post is found (i.e. cached), then return it. (We are done.)
If no post is found in the database with that id, then fetch the post from the API.
Save (cache) the post in the database.
Return the post.
Let’s get started.

Installing HarperDB locally

Install HarperDB locally for Mac, Windows, or Linux.

I’m on Mac, so to install HarperDB I opened a terminal and entered:

$ npm install -g harperdb

This installed HarperDB instance on my Mac is located at the destination: /Users/danadams/hdb Server with:

Listening port: 9925
Username for HDB_ADMIN: HDB_ADMIN
Password: whatever_you_set_this_to_during_installation

We can now start HarperDB with the command:
$ harperdb

Now we can use HarperDB locally!

Setting up HarperDB studio

First, create an account with HarperDB.

Then we need to connect up our locally installed HarperDB instance by registering a user-installed instance:

Select “Register User-Installed Instance”:

Then connect up the local HarperDB instance that you installed in the previous step:

Creating our schema

Let’s create a schema called “caching_project”. A schema is just a fancy way of saying “group of tables” in HarperDB.

Then, in the caching_project schema, create a table called single_post with a hash_attribute of id. A hash_attribute is kind of like a unique primary key for a row in a table.

Creating a custom function project

In HarperDB, custom functions are custom routes that we can define to do whatever we want – usually to interact with our HarperDB database in some way. Essentially, custom functions allow us to build our api right next to where our data is stored, reducing latency.

Custom Functions are powered by Fastify (a light-weight Node.js framework that claims to be faster than Express.js), so they’re extremely flexible.

To spin up a new custom functions project, go to the functions tab, click the ‘+’ icon next to ‘projects’ and create a project called caching-project:

Next, create a file in the ‘routes’ folder called ‘post’. This is where we will be writing our route handlers to fetch single blog posts.

HarperDB provides some example routes, but let’s clear everything out and create a simple route to test that we’re set up correctly:

'use strict';

module.exports = async (server, { hdbCore, logger }) => {
  // Test route
  server.route({
    url: '/test',
    method: 'GET',
    handler: () => {
      return 'It works!' // This should be printed out in browser
    }
  })
};

Locate the url to your custom functions at the bottom left corner of the ‘custom functions’ tab:

Visiting the caching-project/test route:

Perfection!

Note that we can also write our custom functions in your favourite text-editor by opening the project locally. On Mac, the custom functions are located at /Users/your_username/hdb/custom_functions, so to open with VS Code on Mac:

Open up a terminal
$ cd hdb
$ cd custom_functions
$ code .

Now, you can edit your code in your text editor, then go to the HarperDB studio functions tab, click reload to see your local changes, then click the green save button to update.

But for this simple project, I’m just gonna wing it and write the code directly into HarperDB studio.

Creating an un-cached route

Let’s create a route that fetches a post by its id from the JSONPlaceholder API, then returns it to the user:

  // Fetch a post by id from JSONPlaceholder api
  server.route({
    url: '/post/:id',
    method: 'GET',
    handler: () => {
      const postId = request.params.id;
      const response = await fetch(
        `https://jsonplaceholder.typicode.com/posts/${postId}`
      );
      const post = await response.json();
      return post;
    }
  })

Now let’s open up Postman (a popular software for quickly testing api routes) to hit this endpoint, and see how long it takes to receive the data:

After clicking “Send” a few times, the request takes anywhere from 35ms to 200ms, with most requests taking around 45ms. Let’s see if we can improve that by caching the results of the API calls…

Creating a cached route

Let's remind ourselves of the logic for the cached route:
Get the post id from the url, and fetch the post from the HarperDB database.

If a post is found, then return it. (We are done.)
If no post is found in the database with that id, then fetch the post from the API.
Save the post in the database.
Return the post.

Putting this logic into code:

server.route({
    url: "/cached-post/:id",
    method: "GET",
    preParsing: (request, response, payload, done) => {
      request.body = {
        ...request.body,
        operation: "sql",
        sql: `SELECT * FROM caching_project.single_post WHERE id = '${request.params.id}'`,
      };
      done();
    },
    handler: async (request) => {
      const cachedPost = await hdbCore.requestWithoutAuthentication(request);
      if (cachedPost.length === 1) {
        // Post found in db, so return it.
        return cachedPost[0];
      }


      // Post not cached/found in db, so fetch post from api
      const postId = request.params.id;
      const response = await fetch(
        `https://jsonplaceholder.typicode.com/posts/${postId}`
      );
      const newPost = await response.json();


      // Add the HarperDB operation to insert the post into the db
      request.body = {
        operation: "insert",
        schema: "caching_project",
        table: "single_post",
        records: [newPost],
      };
      // Cache (save) the result in db
      hdbCore.requestWithoutAuthentication(request);
      // Return the post
      return newPost;
    },
});

Above, the preParsing callback adds the HaperDB operation that we want to perform to the request body. This operation will fetch the post by id from the database.

We then use hdbCore.requestWithoutAuthentication(request) to perform the database operation without authorisation (these routes should be publicly available, so no authentication is needed). If the post is found, then we return it; otherwise, we fetch it from the api, save it to our HarperDB database then return it.

Now when we hit our endpoint for the first time, we have to wait 118ms to get the response:

But then when we hit the same route again (with the same post id), it takes just 10ms:

Why is the first request slower? Because when a user requests a post for the first time, that post isn’t cached (stored in our db), so the post has to be fetched from the api, cached into our db, then returned to the user.

But any subsequent requests for the same post will be faster, as the post is now cached in the database and can be fetched and returned straight away.

So, by caching with HarperDB, we have reduced the latency of the request by 4 to 5 times (from ~45ms uncached to ~10ms cached).

You can check what data is stored from HarperDB studio:

How could we improve our caching strategy?

Currently, our cache has no expiry date, meaning that if a post got updated at the JSONPlaceholder API, then we’d never see the update as our cache is permanent. To allow for post updates, we could add an expiry date column to each of our rows of cache to expire the cache after a few hours. Then, if the cache has expired, we can re-fetch the post from JSONPlaceholder and update the cache in the database, ensuring our cache is never more than a few hours out of date.

Summary

HarperDB is a great option for caching data as it brings the application and data closer to the user (also known as edge caching), reducing latency and speeding up your application.

If you enjoyed this article, give me a sub on YouTube or follow me on Twitter.

Thanks for reading!

JavaScript Array Method Cheat Sheet (17 must-know methods) 📄

Danny Adams — Tue, 15 Mar 2022 17:57:14 +0000

Having useful array methods at the top of your head will improve your problem solving ability.

So I decided to make a JavaScript array methods cheat sheet so I can quickly revise array methods and always keep them fresh in my mind.

This cheat sheet includes 17 commonly used array methods:

toString()
join()
concat()
splice()
slice()
indexOf()
lastIndexOf()
forEach()
map()
filter()
reduce()
some()
every()
flat()
find()
findIndex()
sort()

Video

I also turned this cheat sheet into a video. If you find this video or cheat sheet useful, you can say thanks by subscribing to my channel 🙏.

Array methods are shared

In JavaScript, all arrays are constructed from the global Array class. All array methods are stored in the Array.prototype object.

This means that array methods are shared between array instances via prototypal inheritance.

Array methods in JavaScript

Array.prototype.toString

Converts an array into a string of comma-separated array values:

let names = ["Zoe", "Adam", "Dan"]

let strNames = names.toString() // Zoe,Adam,Dan

Array.prototype.join

Similar to toString, but you can specify the separator:

let names = ["Zoe", "Adam", "Dan"]

let strNames = names.join(" and ") // Zoe and Adam and Dan

Array.prototype.concat

Create a new array by concatenating existing arrays:

let nums = [1, 2, 3]
let nums2 = [4, 5, 6]
let nums3 = [7, 8, 9]

let concatArr = nums.concat(nums2, nums3)
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

Array.prototype.splice

The splice() method can be used to add new items to an array:

let arr = ["Danny", "Joe"]

arr.splice(1, 0, "Alice", "Amy")

console.log(arr) // ['Danny', 'Alice', 'Amy', 'Joe']

The first parameter (1) defines the index from where the new elements should be added (spliced in).

The second parameter (0) defines how many elements should be removed.

The rest of the parameters ('Alice', 'Amy') define the new elements to be added.

splice() returns an array with the deleted items:

let arr = ["Danny", "Joe"]

let spliced = arr.splice(1, 1, "Alice", "Amy") // ['Joe']

console.log(arr) // ['Danny', 'Alice', 'Amy']

We can also delete items without adding any new ones:

let arr = ["Danny", "Joe", "Amy"]

let spliced = arr.splice(1, 1) // ['Joe']

console.log(arr) // ['Danny', 'Amy']

Since splice() mutates the original array, it is often best to make a copy of it before splicing.

Array.prototype.slice

slice() slices out a piece of an array, and returns it in a new array:

let arr = ["Danny", "Joe", "Amy"]

let slice = arr.slice(1) // ['Joe', 'Amy']

Above, we are slicing from the element at index 1. slice() does not mutate the original array.

We can provide a start and end index to splice from (up to but not including end index):

let arr = ["Danny", "Joe", "Amy"]

let slice = arr.slice(0, 2) // ['Danny', 'Joe']

Array.prototype.indexOf

Find the first index that contains a certain value (searches from left to right):

let arr = ["Danny", "Joe", "Amy", "Joe"]

let index = arr.indexOf("Joe") // 1

Array.prototype.lastIndexOf

Find the last index that contains a certain value (searches from right to left):

let arr = ["Danny", "Joe", "Amy", "Joe"]

let index = arr.lastIndexOf("Joe") // 3

Higher-order array methods in JavaScript

Array methods what is a higher-order function?

A higher-order function is a function that accepts functions as arguments, and/or returns a function. So, higher-order functions are functions that operate on other functions.

In JavaScript, these methods are shared between array instances via prototypal inheritance from Array.prototype.

Array.prototype.forEach

The forEach method is basically just a shorter way of writing for(let i = 0; i < arr.length; i++) {...}.

It loops through the given array, and calls the given call-back function for each of the elements in the array.

The call-back passed to the forEach() function can accept any of the three arguments:

the item value
the item index
the array itself

Example:

let numbers = [1, 2, 3, 4]

numbers.forEach(n => console.log(n))
// 1
// 2
// 3
// 4

It's better to use map if you want to return a new array with return value of each call-back run.

Array.prototype.map

The map function takes in a call-back function as argument, and executes that function on each element of the array it is working on. It maps each of the return values of the call-back into a new array. It does not mutate the original array.

The call-back passed to the map() function can accept any of the three arguments:

the item value
the item index
the array itself

Examples:

let numbers = [1, 2, 3, 4]

// Double all numbers
let doubledNumbers = numbers.map(n => n * 2) // [2, 4, 6, 8]

// Only double numbers at odd indexes
let doubledOddIndexNumbers = numbers.map((n, i) => {
  if (i % 2 === 1) return n * 2
  else return n
}) // [1, 4, 3, 8]

Array.prototype.filter

The filter method is used to filter out array elements that fail a boolean test. Only elements that pass the test are allowed through into the new return array.

The call-back passed to the filter() function can accept any of the three arguments:

the item value
the item index
the array itself

A good use case for filter is a search bar:

let articles = [
  { title: "PHP classes", author: "Danny Adams" },
  { title: "Python arrays", author: "Amy Sanders" },
  { title: "Arrays in PHP", author: "Danny Adams" },
]

// Lets say the user searches for all articles with PHP in the title
let PHPArticles = articles.filter(a => a.title.includes("PHP"))
// [
//   { title: 'PHP classes', author: 'Danny Adams' },
//   { title: 'Arrays in PHP', author: 'Danny Adams' },
// ];

Another use case is filtering via size:

let cities = [
  { name: "Stokington", rivers: 3 },
  { name: "Phillydelfia", rivers: 6 },
  { name: "New Ports", rivers: 2 },
]

let moreThanTwoRivers = cities.filter(c => c.rivers > 2)
// [
//   { name: 'Stokington', rivers: 3 },
//   { name: 'Phillydelfia', rivers: 6 },
// ];

Array.prototype.reduce

The reduce method runs the call-back function on each array element, and reduces the array down into a single value.

The reduce function itself takes two arguments:

A call-back function
An initial value

reduce(callback, initialVal)

The call-back function passed into reduce can take up to four arguments:

total or "accumulator"
current item value
current item index
the array itself

Example:

let numbers = [1, 2, 3, 4]

let total = numbers.reduce((total, currentNum) => total + currentNum) // 10

In the above example, total is initially the first value in the array (1), and currentNum is the second (2).

If we wanted to start from a different value, we can pass in a second initialVal argument to reduce. Let's say we wanted to find the total, starting from 5:

let numbers = [1, 2, 3, 4]

let total = numbers.reduce((total, currentNum) => total + currentNum, 5) // 15

Above, total will now start out as 5, and currentNum will be the first element in the array (1).

Another good use case of reduce is to find the max or min value in an array:

let arr = [1, 2, 3]

let max = arr.reduce((a, b) => {
  return Math.max(a, b)
}, -Infinity)
// 3

Array.prototype.some

The some method checks if some array values pass a test. It returns either true or false.

The call-back takes 3 arguments:

The item value
The item index
The array itself

Example:

let numbers = [4, 6, 14, 16]

let isSomeGreaterThan6 = numbers.some(n => n > 6) // true
let isSomeLessThan4 = numbers.some(n => n < 4) // false

Array.prototype.every

every is similar to the some method, but checks if every value in the array passes a certain test, rather than just some.

Example:

let numbers = [4, 6, 14, 16]

let isEverythingGreaterThan6 = numbers.every(n => n > 6) // false
let isEverythingLessThan20 = numbers.some(n => n < 20) // true

Array.prototype.flat

The flat() method creates a new array with all sub-array elements concatenated into it recursively up to the specified depth.

Example:

let arr = [1, 2, 3, [1, 2], 4]

let flatArr = arr.flat() // [1, 2, 3, 1, 2, 4]

flat takes one optional depth parameter. depth specifies how deep a nested array structure should be flattened. It defaults to 1.

Example:

let arr = [1, 2, 3, [1, 2], [1, [1, 2]]]

let flatArr1 = arr.flat() // [1, 2, 3, 1, 2, 1, [1, 2]]
let flatArr2 = arr.flat(2) // [1, 2, 3, 1, 2, 1, 1, 2]

Array.prototype.find

The find method returns the first element in the array that passes a certain test.

The call-back passed to find takes 3 arguments:

The item value
The item index
The array itself

Example

let stock = [
  { item: "ketchup", quantity: 32 },
  { item: "mayo", quantity: 9 },
  { item: "hot sauce", quantity: 12 },
]

let mayo = stock.find(s => s.item === "mayo")
//  { item: 'mayo', quantity: 9 }

Array.prototype.findIndex

Same as find, but returns the index instead of the value:

let stock = [
  { item: "ketchup", quantity: 32 },
  { item: "mayo", quantity: 9 },
  { item: "hot sauce", quantity: 12 },
]

let mayoIndex = stock.findIndex(s => s.item === "mayo")
//  1

Array.prototype.sort

sort puts an array's elements in ascending order. It is an "in-place" sorting algorithm - meaning that it mutates the original array and returns it.

By default, sort works on strings:

let names = ["Zoe", "Adam", "Dan"]

names.sort()

console.log(names) // ['Adam', 'Dan', 'Zoe']

For numbers, we need to pass a comparison call-back function:

let numbers = [3, 1, 7, 2]

numbers.sort((a, b) => a - b)

console.log(numbers) // [1, 2, 3, 7]

Initially, a is 3 and b is 1. If a - b is negative, it knows that b is larger, and therefore should come after a. If positive, b should come before a.

Thanks for reading!

For more from me, you can:

Follow me on Twitter.
Subscribe to my YouTube channel where I plan to post more programming videos in the near future.

Cheers!

TypeScript Cheat Sheet 📄 (32 Code Examples + PDF & Poster)

Danny Adams — Tue, 01 Feb 2022 19:17:36 +0000

I recently wrote a comprehensive Beginners Guide to TypeScript for FreeCodeCamp, but I wanted distil everything from the article into a concise, easy-to-revise-from cheat sheet. So that's what I did.

This cheat sheet explains the following fundamental TypeScript concepts, with code examples:

Setting up a project
Compiling TypeScript
Strict mode
Primitive types
Union types
Dynamic types
Literal types
Objects
Arrays
Tuples
Functions
Type aliases
Interfaces
The DOM and type casting
Generics
Enums
Narrowing

TypeScript Cheat Sheet PDF

One page PDF to make it easy to copy and paste in commands.

Download the free TypeScript Cheat Sheet PDF here.

Cheat sheets are available in Dark Mode and Light Mode:

TypeScript Cheat Sheet Poster

Order a physical A3 poster for your office wall - so you can quickly look up commands, and keep them at the top of your head.

It comes in thick durable paper, and a matte, light-absorbing finish.

Order a TypeScript cheat sheet poster here

Here is everything included in the cheat sheet:

Setup

Install TS globally on your machine



$ npm i -g typescript

Check version



$ tsc -v

Create the tsconfig.json file



$ tsc --init

Set the root (to compile TS files from) and output (for the compiled JS files) directories in tsconfig.json



"rootDir": "./src",
"outDir": "./public",

Compiling

Compile a specified TS file into a JS file of the same name, into the same directory (i.e. index.ts to index.js)



$ tsc index.ts

Tell tsc to compile specified file whenever a change is saved by adding the watch flag (-w)



$ tsc index.ts -w

Compile specified file into specified output file



$ tsc index.ts --outfile out/script.js

If no file is specified, tsc will compile all TS files in the "rootDir" and output in the "outDir". Add -w to watch for changes.



$ tsc -w

Strict Mode

In tsconfig.json, it is recommended to set strict to true. One helpful feature of strict mode is No Implicit Any:



// Error: Parameter 'a' implicitly has an 'any' type
function logName(a) {
  console.log(a.name)
}

Primitive Types

There are 7 primitive types in JS:

string
number
bigInt
boolean
undefined
null
symbol

Explicit type annotation



let firstname: string = "Danny"

If we assign a value (as above), we don't need to state the type - TS will infer it ("implicit type annotation")



let firstname = "Danny"

Union Types

A variable that can be assigned more than one type



let age: number | string
age = 26
age = "26"

Dynamic Types

The any type basically reverts TS back to JS



let age: any = 100
age = true

Literal Types

We can refer to specific strings & numbers in type positions



let direction: "UP" | "DOWN"
direction = "UP"

Objects

Objects in TS must have all the correct properties & value types



let person: {
  name: string
  isProgrammer: boolean
}

person = {
  name: "Danny",
  isProgrammer: true,
}

person.age = 26 // Error - no age prop on person object

person.isProgrammer = "yes" // Error - should be boolean

Arrays

We can define what kind of data an array can contain



let ids: number[] = []
ids.push(1)
ids.push("2") // Error

Use a union type for arrays with multiple types



let options: (string | number)[]
options = [10, "UP"]

If a value is assigned, TS will infer the types in the array



let person = ["Delia", 48]
person[0] = true // Error - only strings or numbers allowed

Tuples

A tuple is a special type of array with fixed size & known data types at each index. They're stricter than regular arrays.



let options: [string, number]
options = ["UP", 10]

Functions

We can define the types of the arguments, and the return type. Below, : string could be omitted because TS would infer the return type.



function circle(diam: number): string {
  return "Circumf = " + Math.PI * diam
}

The same function as an ES6 arrow



const circle = (diam: number): string => "Circumf = " + Math.PI * diam

If we want to declare a function, but not define it, use a function signature



let sayHi: (name: string) => void
sayHi = (name: string) => console.log("Hi " + name)
sayHi("Danny") // Hi Danny

Type Aliases

Allow you to create a new name for an existing type. They can help to reduce code duplication.
They're similar to interfaces, but can also describe primitive types.



type StringOrNum = string | number
let id: StringOrNum = 24

Interfaces

Interfaces are used to describe objects. Interfaces can always be reopened & extended, unlike Type Aliases. Notice that name is readonly



interface Person {
  name: string
  isProgrammer: boolean
}

let p1: Person = {
  name: "Delia",
  isProgrammer: false,
}

p1.name = "Del" // Error - read only

Two ways to describe a function in an interface



interface Speech {
  sayHi(name: string): string
  sayBye: (name: string) => string
}

let speech: Speech = {
  sayHi: function (name: string) {
    return "Hi " + name
  },
  sayBye: (name: string) => "Bye " + name,
}

Extending an interface



interface Animal {
  name: string
}

interface Dog extends Animal {
  breed: string
}

The DOM & Type Casting

TS doesn't have access to the DOM, so use the non-null operator (!) to tell TS the expression isn't null or undefined



const link = document.querySelector("a")!

If an element is selected by id or class, we need to tell TS what type of element it is via Type Casting



const form = document.getElementById("signupform") as HTMLFormElement

Generics

Generics allow for type safety in components where the arguments & return types are unkown ahead of time



interface HasLength {
  length: number
}

// logLength accepts all types with a length property
const logLength = <T extends HasLength>(a: T) => {
  console.log(a.length)
}

// TS "captures" the type implicitly
logLength("Hello") // 5

// Can also explicitly pass the type to T
logLength<number[]>([1, 2, 3]) // 3

Declare a type, T, which can change in your interface



interface Dog<T> {

  breed: string

  treats: T

}

// We have to pass in a type argument

let labrador: Dog<string> = {

  breed: "labrador",

  treats: "chew sticks, tripe",

}

let scottieDog: Dog<string[]> = {

  breed: "scottish terrier",

  treats: ["turkey", "haggis"],

}

Enums

A set of related values, as a set of descriptive constants



enum ResourceType {

  BOOK,

  FILE,

  FILM,

}

ResourceType.BOOK // 0

ResourceType.FILE // 1

Narrowing

Occurs when a variable moves from a less precise type to a more precise type



let age = getUserAge()

age // string | number

if (typeof age === "string") {

  age // string

}

Thanks for reading

Hope this cheat sheet is useful!

Again, feel free to download the one-page PDF or order a poster:

One-page TypeScript cheat sheet PDF

Order a physical poster

For more from me, you can follow me on Twitter, or subscribe to my YouTube channel.

Cheers!

Git Cheat Sheet 📄 (50 commands + PDF and poster)

Danny Adams — Thu, 20 Jan 2022 18:49:47 +0000

I was tired of looking up the same common Git commands - so I made a cheat sheet that I could print and put on my office wall.

This cheat sheet contains 50 commonly used Git commands on the following topics:

Setting up Git
Starting a project
Making a change
Basic concepts
Branching
Merging
Rebasing
Undoing things
Reviewing your repo
Stashing
Synchronising local and remote repositories

Git Commands Cheat Sheet PDF

One page PDF to make it easy to copy and paste in commands.

Download the Git Commands Cheat Sheet PDF here

Both PDF and poster are available in Light Mode and Dark Mode:

Git Cheat Sheet Poster

Order a physical A3 poster for your office wall - so you can quickly look up commands, and keep them at the top of your head.

It comes in thick durable paper, and a matte, light-absorbing finish.

Order a Git Cheat Sheet Poster here

Here's mine on my office wall:

Here are all of the commands from the cheat sheet:

Setup

Set the name and email that will be attached to your commits and tags



$ git config --global user.name "Danny Adams"

$ git config --global user.email "myemail@gmail.com"

Starting a Project with Git

Create a local repo (omit <directory> to initialise the current directory as a git repo)



$ git init <directory>

Download a remote repo



$ git clone <url>

Make a Change

Add a file to staging



$ git add <file>

Stage all files



$ git add .

Commit all staged files to git



$ git commit -m "commit message"

Add all changes made to tracked files & commit



$ git commit -am "commit message"

Basic Git Concepts

main: default development branch
origin: default upstream repo
HEAD: current branch
HEAD^: parent of HEAD
HEAD~4: great-great grandparent of HEAD

Branches

List all local branches. Add -r flag to show all remote branches. -a flag for all branches.



$ git branch

Create a new branch



$ git branch <new-branch>

Switch to a branch & update the working directory



$ git checkout <branch>

Create a new branch and switch to it



$ git checkout -b <newbranch>

Delete a merged branch



$ git branch -d <branch>

Delete a branch, whether merged or
not



$ git branch -D <branch>

Add a tag to current commit (often used for new version releases)



$ git tag <tag-name>

Merging

Merge branch a into branch b. Add --no-ff option for no-fast-forward merge



$ git checkout b

$ git merge a

Merge & squash all commits into one new commit



$ git merge --squash a

Rebasing

Rebase feature branch onto main (to incorporate new changes made to main). Prevents unnecessary merge commits into feature, keeping history clean



$ git checkout feature

$ git rebase main

Interactively clean up a branches commits before rebasing onto main



$ git rebase -i main

Interactively rebase the last 3 commits on current branch



$ git rebase -i Head~3

Undoing Things

Move (&/or rename) a file & stage move



$ git mv <existing_path> <new_path>

Remove a file from working directory & staging area, then stage the removal



$ git rm <file>

Remove from staging area only



$ git rm --cached <file>

View a previous commit (READ only)



$ git checkout <commit_ID>

Create a new commit, reverting the changes from a specified commit



$ git revert <commit_ID>

Go back to a previous commit & delete all commits ahead of it (revert is safer). Add --hard flag to also delete workspace changes (BE VERY CAREFUL)



$ git reset <commit_ID>

Review your Repo

List new or modified files not yet committed



$ git status

List commit history, with respective IDs



$ git log --oneline

Show changes to unstaged files. For changes to staged files, add --cached option



$ git diff

Show changes between two commits



$ git diff commit1_ID commit2_ID

Stashing

Store modified & staged changes. To include untracked files, add -u flag. For untracked & ignored files, add -a flag.



$ git stash

As above, but add a comment.



$ git stash save "comment"

Partial stash. Stash just a single file, a collection of files, or individual changes from within files



$ git stash -p

List all stashes



$ git stash list

Re-apply the stash without deleting it



$ git stash apply

Re-apply the stash at index 2, then delete it from the stash list. Omit stash@{n} to pop the most recent stash.



$ git stash pop stash@{2}

Show the diff summary of stash 1. Pass the -p flag to see the full diff.



$ git stash show stash@{1}

Delete stash at index 1. Omit stash@{n} to delete last stash made



$ git stash drop stash@{1}

Delete all stashes



$ git stash clear

Synchronizing

Add a remote repo



$ git remote add <alias> <url>

View all remote connections. Add -v flag to view urls.



$ git remote

Remove a connection



$ git remote remove <alias>

Rename a connection



$ git remote rename <old> <new>

Fetch all branches from remote repo (no merge)



$ git fetch <alias>

Fetch a specific branch



$ git fetch <alias> <branch>

Fetch the remote repo's copy of the current branch, then merge



$ git pull

Move (rebase) your local changes onto the top of new changes made to the remote repo (for clean, linear history)



$ git pull --rebase <alias>

Upload local content to remote repo



$ git push <alias>

Upload to a branch (can then pull request)



$ git push <alias> <branch>

Thanks for reading

Hope this cheat sheet is useful!

Again, feel free to download the one-page PDF or order a poster:
One-page Git commands cheat sheet PDF
Order a physical poster

For more from me, you can follow me on Twitter.

Cheers!

Git Workflows - Solo Vs Team Work, Undoing Mistakes, Contributing to Open Source... and more

Danny Adams — Thu, 06 Jan 2022 18:40:18 +0000

In this article, I give my workflows for almost everything that you will ever need to do with Git:

Basic Git commands
Setting up a remote repository and pushing to Github
Undoing things in Git
Ignoring things in Git
Git branches for new features
Working solo vs in a team
Forking and contributing to open source

Basic Git Commands

These are the commands you will use in every single project.

1) Initialise Git

git init <project-name>

2) Add files to the staging area

To add all files:

git add .

To add all files in a specific folder:

git add src/posts/Git_Commands_Post

To add one file:

git add styles.css

To add all files with a specific extension (in this case, all html files):

git add *.html

3) Check the staging area is correct before committing to Git

git status

4) Committing the changes to Git

git commit -m "A short message describing the changes here"

5) Push to remote repository (see below for how to set up remote repository)

git push

Setting up a remote repository and pushing to Github

First we need to set up the repository on Github:

1) Go to github.com
2) Sign in or create an account
3) Select "New" to create a new repository
4) Type in your repository information. I always leave the "Add a README file", "Add a .gitignore" and "Choose a license" checkbox unchecked.
5) Click "Create repository"

Now we need to connect up our local repository to the just-created Github repository:

6) Add the remote repository

git remote add origin https://github.com/YourUsername/Your-remote-repo-name.git

7) Ensure we are in the main branch

git branch -M main

8) Push your committed local code to Github

git push -u origin main

Changing your username and email in Git

git config --global user.name "Danny Adams"
git config --global user.email "my-email@gmail.com"

Undoing things in Git

Remove a file from staging

The below command removes the file only from the Git repository. The local, working directory copy of the file will remain intact - this is ensured by adding the --cached option.

git rm --cached <filename>

To remove all files in a folder, add the recursive flag:

git rm --cached <filename> -r

Going back to a previous commit to READ ONLY

To see how things looked at a particular commit, without re-writing history or deleting things, we can simply:

1) Log the commit history and copy the ID of the commit we want to go back to

git log --oneline

2) Go back in time to the commit

git checkout <commit_ID>

3) Once done, go back to where we were

git checkout main

Reverting a commit

Revert commit creates a new commit, where the changes made in a specific commit are undone.

Let's say we wanted to undo what we did in commit 2 of the below branch:

Using Revert, a new commit would be made, where the changes made in C2 are undone - but C2 is still kept in history so we could still go back and keep the changes if we decide we want them again:

Let's go through an example. Below, I have 3 commits in my project - with the latest at the top:

Let's say I wanted to undo the changes I made with the "Created styles.css" commit only. I can simply revert this commit:

git revert a432c9f

Git will then open up a file in your text editor (if your using VS code) and ask you to create a message for the new commit:

By default, the commit message reads 'Revert "Created styles.css"', but this can be changed to whatever you want. I usually just leave it as is.

Once you're happy with the message, simply close the file and Git will add the new commit where the "Create styles.css" changes are undone.

But here's the beauty of using revert to undo things: the commit history is all still there.

As you can see, the "Created styles.css" commit is still there. Revert has simply made a new commit where the changes made in "Created styles.css" are reverted (undone). This is MUCH safer than using Reset - the next section - which deletes commits.

Reset commit

Reset commit goes back in time to a previous commit and permanently deletes all commits that happened ahead of it.

1) Get the Id of the commit you want to go back to

git log --oneline

2) Reset

git reset <commit_ID>

Note: all the code changes will still remain in the workspace files - but they'll be uncommitted. To remove from Git AND your workspace, use:

git reset <commit_ID> --hard (Very dangerous - be very careful!)

Tell Git to ignore certain files

Some files in your project will contain private information, such as passwords and keys. It's very important that this information isn't pushed to Github. Also, folders like the node_modules folder can take up lots of disc space, and there is no need for them to be pushed to Github as they can be reinstalled any time via the project's package.json file.

1) Create a .gitignore file in the root of your project
2) Add the names of the folders and files you want to ignore:

node_modules
secret-password.txt

It's important to add these files to .gitignore as soon as they are made. But if you have accidentally committed them to git, you can untrack them with the following commands:

1) Remove everything from the repository

git rm -r --cached .

2) Re add everything

git add .

Now everything apart from the files in your .gitignore will be added to the staging area.

3) Commit

git commit -m ".gitignore fix"

The local repository is now clean. Push the changes to Github to see the changes effective there too.

Git branches

A common Git paradigm is to always keep the main branch deployable. This means that whenever you're working on a new feature, you should create a new branch and make your commits to that. Then once the feature is complete, you can merge it back into main.

When working solo

If you're the only one contributing to a repo, then you can safely merge a feature into main without creating a pull request.

1) Create new branch and go into it

git checkout -b <branch-name>

2) Make your changes in this branch. Add and commit your changes as many times as necessary.

3) Checkout to main and merge the feature branch into main

git checkout main

git merge <branch-name> --no-ff

The no-fastforward flag creates a new merge commit and maintains history of the feature branches. Without this flag, the head will simply fastforward to the end of the feature without a new merge commit.

When working in a team

Let's say someone has added you to a Github repository, so that you can now contribute as part of the team.

To contribute, you will need to make a pull request. A pull request is for communicating and reviewing code, before merging it to main. Merging directly, and merging with a pull request are identical - the only difference is that a pull request creates a dedicated forum on Github for discussion - this allows team members to review your code before merging it.

1) Clone the Github repository

git clone <repo-url>

2) Ensure our code is up to date

Before making any changes, you should always make sure your local copy is up to date with the remote repo - as other devs may have contributed. Pull the latest code from remote repo.

git pull origin main

3) Create and checkout to new branch

git checkout -b <branch-name>

4) Make desired changes

5) Add and commit changes

git add .

git commit -m "some message"

6) Push the code in this branch to a branch in Github

git push origin <name-of-branch-for-Github>

7) Create a pull request

Go to the Github repo main branch and click "compare and pull request".

8) Leave a comment to explain exactly what you've done, then "create pull request".

Other team members will get an email for the request to pull your code into main. They can see changes, see commits, leave comments, and (if happy) merge the code into main.

Feature branch can be deleted once merged.

** But what if people make changes to main while your still working on the feature branch? **

git checkout main
git pull origin main
git checkout <feature-branch-name>
Merge the latest main branch into your feature branch

git merge main

You can now incorporate the latest changes by other devs into your feature.

Note: you may need to iron out merge conflicts. This is normal and part of working with Git.

Forking and contributing to open source projects

If you don't have write access to a repo, but still want to contribute to it, you can Fork the project:

Find an open source public repo
Fork the repo (create a copy to your own Github account)
git clone <url-of-your-fork>
Make changes (could also create a new branch for the changes then push to a new branch)
git add . git commit -m "message" git push origin main
Go to your forked copy on Github and click "New pull request"
"Create pull request" - this pulls your code into the parent repo to be reviewed for merging. YOU CAN'T MERGE THIS - only the repo owners are allowed.

Git Cheat Sheet Poster

I was tired of looking up common Git commands, and having to sift through waffle. So I recently made a Git Cheat Sheet poster with 50 common Git commands for my office wall.

It comes in thick durable A3 paper, and a matte, light-absorbing finish.

Order a Git Cheat Sheet Poster here.

Thanks for reading

Hopefully that was helpful.

For more from me, you can:

👋

How to Compare Arrays in JavaScript Efficiently

Danny Adams — Thu, 05 Aug 2021 16:15:25 +0000

In this article, I’m going to show you two ways of solving a typical interview-style question. The first solution is more obvious and less efficient. The second solution introduces a great problem-solving tool: frequency counter objects, which greatly improves the efficiency.

Here’s what you’ll gain from reading this article:

A framework for approaching problems
A very useful, highly performant problem solving technique
An improved ability to analyse functions and improve performance

I also made a YouTube video for those that like video. If you enjoy the video, consider subscribing to my channel.

The problem

“Write a function called “squared” which takes two arrays. The function should return true if every value in the array has its value squared in the second array. The frequency of values must be the same.”

-- Your interviewer

At first, I will show you the “Naïve” way of solving the problem – the more obvious way that isn’t efficient.

I’ll then show you an efficient way to solve the problem using “frequency counter objects”. This is a very handy technique to have in your problem-solving toolbox (your brain).

Understanding the problem

Problem solving 101: Before we attempt to write a solution, it’s very important to understand the problem - to give some examples and the results we expect. We can then use these examples as tests to ensure our solution is working correctly.

Examples:

Squared([1, 2, 3], [9, 1, 4]) // true
Squared([1, 2, 3], [1, 4]) // false
Squared([2, 2, 3], [4, 9, 9]) // false

Example 1 is true because:

1² = 1 (yep, that’s in array 2)
2² = 4 (yep, that’s in array 2)
3² = 9 (yep, that’s in array 2)

Example 2 is false because:

1² = 1 (yep, that’s in array 2)
2² = 4 (yep, that’s in array 2)
3² = 9 (nope, that's not in array 2)

Example 3 is false because:

2² = 4 (yep that’s in array 2)
2² = 4 (nope, there is only one 4 in array 2)
3² = 9 (yep, but we won’t even get to this check because the function returned false beforehand)

The “naïve” way

First, we check if the arrays are not equal length. If not, we return false and get out of the function early because the frequency of values can’t possibly be the same.

Next, we loop over each number (num) in arr1. Inside the loop, we use indexOf() to look for the position of num2 in arr2. The value is assigned to the variable foundIndex.

If the value was not found, indexOf returns -1. So, we can check if foundIndex = -1, and return false if so.

If all is good, we move on and remove this value from arr2 using the splice() method. This ensures the frequency of values in both arrays are the same.

After looping over each number, and all the checks pass, we can return true.

function squared(arr1, arr2) {
  if (arr1.length !== arr2.length) return false

  for (let num of arr1) {
    let foundIndex = arr2.indexOf(num ** 2)

    if (foundIndex === -1) return false

    arr2.splice(foundIndex, 1)
  }

  return true
}

Performance

This algorithm has a Big O(n²) because we loop over every single item in the first array, then inside this loop, we are looping over every single item in the second array (with indexOf()) at worst-case.

If you don’t know (or have forgotten) what Big O is, check out this video: Big O Notation in JavaScript. It’s an important topic!

If the arrays are of length n, then the number of operations will be n * n = n². Hence Big O(n²).

Now, this is not quite true because the second array becomes shorter on each loop, so on average we will only loop over half the second array (0.5n). The Big O will be of n * 0.5n = 0.5n². But Big O looks at big picture stuff, and as the input approaches infinity, the 0.5 will be insignificant and so we simplify to Big O(n²).

A smarter way – Frequency Counter Objects – Big O(n)

What are Frequency Counter Objects?

Frequency counters are objects that tally things up. Here’s two examples of where they would be useful:

The number of times a character appears in a string
The number of times a number appears in an array

Using frequency counters can also significantly improve the performance of an algorithm, as it can often remove the need to use nested for-loops.

Here’s what the frequency counter object for [1, 2, 3, 4, 3] would look like:

let frequencyCounter = {
  1: 1,
  2: 1,
  3: 2,
  4: 1,
}

All the numbers appear once, apart from 3, which appears twice.

The solution

To create a frequency counter object, we loop over the array in question. We then create a key and give it a value of the current value + 1, or if it’s the first time we’ve encountered this number, frequencyCounter[num] will be undefined and so we initialise the value to 1.

I used two for…of loops as I felt it was easier to read, but it could also be done with just one for-loop.

The frequency counter objects can then be compared. We first check if each key squared from frequency counter 1 is a key in frequency counter 2. If not, return false.

Next, we check if the frequencies (values) are equal. If not, return false.

And if we get through all this unscathed, we get to the bottom and return true.

function squared(arr1, arr2) {
  if (arr1.length !== arr2.length) return false

  let frequencyCounter1 = {}
  let frequencyCounter2 = {}

  // Create frequencyCounter1
  for (let num of arr1) {
    frequencyCounter1[num] = frequencyCounter1[num] + 1 || 1
  }

  // Create frequencyCounter2
  for (let num of arr2) {
    frequencyCounter2[num] = frequencyCounter2[num] + 1 || 1
  }

  // Compare frequency counters
  for (let key in frequencyCounter1) {
    if (!(key ** 2 in frequencyCounter2)) return false

    if (frequencyCounter1[key] !== frequencyCounter2[key ** 2]) return false
  }

  return true
}

Performance

To create frequencyCounter1, we loop over all the numbers in arr1 => n loops
Same for frequencyCounter2 => n loops
To compare the frequency counters, we loop over all the keys in frequencyCounter1 => at worst case, n loops

Total = n + n + n = 3n

Resulting in a Big O(n) – linear time complexity.

Much better than our first effort of with Big O(n²) – quadratic time complexity.

Awesome references

I can attribute almost all of my knowledge of algorithms and data structures to one outstanding course: JavaScript Algorithms and Data Structures Masterclass by Colt Steele.
If you prefer books: JavaScript Data Structures and Algorithms: An Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals by Sammie Bae

If you enjoyed this post, consider subscribing to my YouTube channel - it would be much appreciated!

Thanks for reading.

Have a great day!

Merge Sort in JavaScript | Explained Thoroughly

Danny Adams — Wed, 04 Aug 2021 17:07:58 +0000

Merge Sort is one of the most popular and efficient sorting algorithms.

In this article we will discuss:

The logic behind Merge Sort
How to implement Merge Sort in JavaScript
The performance of Merge Sort
The advantages and disadvantages of Merge Sort

This article was originally published on DoableDanny.com.

What is the Merge Sort Algorithm?

Merge Sort is, you guessed it, a sorting algorithm that can be used to order the items of an array from smallest to largest. It takes in an array, sorts it, then spits it out:

Merge Sort is an out-of-place, stable, and comparison-type sorting algorithm

Out-of-place means that the algorithm requires additional data structures when sorting. This is opposite to in-place sorting algorithms, where the input is simply overwritten and no extra data structures are required.

Stable means that two elements with equal values will appear in the same order in the sorted output as they appear in the unsorted input array.

And finally, a comparison sort is a sorting algorithm that only reads the list of elements through a single abstract comparison operation (usually a “less than” or “equal to”) that determines which of the two elements should occur first in the final sorted output array.

Check out my In-place, stable, comparison article if you don’t quite understand the above, or don’t know why it’s important to know these properties of an algorithm.

Merge Sort logic

Merge Sort is a combination of two things: merging and sorting. It exploits the fact that arrays of 0 or 1 item are always sorted e.g.:

[] is always sorted
[4] is always sorted
[5, 4] is not sorted

Merge Sort works by decomposing an array into smaller arrays of 0 or 1 items, then building up a newly sorted array.

First, we divide the array up until we get arrays of 0 or 1 item. This is the “base case” – we know these arrays are sorted because they are 1 or 0 long.

Next, we merge these smaller arrays until we get to the final sorted one:

Here’s a good gif of Merge Sort:

If that doesn’t quite make sense, check out these folk dancers demonstrating merge sort then re-read the above - things will then become clear!

Also, check out Visualgo for beautiful visualisations of sorting algorithms. It’s a great resource to have bookmarked when studying algorithms.

Now you have an idea for how Merge Sort works, let’s put it into code.

Merge Sort - JavaScript

Writing a merge helper function

First, we need to understand how to merge two sorted arrays.

In order to implement Merge Sort, it’s useful to first implement a function responsible for merging two sorted arrays.

Given two arrays which are sorted, this helper function should create a new array which is also sorted, and consists of all the elements in the two input arrays.

Here is our merge helper function. Remember, it accepts two SORTED arrays and merges them into one, larger sorted array.

function merge(left, right) {
  let sortedArr = [] // the sorted items will go here

  while (left.length && right.length) {
    // Insert the smallest item into sortedArr
    if (left[0] < right[0]) {
      sortedArr.push(left.shift())
    } else {
      sortedArr.push(right.shift())
    }
  }

  // Use spread operators to create a new array, combining the three arrays
  return [...sortedArr, ...left, ...right]
}

merge([1, 4], [2, 6, 9]) // [1, 2, 4, 6, 9]

Our merge algorithm runs at O(n + m) where n and m are the lengths of the first and second arrays respectively. This is because we iterate over each item in each array once. This just boils down to a Big O(n) => linear time complexity.

Writing the Merge Sort function

Next we can write a mergeSort function that uses recursion to halve the arrays with the slice() method. The base case is when the arrays have a length of 1 or 0.

function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) return arr

  let mid = Math.floor(arr.length / 2)

  // Recursive calls
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))

  return merge(left, right)
}

mergeSort([3, 5, 8, 5, 99, 1]) // [1, 3, 5, 5, 8, 99]

Merge Sort – step-by-step

The image below shows the steps that occur when mergeSort([10, 24, 76, 73]) is called (operation 0). We finish up with a sorted array at step 16.

Big O of Merge Sort

Unlike some other sorting algorithms, such as Bubble Sort and Insertion Sort, Merge Sort doesn’t care whether the data is almost sorted or not. It will split the array up and merge them back together no matter if the input array is already sorted (best), “random” (average), or in-reverse (worst). For a given length input, the number of operations will always be the same – no matter what order it’s in.

*Best-case Time Complexity of Merge Sort: * O(nlog(n))

*Average-case Time Complexity of Merge Sort: * O(nlog(n))

*Worst-case Time Complexity of Merge Sort: * O(nlog(n))

O(n log(n)) is a combination of linear time, O(n), and logarithmic time, O(log(n)). O(n log(n)) is known as linearithmic time.

But where does this log(n) come from? If the length of the input array is 8, then the array will be divided in half three times:

8 => 4 4 => 2 2 2 2 => 1 1 1 1 1 1 1 1

Each arrow represents a division by 2. We start with one array of 8 items, then two arrays of 4 items, then four arrays of 2 items, and finally eight arrays of 1 item.

This is logarithmic time. Every time we double the size of the input, the number of operations (divisions) increases by just 1.

Now I’ve explained where the log(n) comes from, what about the n? The n comes from the merge helper function. It has to make roughly eight comparisons for an array of 8 items; hence linear time.

So, in total, the worst-case time complexity of Merge Sort is O(n log(n)). The best worst-case we can get from a sorting algorithm.

Merge Sort is one of the most efficient sorting algorithms for sorting large arrays.

However, if you know that the input array will be small, or sorted/almost sorted, you might be better off using an algorithm like insertion sort which is of O(n) at best case (O(n2) worst case).

Space Complexity of Merge Sort

Merge Sort is very fast for a sorting algorithm, but as with most algorithms, the gains in speed come with the cost of taking up more space in memory. The larger the array, the more arrays that have to be stored in memory (from dividing them up). But in most cases, this isn’t a problem, usually we care more about time than space.

The space complexity of Merge Sort is O(n).

Performance summary table

If you Want to Master Algorithms...

If you want to further your knowledge of algorithms and data structures, check out: JavaScript Algorithms and Data Structures Masterclass by Colt Steele. It’s the best Udemy course I’ve ever taken 👌.

If you enjoyed this article, you can say thanks by subscribing to my [YouTube channel (https://www.youtube.com/channel/UC0URylW_U4i26wN231yRqvA) or by signing up to my blog to be notified of new posts 🙏

Also, feel free to connect with me on Twitter!

Thanks for reading!

Important Algorithm Concepts | Algorithm Stability, In-place Algorithms, and Comparison Algorithms

Danny Adams — Tue, 03 Aug 2021 16:38:59 +0000

This article was originally posted on DoableDanny.com.

In this article, we will discuss some important properties of algorithms that can help you to decide which algorithm is best suited to the job.

In this article we will define and discuss:

Algorithm stability
In-place and out-of-place algorithms
Comparison and non-comparison sorts

Don’t worry if you’ve never heard these terms before, I’ll explain them fully as we go.

What is stability in sorting algorithms and why is it important?

Stable means that two elements with equal values will appear in the same order in the sorted output as they appear in the unsorted input array.

For example, if we wanted to sort:

[“Cherries“, “Blackberries”, “Apples”, “Bananas”]

into alphabetical order by first letter, with a stable sorting algorithm, the output would be:

[“Apples”, “Blackberries”, “Bananas”, “Cherries”]

As you can see, “Blackberries” and “Bananas” remained in the same relative positions in the input and output array because the algorithm is stable.
Stable sorting algorithms:

Bubble Sort
Merge Sort
Radix Sort

If the algorithm was unstable, then “Bananas” and “Blackberries” may be interchanged ([“Apples”, “Bananas”, “Blackberries”, “Cherries”]).

Unstable sorting algorithms:

Selection Sort
Heap Sort
Quick Sort

Why is it important to know if an algorithm is stable?

Suppose we have an array of first and last names and we needed to sort by first name, then by last name, e.g.:

[“Danny Adams”, “Bill Gates”, “Dan Jenkins”, “Dylan Grub”]

First, we could sort by first name using either a stable or unstable algorithm because we don’t need to preserve relative positions. Let’s say we use an unstable sorting algorithm, and we get back:

[“Bill Gates”, “Dylan Grub”, “Dan Jenkins”, “Danny Adams”]

The array is now in order by first name – great. But now we need to be careful: the relative positions need to be respected when we sort by last name; we don’t want “Bill Gates” to get swapped with “Dylan Grub” – this could happen if we used an unstable sorting algorithm.

Using a stable algorithm to sort by last name, we’d safely end up with:
[“Bill Gates”, “Danny Adams”, “Dylan Grub”, “Dan Jenkins”]

Happy days.

What is an In-place sorting algorithm?

An in-place sorting algorithm is an algorithm which transforms input using no auxiliary data structure; however, a small amount of extra storage space is allowed for auxiliary variables.

In simple terms, “in-place” just means that the input is overwritten (via swapping or replacement) by the output as the algorithm executes.

The advantage of in-place algorithms is that they take up less space in memory. The input is overwritten, and so no extra data structures are required; this doesn’t include constant time variables, which will never take up much space, such as the i in for-loops.

In-place algorithms have constant space complexity. Out-of-place algorithms have greater than constant space complexity, e.g.: linear time or quadratic time.

In-place algorithms: Bubble Sort, Selection Sort, Insertion Sort, Heap Sort.

Out-of-place: Merge Sort.

What is a comparison algorithm?

A comparison sorting algorithm is an algorithm that only reads the list of elements through a single abstract comparison operation (usually a “less than” or “equal to”) that determines which of the two elements should occur first in the final sorted output array.

Comparison sorting algorithms:

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort

An example of a non-comparison-type sorting algorithm would be Radix Sort. It avoids comparison by creating and distributing elements into buckets according to their radix. Radix Sort exploits the face that information about the size of a number is encoded in the number of digits; more digits equals a bigger number.

If you Want to Master Algorithms...

If you enjoyed this article, you can say thanks by subscribing to my YouTube channel or signing up to my blog to be notified of new posts 🙏

Also, feel free to connect with me on Twitter!

Thanks for reading,

Have a great day!

Binary Search - JavaScript | Plus Big O Performance Explained Simply

Danny Adams — Mon, 02 Aug 2021 17:31:02 +0000

This article was originally published on DoableDanny.com

The Binary Search algorithm is used to search for any element in a sorted array. If the element is found, it returns the element’s index. If not, it returns -1.

Binary Search is a simple and intuitive algorithm that also has great performance; it can find the value fast – much faster than the Linear Search algorithm (as used by the built-in method indexOf()) when the array is large.

Binary Search Steps

Binary search is a “divide and conquer” type algorithm, meaning it divides the array roughly in half every time that it checks whether a value is the one we are looking for.

Why? It means that upon every check, the data the algorithm has to work with gets halved upon each comparison, allowing the value to be found much faster.

See the gif below demonstrating Binary and Linear Search. The target is the value 9.

With Linear Search, if the target is at the end of the array, every single element has to be looped over and checked if it equals the target.

With Binary Search we:

Start in the middle and check if the target is greater or less than that middle value.
If the target is greater than the middle value, we will next look at the second half of the array (ignore the left side)
If the target is smaller, we look at the first half of the array (ignore the right side).
We pick the middle of that half and check if it’s greater or less than our target.
Repeat this process until we find our target.

Example: [1, 2, 5, 9] with target= 5

Start at middle (even length array, so middle – 1): [1, 2, 5, 9]
Is 5 greater than, smaller than, or equal to 2?
Greater, so 5 must be in the right half of the array: [5, 9].
Pick new middle: [5, 9]
Is 5 greater than, smaller than, or equal to 5?
Equal! Return the index of that element, 2.

So, with Binary Search, the data set keeps getting divided in half until we find our target. This tremendously decreases time complexity!

Binary Search in JavaScript

Now we understand the logic of Binary Search, let’s implement it in JavaScript.

function binarySearch(arr, target) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    let middle = Math.floor((start + end) / 2)

    if (arr[middle] < target) {
      // Search the right half
      start = middle + 1
    } else if (arr[middle] > target) {
      // Search the left half
      end = middle - 1
    } else if (arr[middle] === target) {
      // Found target
      return middle
    }
  }

  // Target not found
  return -1
}

console.log(binarySearch([1, 2, 3, 4], 1)) // 1
console.log(binarySearch([1, 2, 3, 5, 9], 4)) // -1
console.log(binarySearch([1, 2, 3, 4, 5], 5)) // 4
console.log(binarySearch([0, 3], 3)) // 1

Here’s what’s going on:

The function accepts a sorted array and a target value.
Create a left pointer at the first element of the array, and a right pointer at the last element of the array.
While the left pointer comes before the right pointer:
- Create a pointer in the middle.
- If the target is greater than the middle element, move the left pointer up.
- If the target is less than the middle element, move the right pointer down.
- If the target equals the middle, return the index.
If the value isn’t found, return -1.

On each iteration of the while loop, we are effectively discarding half of the array, until we find our value or until we’ve exhausted the array.

Binary Search time complexity

We will now discuss the performance of Binary Search in terms of Big O Notation.

If you're unfamiliar with Big O, I strongly suggest that you check out this article I wrote: Big O Notation in JavaScript | The Ultimate Beginners Guide with Examples.

It's a very important topic and will undoubtedly make you a better developer.

Best case complexity of Binary Search

The best case complexity of Binary Search occurs when the first comparison is correct (the target value is in the middle of the input array).

This means that regardless of the size of the array, we’ll always get the result in constant time. Therefore, the best case time complexity is O(1) - constant time.

Worst case complexity of Binary Search

The worst case complexity of Binary Search occurs when the target value is at the beginning or end of the array.

See the image below: if we have an array 32 elements long and our target is 32, then the array will be divided five times until we find 32. So, the Big O complexity of binary search is O(log(n)) – logarithmic time complexity: log(32) = 5.

Average case complexity of Binary Search

The average case is also of O(log(n)).

Space complexity of Binary Search

Binary Search requires three pointers to elements (start, middle and end), regardless of the size of the array. Therefore the space complexity of Binary Search is O(1) – constant space.

Performance summary table

Linear Search vs Binary Search

Binary Search has much better time complexity than Linear Search, which has a Big O(n) – linear time.

From the graph of Big O Notation below, we can see that with larger input arrays, Binary Search (yellow line) will take a lot less time to compute than Linear Search (blue line).

It should be noted that Binary Search only works on sorted arrays. The sorting step, if using an efficient algorithm, will have a time complexity of O(nlog(n)). Since Linear Search can work on sorted arrays, if the array is small, or if we need to search the array just once, then Linear Search might be a better choice.

Binary Search is a great choice if we have to make multiple searches on large arrays. For example, if we have a large 10,000 element array, Linear Search would require 10,000 comparisons at worst case. Binary Search would require log(10,000) = 14 comparisons. That’s a lot less!

If you Want to Master Algorithms...

If you enjoyed this article, you can say thanks by subscribing to my YouTube channel 🙏

Also, feel free to connect with me on Twitter!

Thanks for reading!

Linear Search in JavaScript | Must-Know Beginner Algorithms

Danny Adams — Mon, 12 Jul 2021 17:26:25 +0000

This article was originally posted on DoableDanny.com.

Intro

Linear search is a very common searching algorithm; It is implemented under the hood in the JavaScript built-in methods indexOf(), includes(), find(), and findIndex().

It is also the most straight-forward searching algorithm: it simply loops over each element in an array and stops if that element equals our target value.

Linear Search steps

I think that with this algorithm, the gif below explains it all. But here are the steps in words:

Linear search will accept an array and a target value.
Start searching from the beginning of the array.
Check if that value equals the target:
- If so, stop and return that values index.
- If not, move onto the next element.
Repeat step 3 until all elements are checked. If target not found, return -1.

Source of the above gif: bournetocode.com

And if you ever find yourself looking for a specific length of French fry:

Linear Search in JavaScript

function linearSearch(arr, target) {
  for (let i in arr) {
    if (arr[i] === target) return i
  }

  return -1
}

console.log(linearSearch([1, 2, 3, 4], 1)) // 0
console.log(linearSearch([1, 2, 3, 4], 4)) // 3
console.log(linearSearch([1, 2, 3, 4], 6)) // -1
console.log(linearSearch([3, 4, 1, 6, 3], 6)) // 3

We simply loop over each element in the array, and check to see if the current element is equal to the target; if so, we return that elements index. If the target isn’t found, then we simply return -1 at the end of the function.

Time complexity of Linear Search

Best-case time complexity of Linear Search

If our target value is at the beginning of the array, the algorithm will always run at constant time, O(1). The algorithm will always only have to perform one comparison, no matter what the size of the array.

Worst-case time complexity of Linear Search

If our target is the last element in the array, then the algorithm will have to make n comparisons (n being the length of the input array). This means that the Big O notation of Linear Search is Big O(n) – linear time complexity.

Average-case time complexity of Linear Search

If our target element is somewhere in the middle of the array, then the time complexity will be approximately O(n/2), which simplifies to O(n) – linear time.

Space complexity of Linear Search

Linear Search has a space complexity of O(1) – constant space. It uses no auxiliary data structures to find the target value.

Performance summary table

When to use Linear Search

Linear search is the best we can do when searching in unsorted arrays, such as [2, 3, 1].

Whilst there are searching algorithms that can perform faster, such as Binary Search, they can only search through sorted arrays.

If you enjoyed this post, subscribe to my newsletter. I write on topics such as algorithms, UI design and freelancing. I’ll email you once per week with my latest article and bonus tips and tricks. I like to dive deeply into topics to give you all the information you need in one place!

Also, check out and subscribe to my coding YouTube Channel.

And if you want to further your knowledge of algorithms and data structures, check out: JavaScript Algorithms and Data Structures Masterclass by Colt Steele. It’s the best Udemy course I’ve ever taken 👌.

Thanks for reading,

Have a great day!