DEV Community: Cole Gawin

Leveraging Vector Embeddings and Similarity Search to Supplement ChatGPT’s Training Data

Cole Gawin — Fri, 07 Jul 2023 17:15:17 +0000

Since the release of OpenAI’s ChatGPT, and later its REST API, the technology world has been enveloped by the vast capabilities of this paradigm-shifting technology and pushing it to its limits. However, for as many strengths as it has, ChatGPT has two pronounced weaknesses: 1) its training data cutoff is 2021, meaning it has no knowledge of the information in more recent times, and 2) it is prone to hallucinations or making up information.

To circumvent this issue, software developers and prompt engineers alike have taken on the task of supplementing ChatGPT’s knowledge base with additional information that can provide more relevant, reliable, and informed responses. This process involves a combination of technologies and prompt engineering that we’ll discuss in depth in this series.

In this article, we'll explore how we can transform textual data into vector embeddings and utilize similarity search to find related documents that can help ChatGPT answer questions with reliable, domain-specific information. We generated a databank of documents from Nourish by WebMD in the previous article in this series—we will use that databank as the documents for our vector embeddings and similarity search.

This is part two of my series on creating a nutrition chatbot powered by data from WebMD using sentence-transformers, FAISS, and ChatGPT.

Part 1: Webscraping Techniques to Source Reliable Information for ChatGPT

Part 2: Leveraging Vector Embeddings and Similarity Search to Supplement ChatGPT’s Training Data

Part 3: ChatGPT Prompt-Engineering Techniques for Providing Contextual Information (coming soon)

Vector embeddings are mathematical representations of words or phrases in a high-dimensional vector space. These embeddings encode both syntactic and semantic between words and phrases, and the importance of this nuance cannot be understated. Thanks to vector embeddings, we are essentially able to represent the meaning of a text snippet with numbers, which allows us to do mathematical operations on them.

One of those mathematical operations is similarity search, which compares the distance between two vectors to determine how "similar" they are. For example, if you were to create vector embeddings for the words "dog", "cat", and "house", the "dog" and "cat" vectors would most likely have the least distance and therefore be the most similar since they are most closely related. There are different distance metrics that can be used for similarity search, such as cosine distance or Euclidean distance.

To turn our nutrition databank into vector embeddings, we'll use the sentence-transformers python library. Sentence Transformers comes with many pre-trained models that excel at vectorizing text and run locally on our machine. Alternatively, you could use OpenAI's embeddings API, but that is much more costly and much slower for little marginal benefit.

To index our vector embeddings and perform similarity search over them, we'll use the FAISS library developed by Meta AI. FAISS comes with superb tooling for efficient vector index creation, and allows us to save our indices to disk.

You can do this project in a Jupyter Notebook or on a platform like Google Colab. Alternatively, you can create a new Python project in an IDE like Pycharm or VS Code. I recommend using a Jupyter Notebook for following along with this article.

The code in this article is also available for you to follow along (and run yourself) on Google Colab.

Getting Started

Let’s first install the necessary dependencies for this project:

pip install sentence_transformers faiss-cpu numpy

We're installing faiss-cpu here, but if you are running this on a machine with a capable GPU, you could alternatively install faiss-gpu. We'll be using numpy since it interfaces well with sentence-transformers and FAISS.

Generate Vector Embeddings

Sentence Transformers offers a multitude of pre-trained models to vectorize text, ranked on its documentation. Since our ultimate goal is to create a chatbot in which users ask questions and the bot responds with an answer, it makes most sense to choose a "QA" model that excels in semantic search—furthermore, the faster the better if we want to provide a quality user experience. I chose to use the multi-qa-MiniLM-L6-cos-v1 model since it is extremely fast and takes up little disk space and performs highly with semantic search.

Let's write a function generate_embeddings that uses Sentence Transformers to encode text into a vector:

import numpy as np
from sentence_transformers import SentenceTransformer

# Load the pre-trained SentenceTransformer model for generating sentence embeddings.
model = SentenceTransformer("multi-qa-MiniLM-L6-cos-v1", device="cpu")


def generate_embedding(text):
    response = model.encode([text])  # Encode the text using the pre-trained model
    return np.array(response[0])  # Return the generated embedding as a NumPy array

This function can be called with any piece of text, and it will use sentence-transformers to embed that text into a vector!

We're only encoding one piece of text at a time here by providing an array with one element to model.encode, but you could vectorize multiple at a time if you wish.

We'll also create a utility VectorStore class that will store all of our documents and their respective embeddings. Each document in documents will have an embedding in embeddings stored at the corresponding index—i.e. documents[0] will correspond to embeddings.iloc[0].

import numpy as np


class VectorStore:
  def __init__(self):
    self.documents = []
    self.embeddings = np.empty((0,384))  # Initialize as empty array

  def add_to_store(self, document):
    # Append the document to the list of documents
    self.documents.append(document)

    # Generate the embedding for the document
    embedding = generate_embedding(document.content)

    # Concatenate the response with the existing embeddings vertically
    self.embeddings = np.vstack((self.embeddings, embedding))

add_to_store will generate an embeddings for the content of the provided content, and append the new embedding to the existing embeddings (vertical stacking).

Note that we initialize self.embeddings to a numpy array of shape (0,384)—this is because the multi-qa-MiniLM-L6-cos-v1 Sentence Transformers model provides a vector with 384 dimensions.

Now, we can create our vector store by iterating through each of the documents in docs:

def generate_vector_store():
  store = VectorStore()

  for i in range(len(docs)):
    print(f"Processing {i}...")
    store.add_to_store(docs[i])

  return store

Once we run this function, we will have a vector store that contains all of our documents and their corresponding vector embeddings! Neat, right?

Saving our FAISS index

We need a way to save our vector store with the documents and vector embeddings to disk so we can import and load them on demand. To accomplish this, we'll use FAISS.

First, we have to create an index from our vector embeddings. FAISS provides many indexing algorithms, each with their own pros and cons. You can read more on these algorithms (flat indexes, locality sensitive hashing, hierarchical navigable small worlds, etc.) on Pinecone's incredible FAISS tutorial. For the sake of simplicity, we will just use IndexFlatL2, but I encourage you to experiment with other indexing algorithms!

import faiss


def create_index(embeddings):
  # Create an index with the same dimension as the embeddings
  index = faiss.IndexFlatL2(embeddings.shape[1])

  # Add the embeddings to the index
  index.add(embeddings)

  # Return the created index
  return index

Great, now we have our FAISS index ready to store to disk. To do so, FAISS provides a write_index method:

import faiss

faiss.write_index(store.create_index(), 'index.faiss')

And that's it! Pretty straight forward.

Experimenting with our Vector Index

Now that we have a FAISS vector index with our embeddings, we can play around with similarity search on our databank to see the sources it provides in response to a query.

