DEV Community: Ademar Tutor

Observability with OpenTelemetry, Jaeger and Rails

Ademar Tutor — Thu, 22 Feb 2024 15:53:48 +0000

In a traditional monolithic architecture, the application's behavior is relatively straightforward because all components reside within a single process. You can easily trace requests from their entry to their exit points.

However, in a microservices architecture, a single transaction or request might pass through many services hosted on different machines or across different data centers. This dispersion makes it hard to "observe."

Does it apply to a Rails monolith?

Yes, it does!

Let's say you are working on an e-commerce application. You are fixing a production bug for the checkout workflow on this application.

The workflow includes the following actions:

Charging credit cards via a 3rd party payment gateway (Stripe, Braintree and etc.)
Sending a customer an email notification (Sendgrid, Twilio)
Send updates to your order management system responsible for handling your inventory.

The bug only arises during peak hours.

This would only mean that one or two of the processes took too long to respond and caused the entire workflow to fail.

You do not monitor your Rails application's internal components, but you must also monitor the interactions with these external services.

This is where OpenTelemetry comes in.

What is OpenTelemetry?

OpenTelemetry is an open-source observability framework that helps you gather metrics, traces, and logs.

Why do I need that? I already have New Relic, Skylight, and AppSignal.

OpenTelemetry is vendor-neutral. It doesn't lock you into a specific observability platform. You can switch to another vendor. Plus, OpenTelemetry is incubated by CNCF and is supported by industry leaders. This means it's here to stay!

Would OpenTelemetry replace New Relic, Skylight, and AppSignal?

OpenTelemetry specifies how data should be structured, collected, and sent over the network, but it doesn't provide a backend system to store, visualize, or analyze this data.

You can send this data to New Relic or AppSignal to store, visualize, or analyze.

But you can set up open-source solutions to view your data. This is where Jaeger comes in.

Jaeger maps the flow of requests and data as they traverse a distributed system. These requests may make calls to multiple services, which may introduce their own delays or errors.
https://www.jaegertracing.io/

How do you set up OpenTelemetry + Jaeger with a Ruby on Rails application?

These are the step-by-step process for integrating OpenTelemetry and Jaeger with your Ruby on Rails app.

1) Install the necessary gems

gem "opentelemetry-sdk"
gem "opentelemetry-exporter-otlp"
gem "opentelemetry-instrumentation-all"

2) Run Rails app and set the tracer exporter to console.

env OTEL_TRACES_EXPORTER=console rails server

Now, see if you can see the logs on the server. The logs should show something like this:

3) You can then set up a Jaeger backend to pass data. You can do that by running this image on your terminal:

docker run -d --name jaeger \
  -e COLLECTOR_ZIPKIN_HOST_PORT=:9411 \
  -p 5775:5775/udp \
  -p 6831:6831/udp \
  -p 6832:6832/udp \
  -p 5778:5778 \
  -p 16686:16686 \
  -p 14268:14268 \
  -p 14250:14250 \
  -p 9411:9411 \
  jaegertracing/all-in-one:latest

You will see the Jaeger on your docker desktop. You need to make sure the container is running.

Once it's running you should be able to access the Jaeger UI on your browser via http://localhost:16686/search

By default, traces are sent to an OTLP endpoint listening on localhost:4318. Your rails app should be set up automatically. However, if you need to update the endpoint, you can set it up manually by adding an ENV variable.

env OTEL_EXPORTER_OTLP_ENDPOINT="http://localhost:4318" rails server

You should be able to see the request on Jaeger UI:

Originally posted on: https://blog.ademartutor.com/p/observability-with-opentelemetry

Hello there!

Do you have a startup idea or an exciting project you're passionate about? I'd love to bring your vision to life!

I'm a software developer with 13 years of experience in building apps for startups, I specialize in Rails + Hotwire/React.

Whether you're looking to innovate, grow your business, or bring a creative idea to the forefront, I'm here to provide tailored solutions that meet your unique needs.

Let's collaborate to make something amazing!

Sincerely,
Ademar Tutor
hey@ademartutor.com

Callbacks are evil! 😈

Ademar Tutor — Thu, 22 Feb 2024 14:47:00 +0000

I’m working on a super secret app to revolutionize service field businesses 😜. Yesterday, the codebase had the opportunity to be viewed by eyes from the outside world for the first time and got feedback.

One of the things that stood out was the code related to converting Requests to Quotes. This workflow:

This particular code:

This involved the callback after_create!

I know, I know. Callbacks are evil!

Well, my lame excuse at the time of development is I could not find the correct language for the conversion process when developing the ubiquitous language.

Based on the stakeholders, whenever they need the quote to be produced, they just say to the employee: “Palihug ko pa.quote ani dong/dai. “

This can be loosely translated as: “Hey [name], can you please create a quote for this customer’s request?”

At that time of development, I could not find the right words for it. Based on what I was hearing from the stakeholders, they just said to create a quote.

So, I opted for the easiest solution available, callbacks!

Why are callbacks bad?

It is probably not that concerning in this particular case since the workflow is pretty simple.

However, I’ve been burned by this before! When I was working on an e-commerce application, we used a after_save callback that sent app notifications to listing owners when their listings were updated. When we ran a script that was intended to update silently thousands of listings on a Sunday evening. Long story short, it was not a very silent Sunday 😅.

So, how do we move away from callbacks?

Modeling/developing/writing a better ubiquitous language for the domain you are working on helps you write better code.

In my case, I could not find the right technical words while conversing with the stakeholders.

However, now that I started developing the user interface, it seems it’s pretty straightforward:

So, what does the change look like in the code?

Step 1: Create a PORO to handle the business logic

Things to note on the code above:

I created a PORO (Plain Old Ruby Object) for the Request to Quote Conversion business logic.
Later, if we want to send email or mobile notifications to admins or employees, we should update this class.
If anything fails, this class should handle the failure gracefully, especially if it involves payments, etc.
Now that it’s a class, creating unit tests for this specific business logic would be easier, ensuring that this process is more robust when change requests come in later.

Step 2: Update controllers

You can then use the PORO on the controller like this:

Optional Steps:
You can do it a step further and follow DHH’s approach, creating a method for the request model:

Then, you can easily create a call this method on the controller like so:

Question: Are callbacks evil?

There are two camps for this: people who are for and against callbacks.

My take is:
As developers, we constantly understand the domains that we are working on and develop a unique ubiquitous language for them.

Initially, we may not have the right words for it, thus we need to use convenient “generic” tools such as callbacks. But as soon as you learn more about the domain, and build a better ubiquitous language, the design of your code should follow also.

Originally posted on: https://blog.ademartutor.com/p/callbacks-are-evil

Hello there!

Do you have a startup idea or an exciting project you're passionate about? I'd love to bring your vision to life!

I'm a software developer with 13 years of experience in building apps for startups, I specialize in Rails + Hotwire/React.

Whether you're looking to innovate, grow your business, or bring a creative idea to the forefront, I'm here to provide tailored solutions that meet your unique needs.

Let's collaborate to make something amazing!

Sincerely,
Ademar Tutor

Dynamic AI Prompts with PromptTemplates, Ruby, Langchain.rb and OpenAI

Ademar Tutor — Mon, 15 Jan 2024 10:21:24 +0000

This tutorial talks about how to build a Ruby Chatbot with Langchain, PromptTemplate and OpenAI.

youtube.com

Previously, we've built a basic terminal chatbot with Ruby. Now, we are going to focus on PrompTemplates.

What are PromptTemplates?

PromptTemplates in Langchain.rb are game-changers. They allow you to create flexible, dynamic prompts with placeholders, which can be filled in with user input or other data at runtime.

This adaptability is critical in prompt engineering, where the goal is to generate prompts that elicit the most accurate and relevant responses from an AI model.

What is Prompt Engineering?