To perform similarity search on a FAISS index, we can use index.search. This method accepts two arguments: the first is the vector used to find similar vectors, and the second is how many vectors to identify. The second argument is known as "k"; FAISS similarity search is a "k-selection algorithm", meaning it finds the "k" nearest neighbors to the provided vector.

Say we wanted to find 3 documents in our nutrition databank that include information on the healthiest types of meat. How would we go about this?

We must first generate a vector embedding for our search query. Remember that similarity search compares vectors to vectors, not text to text!
We call index.search on our FAISS index. This gives us the indices of the closest document embeddings in the index, as well as their distances from the search query.
We find the document corresponding to that index.

import numpy as np

# Generate embedding for the given query
query_embedding = generate_embedding("healthiest types of meat")

# Search for similar embeddings in the index
distances, results = index.search(np.array([query_embedding]), k=3)

# Print the content of the documents
for i in results[0]:
  print(docs[i].content)

Sure enough, this prints out 3 documents that contain relevant information to what the "healthiest types of meat" are!

Similarity Threshold

What happens when we use a query that doesn't have much relevance to what's in our databank, like "best building materials"? The documents aren't super helpful—they contain information on things that are tangentially related like "urban agriculture" but nothing that can help us learn more about building materials.

This begs the question, how can we algorithmically determine whether a document is truly "similar" to the search query?

Well, we can use the distances provided by the FAISS search. If you take a look at the distances for documents similar to "healthiest types of meat", they are all much less than the distances for "best building materials". Through trial an error, we can establish a similarity threshold for this case scenario as 1.

Note that similarity thresholds will likely differ based on numerous factors, such as the quality of your databank, which similarity search and/or indexing algorithms you use, and which vector embedding model you use.

If we filter our results to make sure their distances are less than our similarity threshold, we will only get truly similar documents that are relevant to our query.

# Import required libraries
import numpy as np

# Set the similarity threshold
similarityThreshold = 1

# Generate embedding for the given query
query_embedding = generate_embedding("healthiest types of meat")

# Search for similar embeddings in the index
distances, results = index.search(np.array([query_embedding]), k=3)

# Filter the results based on the similarity threshold
filtered_results = []
for i, distance in zip(results[0], distances[0]):
  if distance <= similarityThreshold:
    filtered_results.append(i)

# Print the content of the documents
for i in filtered_results:
  print(docs[i].content)

Sometimes, there may not be any relevant content. In this case, you can say the query is outside the scope of your databank—depending on the quality and size of your databank, you may also determine that the query is not relevant to your similarity search application.

Conclusion

Vector embeddings and similarity search are incredibly powerful means for finding relevant content to a search query. By transforming textual data into vector embeddings, we are able to represent the meaning of text snippets with numbers, allowing us to perform mathematical operations on them. Similarity search then enables us to find related documents to our search query.

The process of generating vector embeddings involves using the sentence-transformers library, which offers pre-trained models that excel at vectorizing text. We can then use the FAISS library for efficient vector index creation and perform similarity search over the indexed embeddings.

Through experimentation with our vector index, we can see how similarity search can retrieve relevant documents based on a query. By establishing a similarity threshold, we can filter the results to include only truly similar and relevant documents.

In the next article in this series, we will use similarity search on our databank to provide contextual information to ChatGPT, thereby enhancing its ability to answer domain-specific questions with reliable information and citations.

Web-Scraping Techniques to Source Reliable Information for ChatGPT

Cole Gawin — Wed, 05 Jul 2023 00:45:03 +0000

Since the release of OpenAI's ChatGPT, and later its REST API, the technology world has been enveloped by the vast capabilities of this paradigm-shifting technology and pushing it to its limits. However, for as many strengths as it has, ChatGPT has two pronounced weaknesses: 1) its training data cutoff is 2021, meaning it has no knowledge of information in more recent times, and 2) it is prone to hallucinations or making up information.

To circumvent this issue, software developers and prompt engineers alike have taken on the task of supplementing ChatGPT's knowledge base with additional information that can provide more relevant, reliable, and informed responses. This process involves a combination of technologies and prompt engineering that we'll discuss in depth in this series.

In this article, we'll investigate how we can write a program to scrape the internet for content that we can use to supplement an LLM like ChatGPT's knowledge beyond its training data. Specifically, we'll gather information from Nourish by WebMD and process articles to create a databank of sources on nutrition that will be used to power a nutrition chatbot.

This is part one of my series on creating a nutrition chatbot powered by data from WebMD using sentence-transformers, FAISS, and ChatGPT.

Part 1: Web-Scraping Techniques to Source Reliable Information for ChatGPT
Part 2: Leveraging Vector Embeddings and Similarity Search to Supplement ChatGPT's Training Data (coming soon)
Part 3: ChatGPT Prompt-Engineering Techniques for Providing Contextual Information (coming soon)

Nourish by WebMD provides a plethora of articles related to nutrition and eating well. Each article is conveniently broken up into multiple sub-headings, with the text underneath each heading providing additional relevant information to the main article topic. Since each sub-heading contains specific information on a sub-topic related to the main topic, instead of choosing the save the entire article as one "document" so to say, we'll want to break the article up by headings into multiple documents.

All of the articles are listed on WebMD's Health & Diet Medical Reference, which is paginated to 23 pages at the time of writing. Each page in this reference contains additional articles that we will need to scrape.

To perform the web scraping, we'll use the BeautifulSoup library, as well as the built-in requests library. Recall that we have to iterate through each paginated page in the Reference. We'll then use html2text to convert the plain HTML of each page into markdown content and split the page by markdown headings into multiple documents.

You can do this project in a Jupyter Notebook, or on a platform like Google Colab. Alternatively, you can create a new Python project in an IDE like Pycharm or VS Code. I recommend using a Jupyter Notebook for following along with this article.

The code in this article is also available for you to follow along (and run yourself) on Google Colab.

Getting Started

Let's first install the necessary dependencies for this project:

pip install bs4 html2text

Next, we'll define some custom request headers to spoof a web-browser client that we will use when making requests:

headers = {
    'User-Agent': 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.124 Safari/537.36',
    'Accept-Language': 'en-US,en;q=0.9',
}

Crawling through the Reference

Because each article we want to scrape is located within WebMD's Health & Diet Medical Reference, and the Reference itself is paginated, we need to first create a web-crawler program to identify each link we will need to scrape.

To do so, let's first make a get_links_from_page function that will retrieve all of the links to articles from a specific page within the Reference:

import requests
from bs4 import BeautifulSoup


def get_links_from_page(index):
  # Send a GET request to the page we want to crawl
  url = f"https://www.webmd.com/diet/medical-reference/default.htm?pg={index}"
  response = requests.get(url, headers=headers)

  # Parse the HTML content using BeautifulSoup
  soup = BeautifulSoup(response.content, 'html.parser')

  # Find the ul element with the links to articles
  ul_element = soup.find('section', class_='dynamic-index-feed').find('ul', class_='list')

  # Find all the anchors (a tags) within the ul element
  anchors = ul_element.find_all('a')

  # Extract the href attribute from each link
  links = [anchor['href'] for anchor in anchors]

  return links