Prompt engineering is the art of crafting prompts that guide AI models to provide the desired output. The way you phrase a prompt can significantly impact the model's response.

PromptTemplates offer a way to experiment with different phrasings and structures without hard-coding every possible prompt.

Building an example chatbot

Imagine building a chatbot that explains to preschools what specific profession and skills they need to succeed in that profession.

Step 1

Require the necessary libraries: OpenAI and Langchain.

require "openai"
require "langchain"

Step 2

Set the logger level of Langchain to info, which means it will log informational messages. It is not a required step, but it's always good to know what's happening in the background with Langchain.rb

Langchain.logger.level =  :info

Step 3

Initialize a new Langchain::LLM::OpenAI object. This object is used to interact with OpenAI's API.
You need to provide your API key and other options.
llm_options is an empty hash here, but it can be used to pass additional options.
default_options sets the default language model to GPT-4 for chat completions.

openai = Langchain::LLM::OpenAI.new(
  api_key: ENV["OPENAI_API_KEY"],
  llm_options: {},
  default_options: { chat_completion_model_name: "gpt-4" }
)

Step 4

Create a new conversation object. This object will manage the conversation flow using the OpenAI model.

chat = Langchain::Conversation.new(llm: openai)

Step 5

Create a new PromptTemplate object. This template has a placeholder {profession} that can be filled in. input_variables defines the placeholders expected in the template.

Step 6

Prompt the user for the profession.

puts "Please enter the profession:"
user_input = gets.chomp

Step 7

Format the prompt template with the user's input and send the message to the OpenAI model. The response from the model is then printed out.

puts chat.message(prompt.format(profession: user_input))

Full Code

require "openai"
require "langchain"

Langchain.logger.level = :info

openai = Langchain::LLM::OpenAI.new(
  api_key: ENV["OPENAI_API_KEY"],
  llm_options: {},
  default_options: { chat_completion_model_name: "gpt-4" }
)

chat = Langchain::Conversation.new(llm: openai)

prompt = Langchain::Prompt::PromptTemplate.new(
  template: "Explain to a pre-schooler what an {profession} is and what they need to in order to be successful in the field.",
  input_variables: [ "profession" ]
)

puts "Please enter the profession:"
user_input = gets.chomp

puts chat.message(prompt.format(profession: user_input))

Hello AI world with Ruby!

Ademar Tutor — Sat, 13 Jan 2024 07:08:02 +0000

In this tutorial, we'll delve into creating your first AI-powered apps using Ruby, Langchain.rb library and OpenAI's GPTPT-4 API.

Objective

We'll create a terminal-based chatbot that allows you to OpenAI'S GPT-4. This chatbot will be able to process user inputs and generate relevant, context-aware responses.

First, we'll need to create a ruby file. Let's call this chat.rb
What we want to do next is import the necessary libraries

require "openai"
require "langchain"
require "reline"

OpenAI: The openai library is a Ruby client for interacting with OpenAI's API.
Langchain: Langchain is a Ruby library designed for building language applications.
reline: Reline is a Ruby library used for readline-compatible input in command-line applications.

Create an instance of Langchain::LLM::OpenAI. This class is a wrapper around OpenAI's API, specifically tailored for language models (LLMs).

Side Note: The great thing with Langchain.rb is it supports other models, too, offering flexibility to switch between different AI models based on requirements.

Chat Interaction

# What we'll do next is to Define a method to prompt for and handle user messages
def prompt_for_message
  # Print instructions for multiline input
  puts "(multiline input; type 'end' on its own line when done. or exit to exit)"

  # Read multiline input from the user, checking if the last word is a termination keyword
  user_message = Reline.readmultiline("Question: ", true) do |multiline_input|
    last = multiline_input.split.last # Get the last word of the input
    DONE.include?(last) # Check if the last word is a termination keyword
  end

  # Return a no-operation symbol if there is no user message
  return :noop unless user_message

  # Process the multiline input to handle the termination keyword
  lines = user_message.split("\n")
  if lines.size > 1 && DONE.include?(lines.last)
    # Remove the "done" keyword from the message
    user_message = lines[0..-2].join("\n")
  end

  # Check if the user wants to exit the program
  return :exit if DONE.include?(user_message.downcase)

  # Return the processed user message
  user_message
end

The method prompt_for_message, handles multiline user inputs and implements commands for ending the input or exiting the program. The commands are: "done", "end", "eof", and "exit".

Interactive Loop

# Our next step is to create infinite loop to continuously handle user input
begin
  loop do
    user_message = prompt_for_message # We get the user message using the defined method above

    # Handle different cases of user message
    case user_message
    when :noop # If no operation, continue to the next iteration of the loop
      next
    when :exit # If exit, break the loop to end the program
      break
    end

    # Using Langchain's instance method 'message, we send the user message to OpenAI and print the OpenAI's response
    puts chat.message(user_message)
  end
# Lastly, we handle the Interrupt exception to gracefully exit the program if interrupted (e.g., Ctrl+C)
rescue Interrupt
  exit 0
end

The code continuously fetches user messages and uses chat.message to obtain and display responses from the AI, creating a dynamic conversation flow.

Full code of chatbot.rb

require "openai"
require "langchain"
require "reline"

Langchain.logger.level = :info

openai = Langchain::LLM::OpenAI.new(
  api_key: ENV["OPENAI_API_KEY"], # Use the OpenAI API key from the environment variable
  llm_options: {}, # Options for the language learning model (empty in this case)
  default_options: { chat_completion_model_name: "gpt-4" } # Set GPT-4 as the default chat model
)

chat = Langchain::Conversation.new(llm: openai)
chat.set_context("You are a chatbot from the future") # Set the context of the conversation

DONE = %w[done end eof exit].freeze

puts "Welcome to the chatbot from the future!"

def prompt_for_message
  puts "(multiline input; type 'end' on its own line when done. or exit to exit)"

  user_message = Reline.readmultiline("Question: ", true) do |multiline_input|
    last = multiline_input.split.last # Get the last word of the input
    DONE.include?(last) # Check if the last word is a termination keyword
  end

  return :noop unless user_message

  lines = user_message.split("\n")
  if lines.size > 1 && DONE.include?(lines.last)
    user_message = lines[0..-2].join("\n")
  end

  return :exit if DONE.include?(user_message.downcase)

  user_message
end

begin
  loop do
    user_message = prompt_for_message

    case user_message
    when :noop
      next
    when :exit
      break
    end
    puts chat.message(user_message)
  end

rescue Interrupt
  exit 0
end

Understanding Big-O Notation with Ruby

Ademar Tutor — Mon, 08 Jan 2024 15:18:59 +0000

Big-O Notation in Ruby

In college, Big-O Notations was taught in one of our courses. I really could not connect the dots back then. Big-O notations felt too theoretical at that time.

So, as a professional developer, I relied upon performance tools like rack-mini-profiler, Benchmark, bullet, etc.

When 3rd party monitoring apps like AppSignal and New Relic started becoming good at monitoring performance, I began creating rules when writing code to avoid performance issues later when my code hits production.

These are some of my "performance" rules:

1) Be Mindful with Loops

Rule: Reduce database hits inside loops.

# Bad
User.all.each do |user|
  user.update_attribute(:status, "active")
end

# Good
User.update_all(status: "active")

2) Optimize Database Queries

Rule: Avoid N+1 queries by eager loading associated records.

# Bad
User.all.each do |user|
  puts user.profile.name
end

# Good
User.includes(:profile).each do |user|
  puts user.profile.name
end

Note: Although, if you use the Russian Doll Caching strategy, this might not apply.

3) Background Jobs for Time-Consuming Tasks

Rule: If all else fails, move long-running tasks to background jobs. Pray that the user does not need the data ASAP 🙏

# Using Sidekiq or similar
LongTaskWorker.perform_async(user_id)

I have realized you can get by with your app's performance by learning those simple rules.