Next, we'll create a get_all_links_from_reference function that will iterate through all 23 pages in the Reference and fetch all of the links to articles.

all_links = []

def get_all_links_from_reference():
  for index in range(1, 24):
    all_links.extend(get_links_from_page(index))

Once we run that, we now have all of the links in the WebMD Health & Diet Reference, and we can now move on to scraping the individual articles for their content.

Scraping and Processing Articles

As previously discussed, we will break up each article into multiple "documents" separated by headings within the article. Let's make a utility Document class to help us structure our code and keep track of the title and URL of the article, as well as the content of the document:

class Document:
  def __init__(self, title, url, content):
    self.title = title
    self.url = url
    self.content = content

We'll also write a brief function that utilizes requests and BeautifulSoup to scrape a given article via its URL:

import requests
from bs4 import BeautifulSoup


def scrape_webpage(url):
  response = requests.get(url, headers=headers)
  soup = BeautifulSoup(response.content, 'html.parser')
  return soup

We now want to begin the work on processing the HTML into documents. First, let's write a function that converts the webpage into markdown text:

from html2text import html2text


def webpage_to_markdown(soup):
  # Find the article body, either by `class_='article__body'` or `class_='article-body'`
  article_body = soup.find(class_='article__body')
  if article_body is None:
    article_body = soup.find(class_='article-body')

  # Extract the HTML content from the article body
  html_content = str(article_body)

  # Convert the HTML content into markdown
  markdown_content = html2texthtml2text(html_content, bodywidth=0)
  return markdown_content

For the sake of making the content more legible for ChatGPT, we'll make a function that strips links from the markdown content and replaces them with just the text of the link. We can do so using regular expressions, like so:

import re


def strip_links_from_markdown(markdown_content):
  # Make a RegEx pattern
  link_pattern = re.compile(r'\[(.*?)\]\((.*?)\)')

  # Find all matches in markdown_content
  matches = link_pattern.findall(markdown_content)

  for _match in matches:
    full_match = f'[{_match[0]}]({_match[1]})'

    # Replace the full link with just the text
    markdown_content = markdown_content.replace(full_match, _match[0])

  return markdown_content

Lastly, split the articles by markdown headings into multiple documents.

def split_markdown_by_headings(markdown_content):
  # Define the regular expression pattern to match H1 and H2 headings
  pattern = r'(#{1,2}.*)'

  # Split the Markdown text based on the headings
  sections = re.split(pattern, markdown_content)

  # Combine each heading with its corresponding text
  combined_sections = []
  for i in range(1, len(sections), 2):
    heading = sections[i].strip()  # Get the heading from sections[i]
    text = sections[i + 1].strip() if i + 1 < len(
        sections) else ''  # Get the text from sections[i + 1] if it exists, otherwise use an empty string
    combined_section = f"{heading}\n{text}"  # Combine the heading and text using a newline character
    combined_sections.append(combined_section)  # Add the combined section to the list

  if len(combined_sections) == 0:
    combined_sections = [markdown_content]

  return combined_sections

We now have all of the logic to both scrape and process articles from the Reference. We can put it together in a function, create_documents_from_webpage:

def create_documents_from_webpage(url):
  # Wrap function in a try-except block to handle any potential exceptions
  try:
    soup = scrape_webpage(url)

    # Extract the title from the article
    title = soup.find('h1').get_text().strip()

    # Convert the webpage HTML to markdown
    markdown_content = webpage_to_markdown(soup)

    # Strip links from the markdown content
    markdown_content = strip_links_from_markdown(markdown_content)

    # Split the article up headings
    contents_by_heading = split_markdown_by_headings(markdown_content)
    docs = []
    for content in contents_by_heading:
      docs.append(Document(title=title, url=url, content=content))
    return docs
  except:
    return []

With this function, we can provide any URL from the Reference, and it will generate a list of documents with content from each of the subheadings.

Generate Databank of Sources

Now that we have all of the logic required to scrape and process articles, we can move on to generating the databank of nutritional sources that will be utilized by the chatbot. To do so, we must iterate through each of the articles on of the pages in the Reference, and save all of the documents created.

We'll put together all of our previous work in the generate_databank function:

def generate_databank():
  docs = []

  # Get all of the links in the Reference
  all_links = get_all_links_from_reference()

  # Iterate through every link in the Reference
  for link in all_links:
    # Add all of the documents created from the article
    docs_from_article = create_documents_from_webpage(link)
    docs.extend(docs_from_article)

  return docs

Feel free to add additional debug comments, such as which link is currently being processed, how many links are left, how many documents were added, etc.

After running generate_databank, we now have a databank of nutrition sources!

Keep in mind that this may be a memory-intensive process, and depending on your machine, you may want to consider running this program in a hosted environment like Google Colab. I was able to run this program on my 2023 M2 Pro MacBook Pro, but results may vary by your specific setup.

Conclusion

Through following the steps in this article, we utilized real-world web-scraping techniques to gather and process information from the internet and create a databank of sources; this databank will be used to provide reliable information to our nutrition chatbot.

We used the BeautifulSoup library and the requests library to crawl through the WebMD Health & Diet Medical Reference, and wrote functions to convert the webpage into markdown text, strip links from the markdown content, and split the articles by markdown headings. Finally, we generated the databank of nutritional sources by iterating through all of the articles on pages in the Reference and saving all of the documents created.

In the next article in this series, we'll explore using sentence-transformers and FAISS to create a vector store index to connect the databank we created to an LLM like ChatGPT.

Configuring nodemon with TypeScript

Cole Gawin — Tue, 18 Jan 2022 05:26:44 +0000

Originally published on the LogRocket blog.

nodemon is a CLI for Node.js that makes JavaScript development much quicker by restarting an execution process when a file is updated. For example, if you have a project with an index.js file that you want to quickly test and iterate on, you can run nodemon index.js, and a new Node.js execution process will begin for index.js, restarting whenever a file in the project is updated. Simple, right?

Well, the simplicity offered by nodemon diminishes both as you introduce TypeScript into your project, and as the complexity of your project grows. But fear not! In this article, we’ll review three methods of configuring nodemon, each of which offers different features and functionalities that can meet the needs of your TypeScript project.

We will also review three nodemon alternatives with extra features and more customizability, if you are looking for alternatives to nodemon that will better fit your project's requirements. Since each option has its own pros and cons, we will discuss whether or not each option will suit the needs of our project, and if not, which option is a better choice.

Method 1: No-config workflow

As of v1.19.0, nodemon has built-in support for Typescript files with help from ts-node that requires no manual configuration. By default, nodemon uses the node CLI as an execution program for running JavaScript files; for TypeScript files, nodemon uses ts-node as the execution program instead.