However, having a solid foundation in your bag that has been used since 1894 might be a good idea.

What is Big-O notation?

In plain words, Big-O notation describes the performance of your code using algebraic terms. Performance in this context refers to either the speed of execution or the amount of RAM the code consumes.

In computer science, these concepts are more formally known as 'time complexity' for speed and 'space complexity' for RAM usage. Big-O notation is used for both, but we're going to focus on speed here to simplify our discussion.

Big-O in real-life

In a web application, handling a process that involves sorting or searching through 100 data entries will naturally be slower compared to dealing with just 10 entries.

The key question is: how much slower is it? Does the time taken increase 10x, a 100x, or perhaps even a 1000x?

This variance in processing speed might not be evident when dealing with smaller data sets.

However, the situation changes if your application's performance degrades significantly with the addition of each new entry in the database.

Such a decline in speed becomes a major concern, particularly as the volume of data grows larger in the app.

Understanding Big O notation is crucial in this context. It helps developers predict how their code will scale as data volumes increase, allowing them to choose the most efficient algorithms and data structures.

By anticipating performance issues before they occur, developers can optimize their applications for speed and efficiency, ensuring a smoother user experience even as data grows. This foresight is invaluable in maintaining a high-performing web application over time.

Here's a super accurate emoji-based representation of Big-O notations to give you an idea of how fast they are as your data scales:

🚀 O(1) - Speed does not depend on the scale of the dataset

🚄 O(log n) - If you have ten times more data, it only takes twice as long to process.

🚗 O(n) - If the amount of data increases tenfold, the processing time also increases tenfold.

🚲 O(n log n) - If you increase the data by ten times, the processing time will roughly increase by twenty times.

🏃‍♂️ O(n^2) - If the amount of data is multiplied by ten, the processing time increases by a factor of one hundred.

🚶‍♂️ O(2^n) - Doubling the amount of data leads to an exponential increase in processing time, making it significantly longer.

Big-O Notations In-depth

🚀 O(1)

O(1) indicates that the execution time of an operation remains constant, regardless of the size of the data set.

Example of accessing an element in a hash; the time taken is independent of the hash's size:

# Access time remains 
# constant for these

hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]

As a result, hashes generally perform better than arrays for large datasets. Here's another Ruby example:

# Retrieving an item 
# from arrays of varying 
# sizes

array_with_100_items[50]
array_with_1000_items[50]
array_with_10000_items[50]

In this case, fetching an element at a specific index (like the 50th position) takes the same amount of time, regardless of the array's size.

🚄 O(log n)

O(log n) describes an algorithm where the time it takes to complete a task increases logarithmically in relation to the size of the dataset.

This means that each time the dataset doubles in size, the number of steps required increases by a relatively small, fixed amount.

O(log n) operations are efficient and much faster than linear time operations for large datasets.

Here is a Ruby example illustrating O(log n) complexity:

Binary Search:

A binary search algorithm in a sorted array is a classic example of O(log n) complexity. At each step, it divides the dataset in half, significantly reducing the number of elements to search through.

Here’s an example of a Ruby code of binary search. We compare the time difference with benchmark when we double the dataset. Code:

require 'benchmark'

def binary_search(array, key)
  low = 0
  high = array.length - 1

  # This loop runs as long 
  # as the 'low' index is 
  # less than or equal to  
  # the 'high' index
  while low <= high
    # Find the middle 
    # index of the 
    # current range
    mid = (low + high) / 2
    value = array[mid]

    # If the value is less 
    # than the key, narrow 
    # the search to the 
    # upper half of the 
    # array
    if value < key
      low = mid + 1
    # If the value is 
    # greater than the 
    # key, narrow the 
    # search to the 
    # lower half of 
    # the array
    elsif value > key
      high = mid - 1
    # If the key is found, 
    # return its index
    else
      return mid
    end
  end

  # If the key is not 
  # found in the 
  # array, return nil
  nil
end