ts-node is a TypeScript execution engine that compiles and runs TypeScript files. ts-node serves as drop-in replacement for the node CLI, so the same arguments can be passed to the ts-node CLI as the node CLI.

This method requires a version of nodemon ≥1.19.0 to be installed. In addition, ts-node must be installed in your project. Since both of these packages will likely only be used during development, they should be installed as devDependencies.

yarn add --dev nodemon ts-node

Once both of these dependencies are installed, you can pass a TypeScript file to nodemon as you would a JavaScript file.

npx nodemon ./main.ts

Advantages and disadvantages

This method is by far the most simple, as it requires minimal setup. It’s built into nodemon itself, so all that is required is installing the necessary packages.

However, this method falls short in terms of flexibility and customization. Many projects require more than just the default tsc TypeScript compiler that is used by ts-node, and still others will require more advanced configuration; if this scenario describes your needs, proceed to method two.

Method 2: Manual configuration

The built-in nodemon TypeScript runner provides a method to get up and running with minimal setup: manual configuration.

If your project requires more flexibility in how your files are executed, nodemon allows users to create a configuration file to meet a project's exact specifications. By using a custom configuration file, you can reap the maximum benefits of nodemon's flexibility and take advantage of all of its offered settings.

The specific setting we will be configuring is execMap, or execution map. This setting informs nodemon about which executables or commands to run for different file types. For now, we'll go over how to set up an execution map specifically for TypeScript files.

To create a configuration file, make a new file in your project's root directory named nodemon.json.

touch ./nodemon.json

In the nodemon.json file, create a new JSON object with an execMap property. The value of the execMap property should be an object.

{
    "execMap": {}
}

Inside the execMap object, create a new property for ts files. The value of this property should be whatever command you want to run when executing your TypeScript files. For example, you can set it to ts-node, or any other execution script or command.

{
    "execMap": {
        "ts": "ts-node"
    }
}

Voilà, nodemon is now configured to run a custom command for TypeScript files. When you call nodemon with a TypeScript file (i.e., nodemon index.ts), nodemon will find the command in the execMap that correlates to .ts files and then run that command, passing the file as the final argument (i.e. ts-node index.ts).

Bonus tip: if you want to pass the filepath elsewhere in the command (i.e., not as the final argument), type {{pwd}} where the filepath should be placed in the command. For example, if your execMap command for .js files is node {{pwd}} && echo "Hello world", then calling nodemon index.js will run node index.js && echo "Hello world".

Advantages and disadvantages

Using a custom nodemon configuration file opens up a lot of flexibility that many projects require. There are a lot of settings that you can configure, as explained by the nodemon documentation.

To that extent, this method should only be used in cases where the first method will not meet your project's requirements. If your project only needs your TypeScript files to be compiled and ran, then the inbuilt nodemon TypeScript support with ts-node (method one) will likely be the best option for your project.

If your project happens to need even more customization, consider method three.

Method 3: Custom execution command

nodemon shines as a tool to help run and restart the execution of a single file when any file in a project is updated. However, not all projects have a single entry point; that is, many modern projects require the use of an outside tool to bootstrap or execute your project.

Whereas methods one and two offer ways to execute a single file, this method will offer a way to execute a single command, thereby offering the most flexibility of these methods.

In your package.json file, create a start script. This will serve as the command that will be run and restarted by nodemon when a file changes.

To execute this command with nodemon, run:

nodemon --exec "yarn start"
# or
nodemon --exec "npm run start"

This passes the start script as the executable command to run for your project by nodemon.

Bonus tip: you can make the full nodemon command (i.e., nodemon --exec "yarn start") a dev script, such that calling yarn dev will run nodemon with your custom execuction command.

Advantages and disadvantages

Although this method offers the most flexibility in terms of what can be run, it does negate nodemon's most notable feature: (re)running the execution of a single file when a file in the project is updated.

Before choosing this method, consider whether methods one or two are better suited for your project's needs.

What are some alternatives to nodemon?

nodemon is certainly a powerful tool for rapid development with Node.js. However, there are also numerous alternatives that may be better suited for your project.

In the next part of this post, we’ll consider three alternatives to nodemon: ts-node-dev, pm2, and a DIY file watcher built with Parcel.

Alternative 1: ts-node-dev

In the first method, we discussed how nodemon uses ts-node to compile and run TypeScript files. [ts-node-dev](https://github.com/wclr/ts-node-dev) combines the file-watching capabilities of nodemon with the TypeScript support from ts-node into a nodemon-like service that is specifically tailored to TypeScript.

ts-node-dev interfaces directly with the TypeScript execution engine and compilation process to offer a more efficient system than nodemon for TypeScript files. ts-node-dev only reloads when changes are made to files that are a dependency of (i.e., imported by) the entry file. Additionally, ts-node-dev shares a singular compilation process between restarts to maximize efficiency and make restarts quicker.

To use ts-node-dev, first install it as a devDependency:

 yarn add --dev ts-node-dev

Then, to run your file and restart on file changes, run:

ts-node-dev --respawn index.ts
# or
tsnd --respawn index.ts

Replace index.ts with the entry file to your project.

Advantages and disadvantages

ts-node-dev is a great option for fast TypeScript development because it is more efficient than nodemon, and is made specifically for TypeScript.

However, while it does offer some level of configuration, ts-node-dev is arguably much less customizable than nodemon. It also does not restart on changes to static assets, which can be useful when serving images on a web server. Make sure to consider these downsides before choosing ts-node-dev for your project.

Alternative 2: `pm2`

[pm2](https://github.com/Unitech/pm2) is a battle-tested and production-ready process manager for Node.js programs that is loaded with numerous features and configuration options. It is used to manage multiple Node.js applications and processes, and comes with a load balancer to manage heavy applications with high amounts of queries.

pm2 supports hot reloading, application monitoring, and detailed process management. In addition to all of these features, pm2 offers an auto-restart functionality that will restart your program when a file is changed.

To get started with pm2, install it globally on your system.

npm install pm2 -g

Next, we will have to do a little bit of configuration. Create a file named ecosystem.config.json, and enter the following contents:

module.exports = {
    apps: [
        {
            name: "TSServer",
            script: "ts-node",
            args: "index.ts", // replace this with your project's entry file
        }
    ]
}

This will create a new app called "TSServer" that will run ts-node index.ts. Finally, run:

pm2 start ecosystem.config.js --only TSServer --watch

This will run the TSServer app and restart on file changes with the watch argument. A fancy table with information about your application should print to the terminal, and a column titled Watching should read Enabled for your application. This application will now run in the background until you call pm2 stop TSServer.

Advantages and disadvantages

As previously stated, pm2 is jam-packed with exciting features that are incredibly useful for large production applications. However, for this reason, pm2 may very well be overkill for your project.

If you are just looking for a simple way to restart TypeScript projects, this method will likely not be the best choice for your project and you should consider other alternatives or nodemon methods.

Alternative 3: DIY file watcher with Parcel

Sometimes, the best way to do something is it do it entirely by yourself from scratch.

As we have seen in all of the previous methods and alternative, there is always a potential negative or drawback to using one option instead of another. You can avoid these limitations by creating a file watcher from scratch, and even learn something along the way!

For this DIY file watcher, we will take advantage of the capabilities provided by the Parcel file bundler, which can be utilized for developing web apps or Node.js libraries.

Parcel exposes a JavaScript API to watch events in the bundling process. Each time a file is updated, the bundling process for our TypeScript project restarts. When the bundling process completes, we will spawn a child process that executes the bundled and compiled JavaScript file.
Here is an example of my DIY file watcher built with Parcel:

// make sure you have @parcel/core and @parcel/config-default
// installed as devDependencies

import {Parcel} from '@parcel/core';
import {spawn, ChildProcessWithoutNullStreams} from 'child_process';

let bundler = new Parcel({
    entries: 'src/index.ts',
    defaultConfig: '@parcel/config-default',
    defaultTargetOptions: { distDir: `${process.cwd()}/dist` },
});

async function main() {
    let cp: ChildProcessWithoutNullStreams;

    await bundler.watch(() => {
        cp?.kill()
        cp = spawn("node",[`${process.cwd()}/dist/index.js`])
        cp.stderr.on('data', (data) => {
            console.log(`stderr: ${data}`);
        })
        cp.stdout.on('data', (data) => {
            console.log(`stdout: ${data}`);
        });
    });
}

main()

Another benefit of this method is that you can actually write your entire file watcher in TypeScript! To run your file watcher, simply run your file with ts-node.

ts-node runner.ts

Advantages and disadvantages

This method, by far, offers the most customizability, since you are creating the file watching process yourself. You can spawn a different child process if needed, or spawn multiple, and you can run any other JavaScript/TypeScript code as needed when a file is updated.

However, as this is a DIY solution, it is your own responsibility to upkeep and maintain the runner, whereas this is done for you by teams of knowledgeable open source developers for all of the other options provided in this article. As long as you know what you are doing, however, this alternative option should certainly not be overlooked!

Conclusion

There are numerous ways in which nodemon can be configured to fit your project’s needs and requirements. However, if none of those methods work for you, there are also ample alternatives that may offer different advantages over nodemon for your project. I hope you have found a method in this article that will suit your specific use case.

Why the New Firebase Web v9 Modular SDK is a Game-Changer

Cole Gawin — Sat, 07 Aug 2021 01:34:00 +0000

Firebase is one of the most popular Backend-as-a-Service options for a modern tech stack. In addition to offering a NoSQL database solution called Firestore, the Firebase platform provides solutions for authentication, file storage, hosting, and analytics. The Firebase SDK is available for many platforms, including mobile, Unity, Java, C++, and the web.

One of the major shortcomings of Firebase on the web, however, was its sheer size. According to BundlePhobia, a tool used to determine the size of NPM packages, the firebase Web Javascript package weighs in at 235.5kB when minified & g-zipped. This can result in an additional 0.59s of loading time for some users with slower network connections. For comparison, lodash is another notoriously heavy NPM package yet it only weighs 24.5kB when minified & g-zipped: a 10th of the size of Firebase.

This is a known issue with the Firebase Web Javascript SDK, and has turned many developers away from the product. Especially for developers building products for end-users who may not have access to a fast internet connection, loading a package as large as Firebase was simply not an option for them.

Thankfully, the Firebase team has been hard at work recreating the Firebase Web SDK from the group up. On July 27th, 2021, the official Firebase Blog account announced the pre-release of the a new, modular JavaScript SDK that can be “up to 80% smaller!”

Firebase Web v9 will completely change how web developers use Firebase. With the introduction of a fully overhauled, modular, functional programming style and the inclusion of a Firestore “lite” library, web apps powered by Firebase Web v9 will run faster, loader quicker, and dramatically enhance both the user and developer experience.

With all that said, let’s take a look at some of the radical changes introduced in this new modular Firebase Web SDK.

Side-effect-free imports

Previously, the Firebase Javascript SDK incorporated what is known as side-effect imports. In simplest terms, a side-effect occurs when a function modifies state outside of its provided scope. For example, if function a were to modify global variable x, then function a would produce a side-effect. Side-effect imports effect the state, logic, or functionality of your program without calling any methods or referencing any variables that are exported from the package. The mere presence of the package in your program (via an import statement or require call) can affect the functionality of your program.

The old Firebase Web SDK heavily relied on side-effect imports. For each additional Firebase functionality you wanted to include in your app (authentication, Firestore, cloud storage, analytics, etc.), you had to import an additional package like so:

// main firebase app import
import app from "firebase/app";

// SIDE EFFECT PACKAGES
import "firebase/auth";
import "firebase/firestore";
import "firebase/storage";

If you have experience with working with the old Firebase Web SDK, you might have incorporated lazy-loading for importing the Firebase packages. This solution would decrease the initial load size and time of your web app, but users would still be forced to wait for all of these packages to load before the app became fully functional.

Firebase Web v9 changes all of this. The concept of side-effect packages is non-existent in the new Firebase Web SDK, and all of the packages are completely tree-shakable. That means that only the parts of Firebase that are needed by your app will be imported on the client. This drastically reduces the final bundle size of your app and will lead to much faster loading times!

Native Javascript ES modules

In the new Firebase Web SDK, each individual functionality of Firebase that your app requires is imported separately thanks to the introduction of modular packages. Because the new SDK is built into native Javascript ES modules, you can directly import only the features that your program needs: nothing more, nothing less. For example, let’s say you want to initialize your Firebase app and then watch for auth changes:

// imports with ES modules
import { initializeApp } from "firebase/app";
import { getAuth, onAuthStateChanged } from "firebase/auth";

// initialize firebase app
initializeApp(firebaseConfig);

// watch for auth changes
const auth = getAuth();
onAuthStateChanged(auth, (user) => {
 // deal with authentication changes 
});

The introduction of modular packages in turn results in the introduction of a more functional programming style when working with the Firebase Web SDK.

Functional programming style

If you have ever worked with functional programming languages or libraries, you will be familiar with the advantages that functional programming grants you as a developer. Programs that adhere to the functional programming style often have the advantages of being very intuitive and incredibly test-friendly. Although the old Firebase Web SDK was hardly difficult to comprehend, the new Firebase Web SDK is no less intuitive or beginner-friendly.

To demonstrate the functional programming style introduced by the new modular Firebase packages, let’s look at an example of updating a document in Firestore.

import { getStorage, ref, uploadBytes } from "firebase/storage";


// first, get a reference to the storage bucket for our app
const storage = getStorage();

// then, make a reference to the file
const usersCollection = ref(storage, "files/example.png");

// finally, upload the file to the reference
uploadBytes(usersCollection, file);

As you can see, there is a lot of function nesting present in this code example—the result of one function is passed as the argument to another function, whose result is passed to the argument of another function, and so on. This is in stark contrast to the method chaining approach used by the old Firebase Web SDK.

To summarize, the code used with the new Firebase SDK functional languages like F# or Scala (or functional libraries like Ramda and RxJS), whereas the code used with the old Firebase Web SDK resembles that of Java or C++.

Firestore Lite

Firestore is an incredibly powerful and useful database service. It provides a lot of features, many of which aren’t actually utilized in all web apps that use Firestore. Many developers simply use Firestore as an easy-to-implement NoSQL database that handles many of the complexities of operating a database on both the client- and server-side. To that extent, a lot of web apps don’t need the realtime updates capability of Firestore; they just need access to one-time document and collection queries.

The Firebase team recognizes this valid use case, and has addressed it with the introduction of a new library: Firestore Lite. The Firestore Lite library is up to 80% lighter than the old Firestore v8 library. All of the features of Firestore that you have grown to love and take full advantage of, minus realtime updates, are available in the Firestore Lite library. This is a big win for the Firebase Web community because your apps can now be more performant and less bloated with unused code!

Compatibility

The new Firebase Web v9 SDK makes it easy to progressively upgrade from the v8 SDK. The firebase package provides a compat library to make migrating from v8 to v9 easy and incremental. For all of the places in your codebase where you aren't ready to make the full switch to Firebase Web v9, you can take advantage of the compat library and incrementally upgrade parts of your codebase until you no longer need to use the compat library functionality.

The main drawback for this is that you won’t experience all of the bloat and load time reducing features of the new v9 SDK when using the compat library. The compat library still relies on side-effect imports, so you will have to deal with those like you would with the Firebase Web v8 SDK.

Conclusion

If you have ever worked with Firebase on the web before, the future of Firebase should really excite you. The introduction of this new modular Firebase Web v9 SDK changes everything in terms of developing with Firebase on the web. From making your apps less bloated to improving the experiences of both the developer and the end-user, the new Firebase Web v9 modular SDK removes one of the biggest downsides to using Firebase, and will revolutionize the future of Firebase-powered web apps!

9 Technologies to Check Out for Your Next.js & React Project

Cole Gawin — Thu, 24 Jun 2021 15:57:08 +0000

Libraries, frameworks, and services that will take your project to the next level.

Next.js is a great technology by itself, as it offers many great features that makes creating fast and versatile React apps and websites easily. However, the beauty of the Javascript ecosystem is that there is an abundance of hidden (and not-so-hidden) gems that will enhance your experience as a developer and the experience for the end user. In this article, I will present 9 technologies that can enhance the frontend, backend, and full-stack development and experience for your next project with Next.js.

Frontend

goober: a smaller option for CSS-in-JS

The React ecosystem has become bloated with different styling options, with arguably the most popular being CSS Modules, emotion, and styled-components. However, a lesser-known competitor to these options has the same core capabilities as other CSS-in-JS libraries, with the differentiating feature being its size: compared to 11kB and 12kB for emotion and styled-components respectively, goober comes in at less than 1kB! This will drastically reduce the bundle size of your web app and will ultimately lead to faster loading times and a better user experience all around.

Check out the project at https://github.com/cristianbote/goober.

Preact: a fast, tiny alternative to React

Preact offers the same advantages as the aforementioned library: it offers the same core capabilities as its more popular competitor, with an immensely smaller footprint. Together, React and React-DOM have a bundle size of 42.2kB (!), while Preact is about a 10th of a size at ~4kB. Preact offers direct compatibility with React and React-DOM, so you can easibly substitute React for Preact in your Next.js app.

Learn more about Preact at https://preactjs.com.

Chakra-UI: predesigned and highly-customizable UI components

Pre-made CSS frameworks and component libraries are growing increasingly popular in the world of web and mobile design, and rightfully so. You no longer have to hire a designer to create visually-appealing and attention-grabbing apps and websites. There are many component libraries available for React that come with pre-designed components and styles with which you can design and code your app, including Ant Design, Evergreen, and React-Bootstrap built on top of the bootstrap.css library. However, Chakra-UI is making a name for itself amongst all of the other component libraries because of its infinite modularity and customizability. Its components take inspiration from the likes of TailwindCSS and TailwindUI, and you can customize and tweak them to match your envisioned design.

See documentation and examples at https://chakra-ui.com.

Backend

Nest.js: a versatile web framework for Node.js

By itself, Next.js offers great options for writing lambda functions to power the backend of your application. However, the default offerings can be limiting, especially if your backend involves more complex logic than what is allowed by straightforward lambda functions. Nest.js is a popular framework made to be used for building complex server-side applications, and can be integrated into Next.js to combine the powers of both. Nest.js is inspired by the modularity of Angular, and they offer great documentation that helps with overcome the learning curve that comes with any new framework.

Visit their official website at https://nestjs.com. Bonus: for an example of how to integrate Nest.js into Next.js, follow Simon Knott’s great tutorial at https://simonknott.de/articles/Integrating-NextJS-with-NestJS.html.

Prisma: future-proof ORM and database client

The features offered by Prisma dramatically improve the developer experience of working with SQL databases. Prisma offers a schema language that allows you to easily define models that will be represented in your database, as well as the Prisma database client. Because the schema you create integrates with the Prisma Client, you can pragmatically make type-safe queries and mutations. Additionally, Prisma offers a database migration service that will automatically generate schemas for your database based on pre-existing data, and a database browser to view and manipulate your database.

Learn more about the features offered by Prisma at https://www.prisma.io.

Supabase: an open-source alternative to Firebase

Firebase is one of the most popular options for backend-as-a-service because of its great feature set and its large community and ecosystem. However, by using Firebase or its main competitor AWS Amplify, you can unknowingly fall victim to vendor lock-in, which will restrict your ability to grow and utilize other services later on. Supabase, on the other hand, is a completely open-source alternative to Firebase. The advantages of Supabase being open-source software is that it is constantly audited by the community for security flaws and vulnerabilities, in addition to not being locked into the ecosystem of Google Cloud or AWS.

Check out the Supabase project at https://supabase.io.

Full-stack

Blitz.js: a full-stack React framework built on-top of Next.js

As previously discussed, the options provided by Next.js in terms of backend development are pretty limited. Nest.js can certainly solve this problem solely on the server-side, but if you are looking for a more comprehensive solution that integrates both the frontend and backend, consider Blitz.js. As described by the official project website, “Blitz is a batteries-included framework that’s inspired by Ruby on Rails, is built on Next.js, and features a “Zero-API” data layer abstraction that eliminates the need for REST/GraphQL.” The purpose of Blitz.js was to be able to seamlessly integrate complex backend logic into your frontend React app. Blitz.js is a relatively opinionated framework, which means that much of the file and folder structure of your app is dictated by the requirements of the framework; that being said, the structure that Blitz.js incorporates will make your code organized and easy to understand.

Watch introductory videos and read about the features of Blitz.js at https://blitzjs.com.

SWR: real-time updates without sacrificing UX

As the famous quote by Phil Karlton goes, “There are only two hard things in Computer Science: cache invalidation and naming things.” Stale-while-revalidate, or SWR for short, attempts to solve the first of those two challenges. This term originated in HTTP RFC 5861, which describes a strategy to manage cache invalidation and revalidation. The React SWR library, developed by the team behind Next.js, describes the advantages of using SWR: “With SWR, components will get a stream of data updates constantly and automatically. And the UI will be always fast and reactive.” Using SWR in your Next.js app, you can implement a real-time experience to your app with automatic updates.

Learn more about SWR and the React SWR library at https://github.com/vercel/swr.

GraphQL + Apollo: improve DX and UX

By now, you have probably heard of the advantages offered by implementing GraphQL into your backend API. GraphQL allows you to easily query and mutate data by calling a single endpoint on your API. With GraphQL, you only receive the data you need, reducing the size of the HTTP response sent from your API, thereby making your app quicker. Using Next.js API routes in addition to apollo-server-micro, you can easily implement a GraphQL backend to your Next.js app that integrates with Apollo client.

View the Next.js api-routes-graphql example at https://github.com/vercel/next.js/tree/canary/examples/api-routes-graphql

Conclusion

Each of these technologies can help to improve a different aspect of your Next.js app or website, and hopefully you found some of interest and will consider using them in your next project! If you have any other suggestions, please feel free to leave them in the comments of this article.

Visualizing Algorithm Runtimes in Python

Cole Gawin — Mon, 31 May 2021 16:16:18 +0000

This article will cover how you can use visualization libraries and software to determine runtime complexities for different algorithms. We will cover the basic usage of matplotlib for visualization of 2d plots and numpy for calculating lines of best fit, and then go over how these libraries can be used to determine their runtime complexity either through "guesstimation" or by comparing the plots of their runtimes to that of known functions (i.e. y=x, y=2^n).

If you are interested in downloading the code featured in this article, please visit this repository on my GitHub (chroline/visualizingRuntimes).

What is runtime complexity?

Runtime complexity, more specifically runtime complexity analysis, is a measurement of how “fast” an algorithm can run as the amount of operations it requires increases. Before we dive into visualizing the runtimes of different algorithms, let’s look at a couple of basic examples to explain the concept.

Take the following add function. It accepts two parameters, a and b, and performs addition on a and b.



def add(a, b):
    return a + b

When given any two parameters (1 and 2, 2 and 3, 29347 and 93648), the amount of operations does not change. Therefore, we say the algorithm runs in constant, or O(1), time.

However, now consider the following permutations function. It accepts one main parameter, string, and prints all of the permutations of that string.



def permutations(string, step = 0):
    if step == len(string):
        print "".join(string)
     for i in range(step, len(string)):
        string_copy = [c for c in string]
        string_copy[step], string_copy[i] =string_copy[i], string_copy[step]
        permutations(string_copy, step + 1)

As you could imagine, this function would take much longer than the previous add function; in fact, this function would run in what is called factorial time, represented as O(n!). That is because as the amount of characters in string increases, the amount of operations required to find all the permutations increases factorially.

When comparing the runtimes of two functions visually, you would notice a stark contrast in the graphs they produce. For the add function, you would observe a flat line, as the input of the function does not affect the amount of operations required by the function. However, for the permutations function, you would observe a line that drastically spikes upwards (the slope of the line would approach infinity) because the amount of operations increases factorially as the size of the input increases.

Now that we have covered the basics of runtime complexity analysis, we can begin the process of writing code to visualize the runtimes of different algorithms.

Initialization

Before running any visualizations, we must first import the necessary libraries and initialize them.

matplotlib is a library that will create and display the graphs
numpy is a library that consists of numerous mathematical utility functions
timeit is a library that we will use to time how long each call to the algorithm takes
math is the basic Python math library
random is the basic Python randomization library



import matplotlib.pyplot as plt
import numpy as np
import timeit
import math
import random

plt.rcParams['figure.figsize'] = [10, 6] # set size of plot

Demos

Below are some code segments that demonstrate how to use matplotlib and numpy.

`sum` function

The Python sum function calculates the sum of all elements of a provided Iterable. This function implements an algorithm with a O(n) runtime complexity.

To test this, we will use the linspace method from the numpy library to generate an iterable with 50 evenly-spaced values ranging from 10 to 10,000. The graph, although not a perfectly straight plot, illustrates this.



ns = np.linspace(10, 10_000, 50, dtype=int)
ts = [timeit.timeit('sum(range({}))'.format(n), number=100)
      for n in ns]

plt.plot(ns, ts, 'or')

We can add a line of best fit (using a 4th-degree function) to further exemplify this. The graph will never be a perfectly straight-line, but it should come close.



degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, ts,'or')
plt.plot(ns, [p(n)for nin ns],'-b')

List Indexing

Retrieving an item from a list (list indexing) runs with O(1) runtime complexity, which means that the amount of items in the list does not affect how long the algorithm takes to run. How is this represented in a graph?



lst = list(range(1_000_000))
ns = np.linspace(0, len(lst), 1000, endpoint=False, dtype=int)
ts = [timeit.timeit('_ = lst[{}]'.format(n),
                    globals=globals(),
                    number=10000)
for nin ns]

plt.plot(ns, ts,'or')

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n)for nin ns],'-b')