# Example usage with an 
# array of 100 million 
# elements
array = (1..100000000).to_a
puts Benchmark.measure {
  binary_search(array, 30)
}

# Example usage with an 
# array of 200 million 
# elements
array = (1..200000000).to_a
puts Benchmark.measure {
  binary_search(array, 30)
}

# Example usage with an 
# array of 300 million 
# elements
array = (1..300000000).to_a
puts Benchmark.measure {
  binary_search(array, 30)
}

In this code, the binary search algorithm has a time complexity of O(log n) because it divides the search interval in half with each step.

In each iteration of the while loop, it either finds the element or halves the number of elements to check.

This halving process continues until the element is found or the interval is empty.

As a result, the time to complete the search increases logarithmically with the size of the array (n), making binary search efficient for large datasets.

Result:

Even got faster on with 300 million elements 😅

🚗 O(n)

O(n) describes the time complexity of an algorithm where the time to complete a task grows linearly and in direct proportion to the size of the input data set. This means that if you double the number of elements in your data set, the algorithm will take twice as long to complete.

Here is a Ruby example illustrating O(n) complexity:

Summing all elements in an array:

In this example, the time to sum all elements increases linearly with the number of elements in the array.

Code:

require 'benchmark'

def sum_array(array)
  sum = 0
  # Iterating over each 
  # element in the array
  array.each do |element|
    # Adding each element 
    # to the sum
    sum += element  
  end
  # Returning the 
  # total sum
  sum  
end

# Summing an array of 
# 100 million elements
array = (1..100000000).to_a
puts Benchmark.measure {
  # The time taken here is 
  # proportional to the 
  # array's size
  sum_array(array)  
}

# Summing an array of 
# 200 million elements
array = (1..200000000).to_a
puts Benchmark.measure {
  # Time taken will be roughly 
  # twice that of the 100 
  # million array
  sum_array(array)  
}

# Summing an array of 
# 300 million elements
array = (1..300000000).to_a
puts Benchmark.measure {
  # Time taken will be roughly 
  # three times that of the 
  # 100 million array
  sum_array(array)  
}

In this code, the sum_array function has an O(n) complexity because it involves a single loop that iterates over each element of the array exactly once.

The time taken to execute this function scales linearly with the number of elements in the array (n).

Therefore, if you double the size of the array, the time to sum the array also doubles, which is characteristic of linear time complexity.

Result:

Observe how the execution time scales linearly as we add 100 million more elements each time.

🚲 O(n log n)

O(n log n) describes the time complexity of an algorithm where the time to complete a task increases at a rate proportional to the number of elements in the data set (n) multiplied by the logarithm of the number of elements (log n).

Here is a Ruby example illustrating O(n log n) complexity:

Merge Sort:

Merge Sort is a classic example of an algorithm with O(n log n) complexity. It divides the array into halves, sorts each half, and then merges them back together.

Code:

require 'benchmark'

def merge_sort(array)
  # Base case: a single 
  # element is already 
  # sorted
  if array.length <= 1
    array
  else
    # Find the middle 
    # of the array
    mid = array.length / 2

    # Recursively sort 
    # the left half
    left = merge_sort(array[0...mid])
    # Recursively sort 
    # the right half
    right = merge_sort(array[mid..-1])

    # Merge the two 
    # sorted halves
    merge(left, right)
  end
end

def merge(left, right)
  sorted = []
  # Until one of the arrays 
  # is empty,pick the smaller 
  # element from the front 
  # of each array
  until left.empty? || right.empty?
    if left.first <= right.first
      sorted << left.shift
    else
      sorted << right.shift
    end
  end

  # Concatenate the remaining 
  # elements (one of the arrays 
  # may have elements left)
  sorted.concat(left).concat(right)
end


# Benchmarking with 
# 10 million elements
array = (1..10000000).to_a
puts Benchmark.measure {
  merge_sort(array)
}

# Benchmarking with 
# 20 million elements
array = (1..20000000).to_a
puts Benchmark.measure {
  merge_sort(array)
}