Algorithms

Now we will look at the graphs produced by the following algorithms:

linear search
binary search
insertion sort

Linear Search

Linear search has a runtime complexity of O(n), which will be represented by an approximately straight line.

Red plots demonstrate searching for an element in a shuffled, blue plots demonstrate searching for an element that is not present in the list.

The line of best fit for the red plots will generally be lesser than that of the blue plots because searching for an element that is not present in the list requires iterating through the entire list.



## searches for an item in a list
def contains(lst, x):
    for y in lst:
        if x == y: return True
    return False

ns = np.linspace(10, 10_000, 100, dtype=int)

# red plots
ts = [timeit.timeit('contains(lst, 0)', 
                    setup='lst=list(range({})); random.shuffle(lst)'.format(n),
                    globals=globals(),
                    number=100)
      for n in ns]
plt.plot(ns, ts, 'or')

# line of best fit for red plots
degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-r')

# blue plots
ts = [timeit.timeit('contains(lst, -1)', 
                    setup='lst=list(range({}))'.format(n),
                    globals=globals(),
                    number=100)
      for n in ns]
plt.plot(ns, ts, 'ob')

# line of best fit for blue plots
degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-b')

Binary Search

Binary search runs with O(log n) runtime complexity.



# searches for an item in a list using linear search
def contains(lst, x):
    lo = 0
    hi = len(lst)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if x < lst[mid]:
            hi = mid - 1
        elif x > lst[mid]:
            lo = mid + 1
        else:
            return True
    else:
        return False

ns = np.linspace(10, 10_000, 100, dtype=int)
ts = [timeit.timeit('contains(lst, 0)', 
                    setup='lst=list(range({}))'.format(n),
                    globals=globals(),
                    number=1000)
      for n in ns]

plt.plot(ns, ts, 'or')

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-b')

Above is what the graph should look like in a near-perfect simulation. As you can see, there are some some outliers, and in a perfect simulation the line of best fit would be identical to a logarithmic function.

Insertion Sort

What runtime complexity does insertion sort have? We can use the plots of its runtime and compare those plots against the graphs of known runtimes to determine which is the closest match.



def insertion_sort(lst):
    for i in range(1, len(lst)):
        for j in range(i, 0, -1):
            if lst[j-1] > lst[j]:
                lst[j-1], lst[j] = lst[j], lst[j-1]
            else:
                break

# 15 values
ns = np.linspace(100, 2000, 15, dtype=int)
ts = [timeit.timeit('insertion_sort(lst)',
                    setup='lst=list(range({})); random.shuffle(lst)'.format(n),
                    globals=globals(),
                    number=1)
         for n in ns]
plt.plot(ns, ts, 'or');

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-r')

Now, we can compare that graph with graphs of different runtimes to ultimately determine which is most similar and which runtime complexity insertion sort has.