# Benchmarking with 
# 30 million elements
array = (1..30000000).to_a
puts Benchmark.measure {
  merge_sort(array)
}

The merge_sort function exhibits O(n log n) complexity because it involves a divide-and-conquer approach.

The array is repeatedly divided into halves (resulting in a logarithmic number of divisions, i.e., log n), and each half is sorted and then merged.

The merging process for each level is linear in the size of the input (i.e., n), leading to a total time complexity of O(n log n).

This makes merge sort much more efficient for large datasets compared to algorithms with quadratic time complexities (like bubble sort or insertion sort), especially as the size of the data increases.

Result:

The slowness of execution time of merge sort handling millions of elements becomes really obvious.

🏃‍♂️ O(n^2)

O(n^2) describes the time complexity of an algorithm where the time to complete a task is proportional to the square of the number of elements in the input dataset.

This means that if the number of elements doubles, the time to complete the task increases by four times. Algorithms with O(n^2) complexity are generally less efficient for large datasets compared to O(n log n) or O(n) algorithms.

Here is a Ruby example illustrating O(n^2) complexity.

Bubble Sort:

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Code:

require 'benchmark'

def bubble_sort(array)
  n = array.length
  # Loop until no more swaps are needed
  loop do
    swapped = false
    # Iterate through the array. The '-1' is because Ruby arrays are zero-indexed,
    # and we're comparing each element with the next.
    (n-1).times do |i|
      # Compare adjacent elements
      if array[i] > array[i+1]
        # Swap if they are in the wrong order
        array[i], array[i+1] = array[i+1], array[i]
        # Indicate a swap occurred
        swapped = true
      end
    end
    # Break the loop if no swaps occurred in the last pass
    break unless swapped
  end
  # Return the sorted array
  array
end

# Benchmarking with 10,000 elements
array = (1..10000).to_a.shuffle
puts Benchmark.measure {
  bubble_sort(array)
}

# Benchmarking with 20,000 elements
array = (1..20000).to_a.shuffle
puts Benchmark.measure {
  bubble_sort(array)
}

# Benchmarking with 30,000 elements
array = (1..30000).to_a.shuffle
puts Benchmark.measure {
  bubble_sort(array)
}

In this bubble_sort method, the O(n^2) complexity arises from the nested loop structure:

a) The loop construct potentially iterates n times (in the worst case where the array is in reverse order).

b) Inside this loop, there's a (n-1).times loop that also iterates up to n-1 times for each outer loop iteration.

This nesting of loops, where each loop can run 'n' times, leads to the time complexity of O(n^2).

Result:

Noticed that I just maxed out the elements to 30,000. It was pretty slow already 😅

🚶‍♂️ O(2^n)

O(2^n) describes the time complexity of an algorithm where the time to complete a task doubles with each additional element in the input data set.

This kind of complexity is typical in algorithms that involve recursive solutions to problems where the solution involves creating two or more subproblems for each problem.

Such algorithms are often seen as inefficient for large datasets due to their exponential time growth.

Here is a Ruby example illustrating O(2^n) complexity.

Fibonacci Sequence (Recursive Implementation):

A classic example of O(2^n) complexity is the recursive calculation of the Fibonacci sequence, where each number is the sum of the two preceding ones.

Code:

require 'benchmark'

def fibonacci(n)
  return n if n <= 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

puts Benchmark.measure {
  fibonacci(10)
}

puts Benchmark.measure {
  fibonacci(20)
}

puts Benchmark.measure {
  fibonacci(30)
}

The number of operations grows exponentially with the input size, characteristic of O(2^n) time complexity.

This exponential growth makes these algorithms impractical for large input sizes due to the rapid increase in computation time.

Result:

I did not dare to use numbers above 100. It would be super slow 🐢

Summary

You should not be using these code examples in production apps. There are built-in Ruby sort and search. And if you are sorting records (in PostgreSQL), please use the database feature.

I hope you can appreciate Big-O notation and apply this to your daily work. 🚀