Red plots represent O(log n), blue plots represent O(n^2), green plots represent O(2^n).



# y = log x
# vertically stretched 1000x
ns = range(1, 100)
ts = [math.log(n, 2) * 1000 for n in ns]
plt.plot(ns, ts, 'or');

# y = x^2
ns = range(1, 100)
ts = [(n*n) for n in ns]
plt.plot(ns, ts, 'ob');


# y = 2^x
# vertically stretched 20x
# horizontally compressed 1x
ns = range(1, 10)
ts = [math.pow(2, n)*20 for n in ns]
plt.plot(ns, ts, 'og');

Based on these graphs, it is safe to assume that insertion sort runs in O(n^2) time.

Mystery function runtime analysis

Can we use visualization of the runtimes of mystery functions to guesstimate their runtime complexities?

Mystery function #1



def f(l: list, val): # l is a python list with n items
  d = {}
  for i in range(len(l)):
    d[l[i]] = i
  return d[val]

ns = range(5, 2000)
ts = [timeit.timeit('f(lst, {})'.format(n-1),
                    setup='lst=list(range({})); random.shuffle(lst)'.format(n),
                    globals=globals(),
                    number=1)
         for n in ns]
plt.plot(ns, ts, 'or');

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-b')

Without even comparing this graph to the graphs of the possible runtimes, we can already safely assume that this function operates in O(n) runtime.

Mystery function #2



def g(l): # l is a python list of integers of length n
  pairs = [ (i,j) for i in range(len(l)) for j in range(len(l)) if i < j ]
  result = []
  for (i,j) in pairs:
    if l[i] == l[j]:
      result.append((i,j))
  return result

ns = range(5, 200)
ts = [timeit.timeit('g(lst)',
                    setup='lst=list(range({}))'.format(n),
                    globals=globals(),
                    number=1)
         for n in ns]
plt.plot(ns, ts, 'or')

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-b')

This graph looks very similar to the one for insertion sort, so we can determine that this function has a runtime complexity of O(n^2).

Mystery function #3



def h(n):
   if n <= 1:
       return n
   else:
       return h(n-1) + h(n-2)

ns = range(5, 30)
ts = [timeit.timeit('h({})'.format(n),
                    globals=globals(),
                    number=1)
         for n in ns]
plt.plot(ns, ts, 'or')

This function is more ambiguous than the previous two. It is evident that its runtime must be greater than O(n) as the slope increases as n increases. Let's consider the graphs of runtimes O(n^2) in red and O(2^n) in blue.



# y = n^2
# vertically stretched 20x
ns = range(5, 30)
ts = [n*n*20000 for n in ns]
plt.plot(ns, ts, 'or')

# y = 2^n
# vertically compressed 50x
ns = range(5, 30)
ts = [math.pow(2, n)/50 for n in ns]
plt.plot(ns, ts, 'ob')

The graph of the runtime of mystery function #3 more closely resembles the blue plots, so therefore the runtime complexity of mystery function #3 is O(2^n).

Conclusion

Using these visualization libraries, we are able to determine the runtime complexities of functions and algorithms by comparing them to plots/graphs of known runtimes (i.e. comparing plots of insertion sort runtime against y=n^2). In addition to determining runtime complexities, this methodology can be used to compare the speeds of different algorithms against each other. With only a few lines of code, you can quickly see the speed at which your chosen algorithms will run with large sets of data!

DEV Community: Cole Gawin

Leveraging Vector Embeddings and Similarity Search to Supplement ChatGPT’s Training Data

Getting Started

Generate Vector Embeddings

Saving our FAISS index

Experimenting with our Vector Index

Similarity Threshold

Conclusion

Web-Scraping Techniques to Source Reliable Information for ChatGPT

Getting Started

Crawling through the Reference

Scraping and Processing Articles

Generate Databank of Sources

Conclusion

Configuring nodemon with TypeScript

Method 1: No-config workflow

Advantages and disadvantages

Method 2: Manual configuration

Advantages and disadvantages

Method 3: Custom execution command

Advantages and disadvantages

What are some alternatives to nodemon?

Alternative 1: ts-node-dev

Advantages and disadvantages

Alternative 2: pm2

Advantages and disadvantages

Alternative 3: DIY file watcher with Parcel

Advantages and disadvantages

Conclusion

Why the New Firebase Web v9 Modular SDK is a Game-Changer

Side-effect-free imports

Native Javascript ES modules

Functional programming style

Firestore Lite

Compatibility

Conclusion

9 Technologies to Check Out for Your Next.js & React Project

Frontend

goober: a smaller option for CSS-in-JS

Preact: a fast, tiny alternative to React

Chakra-UI: predesigned and highly-customizable UI components

Backend

Nest.js: a versatile web framework for Node.js

Prisma: future-proof ORM and database client

Supabase: an open-source alternative to Firebase

Full-stack

Blitz.js: a full-stack React framework built on-top of Next.js

SWR: real-time updates without sacrificing UX

GraphQL + Apollo: improve DX and UX

Conclusion

Visualizing Algorithm Runtimes in Python

What is runtime complexity?

Initialization

Demos

sum function

List Indexing

Algorithms

Linear Search

Binary Search

Insertion Sort

Mystery function runtime analysis

Mystery function #1

Mystery function #2

Mystery function #3

Conclusion

Resources

Alternative 2: `pm2`

`sum` function