DEV Community: Giovanni Lima

Creating a Libras Recognizer with Artificial Intelligence and Teachable Machine

Giovanni Lima — Fri, 17 Oct 2025 04:47:31 +0000

Introduction

You know that one topic that seems like a seven-headed beast? For a long time, for me, that beast was called "Artificial Intelligence" and "Computer Vision." I thought it was just for experts, something super complex and far from my reality. But my curiosity was always there, and with the AI boom, I decided it was time to dive in and understand what happens behind the curtain.
That's when I discovered Teachable Machine, a tool from Google. It allowed me to train an image recognition model in a super simple way and see, in practice, how the magic happens.
For my very first experiment, I decided to create a letter recognizer for Libras (Brazilian Sign Language). ✌️

The Motivation Behind the Project

Talking about accessibility is fundamental to me. We live in an era with incredible technologies, frameworks, and AIs, and we have all the tools at our fingertips to build applications that truly include everyone.

Libras (Língua Brasileira de Sinais) is the official language of the deaf community in Brazil. It's not just a set of gestures; it's a complete and rich language. Communication is the bridge that connects us, and technology can be a powerful tool to make that bridge stronger and more accessible. Imagine using your phone's camera to translate Libras in real-time? The possibilities are enormous!

With this idea in mind, I started looking for tools for a pilot project, and Teachable Machine seemed perfect to get started.

Teachable Machine

Think of Teachable Machine as a "private tutor" for your Artificial Intelligence, but much easier to use. It's a free online platform from Google that works visually, without you needing to write a single line of code for the training.
It basically works in three steps:

Collect: You show the AI examples. If it's an image project, you take pictures. If it's sound, you record audio clips. Simple as that.

Train: You press a button. The platform analyzes all the examples you provided and learns to recognize the patterns for each category.

Export: The tool gives you a "finished" model, which you can download or use via a link in your own website or app projects.

Training a Model 🏋️

To start training our first model, we have the option to choose which category we want to train:

First, I chose an image project. Then, the fun began: I created my "classes," which are the categories I wanted the model to learn. For example: "Letter A," "Letter B."

With the webcam on, I started capturing several photos for each class. (A quick tip: Don't take all the pictures exactly the same! I moved my hand a bit, changed the angle, and moved closer to and farther from the camera. This helps the model become "smarter" and not depend on perfect conditions to work).

After capturing a good number of images, I clicked "Train Model." A few seconds later, the model was ready to be tested and exported.

Inside the Code 👨‍💻

The code that Teachable Machine generates is basically a web page (HTML + CSS + JavaScript) that comes ready to use. It accesses your webcam, loads the model you just trained, and shows what it's "seeing" in real-time.

Example of the application running:

Script Used:

 <script type="text/javascript">
        const URL = "https://teachablemachine.withgoogle.com/models/Ku7kMohsH/";

        let model, webcam, maxPredictions;
        let isRunning = false;

        const overlay = document.getElementById('overlay');
        const startBtn = document.getElementById('startBtn');
        const stopBtn = document.getElementById('stopBtn');
        const predictionsPanel = document.getElementById('predictionsPanel');
        const predictionsGrid = document.getElementById('predictionsGrid');
        const perfectPredictions = document.getElementById('perfect-predictions');
        const errorDiv = document.getElementById('error');

        async function init() {
            try {
                startBtn.disabled = true;
                startBtn.innerHTML = '<span class="spinner"></span>Initializing...';
                errorDiv.classList.add('hidden');

                if (typeof tmImage === 'undefined') {
                    throw new Error('Teachable Machine library not loaded. Please refresh the page.');
                }

                console.log('Loading model...');
                const modelURL = URL + "model.json";
                const metadataURL = URL + "metadata.json";

                model = await tmImage.load(modelURL, metadataURL);
                maxPredictions = model.getTotalClasses();
                console.log('Model loaded successfully. Classes:', maxPredictions);

                console.log('Setting up webcam...');
                const flip = true;
                webcam = new tmImage.Webcam(640, 480, flip);
                await webcam.setup({
                    facingMode: "user"
                });
                await webcam.play();

                console.log('Webcam ready');

                document.getElementById("webcam-container").appendChild(webcam.canvas);

                overlay.classList.add('hidden');
                startBtn.classList.add('hidden');
                stopBtn.classList.remove('hidden');
                predictionsPanel.classList.remove('hidden');

                isRunning = true;
                window.requestAnimationFrame(loop);

            } catch (error) {
                console.error('Initialization error:', error);
                errorDiv.textContent = error.message;
                errorDiv.classList.remove('hidden');
                startBtn.disabled = false;
                startBtn.textContent = 'Start Webcam';
            }
        }

        async function loop() {
            if (!isRunning) return;

            webcam.update();
            await predict();
            window.requestAnimationFrame(loop);
        }

        async function predict() {
            const prediction = await model.predict(webcam.canvas);
            displayPredictions(prediction);
        }

        function displayPredictions(predictions) {
            // Update predictions grid
            predictionsGrid.innerHTML = '';
            predictions.forEach(pred => {
                const item = document.createElement('div');
                item.className = 'prediction-item';
                item.style.borderLeftColor = `rgba(34, 211, 238, ${pred.probability})`;

                item.innerHTML = `
                    <span class="prediction-name">${pred.className}</span>
                    <div class="prediction-bar">
                        <div class="bar">
                            <div class="bar-fill" style="width: ${pred.probability * 100}%"></div>
                        </div>
                        <span class="prediction-value">${(pred.probability * 100).toFixed(1)}%</span>
                    </div>
                `;

                predictionsGrid.appendChild(item);
            });

            // Show perfect predictions overlay
            const perfect = predictions.filter(p => p.probability >= 0.95);
            if (perfect.length > 0) {
                perfectPredictions.innerHTML = perfect.map(p => `
                    <h2>${p.className}</h2>
                    <p>Precisão: ${(p.probability * 100).toFixed(1)}%</p>
                `).join('');
                perfectPredictions.classList.remove('hidden');
            } else {
                perfectPredictions.classList.add('hidden');
            }
        }

        function stop() {
            isRunning = false;

            if (webcam) {
                webcam.stop();
                const canvas = document.querySelector('#webcam-container canvas');
                if (canvas) {
                    canvas.remove();
                }
            }

            overlay.classList.remove('hidden');
            startBtn.classList.remove('hidden');
            startBtn.disabled = false;
            startBtn.textContent = 'Start Webcam';
            stopBtn.classList.add('hidden');
            predictionsPanel.classList.add('hidden');
            perfectPredictions.classList.add('hidden');
        }

        startBtn.addEventListener('click', init);
        stopBtn.addEventListener('click', stop);

        window.addEventListener('load', () => {
            if (typeof tmImage === 'undefined') {
                errorDiv.textContent = 'Required libraries failed to load. Please refresh the page.';
                errorDiv.classList.remove('hidden');
                startBtn.disabled = true;
            }
        });
    </script>

Essential Technologies:

TensorFlow.js (tf.min.js): This is the main library, the "brain" of the operation. It allows Machine Learning models to run directly in the browser, without needing a complex server. It's what performs the calculations to analyze the image from your webcam.
Teachable Machine Image Library (teachablemachine-image.min.js): This is a "helper" library built on top of TensorFlow.js. It enormously simplifies the process of loading your specific Teachable Machine model and connecting it to the webcam.

How the Script Works:

The URL constant: At the beginning of the script, the URL variable points to your model hosted on the Google cloud. That's where the browser downloads model.json (the architecture and "weights" of your trained model) and metadata.json (the names of your classes, like "Letter A").
init() function (Initialization): When you click to start the webcam, this function is called. It:
Loads the model from the specified URL (tmImage.load).
Configures and turns on the webcam (new tmImage.Webcam).
Starts a continuous "loop" to make predictions.
loop() function (The Real-Time Heart): This function runs dozens of times per second. In each "lap" of the loop, it:
Updates the webcam image (webcam.update).
Calls the predict function to analyze the current image.
predict() function (The Prediction): This is the most important part. It takes the current frame from the webcam and sends it to the loaded model (model.predict). The model returns an array with the probability that the image belongs to each of your classes (e.g., [{className: "Letter A", probability: 0.98}, {className: "Letter B", probability: 0.02}]).
displayPredictions() function (The Display): This function takes the prediction result and updates the page's interface, showing the class names and the percentage bars, giving you real-time visual feedback.

Results, Challenges, and Reflections 🤔

For a first experience, the result was incredible! It was really cool to see the machine recognizing my gestures on the screen. But, like in any project, I also faced some challenges.

What went well? For well-defined gestures with good lighting, the accuracy was very high, often exceeding 95%. The real-time response was also fantastic, with no delays.

What were the difficulties encountered? It became clear that the model is sensitive to its environment. A change in the room's lighting or a cluttered background was enough to confuse the AI. Similar gestures were also a challenge. This just goes to show how extremely important the quality of the training data is.

This experience made me think about the next step: a model that can identify complete words in Libras. The challenge would be much greater because it would involve recognizing a sequence of moving gestures, but with the tools we have today, it seems more and more possible.

Conclusion

Creating a Libras recognizer, even a simple one, reinforced for me the giant potential that technology has to promote inclusion. It's not just about code and algorithms, but about building bridges.

If I was able to create this in one evening, what's stopping us from diving deeper into our own projects? AI is increasingly within our reach these days. For those of you who read this far, thank you very much! Any feedback or questions will be well received.

How a Web Browser Works: Inside Modern Browsers

Giovanni Lima — Fri, 12 Sep 2025 02:09:32 +0000

Have you ever wondered what happens behind the scenes of your browser when you type a URL and press Enter? From the outside, it looks simple, but behind it lies a very complex engineering process involving steps, layers, and protocols. In this article, we’ll explore how browsers work and how their inner architecture is designed.

Components of a Browser

A browser can be understood and divided into several important parts:

User Interface (UI): The layer of interaction with the user, meaning everything you see and interact with directly, such as the address bar, navigation buttons, and tabs.

Browser Engine: The central engine of the browser. It bridges the user interface with other browser components. It also handles data persistence (cookies, cache, localStorage) and communicates with the Rendering Engine.

Rendering Engine: Responsible for rendering content on screen. This component converts HTML, CSS, and JavaScript into visible pixels, working alongside the JS interpreter and networking layer.

Networking: Manages HTTP/HTTPS requests, DNS resolution, cookies, cache, data compression, and all the security measures of the connection.

JavaScript Interpreter: Parses, compiles, and executes JS code: parsing, creating the Abstract Syntax Tree (AST), converting to bytecode, applying JIT optimizations, and running it on the JS VM. This enables DOM manipulation, event handling, and page interactivity.

Data Persistence: Allows the browser to store and retrieve data locally, ensuring user data, settings, and preferences are maintained across sessions.

It’s worth noting that the browser is primarily single-threaded. This means only one main thread controls the flow, which is crucial when discussing performance. To overcome this limitation, browsers use mechanisms such as the event loop, very similar to what we know from Node.js.

What Happens When We Type a URL?

When a URL is entered and Enter is pressed, the following steps occur:

Domain Resolution (DNS):
The first step is converting the domain name (e.g., google.com) into an IP address. The browser checks various caches (browser, OS, router, ISP).
If not found, it queries the DNS server, which returns the correct IP.

Server Connection (TCP Handshake):
After obtaining the IP, the browser establishes a connection using the three-way TCP Handshake:
SYN → SYN-ACK → ACK.
Think of this as the digital equivalent of starting a phone conversation.

Security with TLS Handshake:
Before exchanging data, a secure encryption key must be established. This involves multiple message exchanges between client and server to ensure traffic cannot be intercepted.

Edge Computing & CDNs:
To speed this up, companies like Google, Netflix, and Amazon use CDNs and Edge Locations worldwide, reducing latency between users and servers.

First Response – TTFB:
Once everything is set, the browser receives the first byte (Time to First Byte). Even before the full page is loaded, rendering begins.

Parsing and the Critical Render Path

When the browser receives the initial HTML, it begins parsing. The process includes:

DOM Construction: HTML is transformed into a tree structure called the Document Object Model.

CSSOM Construction: CSS is also parsed into a tree, the CSS Object Model. Unlike DOM, it must be fully built before continuing.

Render Tree: DOM + CSSOM combine into the Render Tree, which includes only visible elements with calculated styles.

Layout: Determines each element’s position and size on screen.

Painting: Finally, pixels are drawn on screen.
This flow is known as the Critical Render Path (CRP). Scripts may block DOM construction, and styles may delay CSSOM construction. That’s why techniques like async and defer for scripts improve loading speed.

Preload Scanner

As the DOM is being built, the browser runs the Preload Scanner, which looks for external resources (images, scripts, styles) referenced in HTML. These are downloaded in advance, reducing overall render time.

JavaScript and AST
Unlike compiled languages, JavaScript is interpreted, but modern browsers optimize execution:

Parsing: Code is parsed into an Abstract Syntax Tree (AST).

Bytecode & JIT: The AST is converted into bytecode, optimized by the Just-in-Time (JIT) compiler, and then executed by the JS Virtual Machine.

Execution: Deferred and blocking scripts are executed only after HTML and CSS are ready, ensuring faster initial rendering.

DOM in Detail

An HTML document can be represented in memory as a JavaScript tree (nodes and children). This allows frameworks, libraries, and developers to manipulate the page in real time.

Example:

const domTree = {
  nodeType: 'document',
  children: [
    { nodeType: 'doctype', name: 'html' },
    {
      tagName: 'html',
      attributes: { lang: 'en' },
      children: [
        {
          tagName: 'head',
          children: [
            { tagName: 'meta', attributes: { charset: 'utf-8' }, children: [] },
            { tagName: 'meta', attributes: { name: 'viewport', content: 'width=device-width, initial-scale=1' }, children: [] },
            { tagName: 'title', children: [{ type: 'text', content: 'Page Title' }] },
            { tagName: 'link', attributes: { rel: 'stylesheet', href: '/styles.css' }, children: [] },
            { tagName: 'script', attributes: { src: '/scripts/head.js', defer: true }, children: [] }
          ]
        },
        {
          tagName: 'body',
          children: [
            {
              tagName: 'header',
              children: [
                { tagName: 'h1', children: [{ type: 'text', content: 'Main Header' }] },
                {
                  tagName: 'nav',
                  children: [
                    {
                      tagName: 'ul',
                      children: [
                        { tagName: 'li', children: [{ tagName: 'a', attributes: { href: '/' }, children: [{ type: 'text', content: 'Home' }] }] },
                        { tagName: 'li', children: [{ tagName: 'a', attributes: { href: '/about' }, children: [{ type: 'text', content: 'About' }] }] }
                      ]
                    }
                  ]
                }
              ]
            },
            {
              tagName: 'main',
              children: [
                {
                  tagName: 'article',
                  attributes: { id: 'post-1' },
                  children: [
                    { tagName: 'h2', children: [{ type: 'text', content: 'Article Title' }] },
                    { tagName: 'p', children: [{ type: 'text', content: 'First paragraph of the article.' }] },
                    { tagName: 'img', attributes: { src: '/img/photo.jpg', alt: 'Photo' }, children: [] }
                  ]
                },
                {
                  tagName: 'section',
                  attributes: { id: 'features' },
                  children: [
                    { tagName: 'h3', children: [{ type: 'text', content: 'Features Section' }] },
                    {
                      tagName: 'ul',
                      children: [
                        { tagName: 'li', children: [{ type: 'text', content: 'Feature A' }] },
                        { tagName: 'li', children: [{ type: 'text', content: 'Feature B' }] }
                      ]
                    }
                  ]
                }
              ]
            },
            {
              tagName: 'aside',
              children: [
                { tagName: 'h4', children: [{ type: 'text', content: 'Sidebar' }] },
                { tagName: 'p', children: [{ type: 'text', content: 'Supporting content / widgets.' }] }
              ]
            },
            {
              tagName: 'footer',
              children: [
                { tagName: 'p', children: [{ type: 'text', content: '© 2025 My Company' }] },
                { tagName: 'ul', children: [{ tagName: 'li', children: [{ tagName: 'a', attributes: { href: '/privacy' }, children: [{ type: 'text', content: 'Privacy Policy' }] }] }] }
              ]
            },
            { tagName: 'script', attributes: { src: '/scripts/bundle.js' }, children: [] }
          ]
        }
      ]
    }
  ]
};

Also, the DOM is not static. The browser may build it incrementally while downloading new resources. This makes the DOM a live and dynamic structure, fully manipulable via JavaScript APIs.

Conclusion

To render a single webpage, the browser goes through a huge process that involves:

Resolving domains
Performing multiple handshakes
Handling security protocols
Building DOM and CSSOM trees
Generating the Render Tree, layout, and painting
Executing optimized JavaScript

And all of this happens within a fraction of a second. This article was inspired by Augusto Galego’s amazing video How Browsers Work?, where he explains these topics in a clear and simple way. Of course, many other layers are involved in browser functionality, and building one from scratch would be an incredibly complex task.

If you’ve read this far, thank you very much! Any feedback will be greatly appreciated.

How Jotai Atoms Are Transforming Our Front-End Architecture.

Giovanni Lima — Fri, 29 Aug 2025 12:13:52 +0000

Atom-Based Architecture ⚛️

Jotai’s architecture is based on the concept of atoms, where we work with independent and reactive units of state. Each atom can represent a unique source of data, holding either a primitive value or a derived state from other atoms, allowing for fine control over the behavior of global state.

Atoms are created in an immutable way, where only an initial value or a function for derived values is defined, making dependency and update management much more efficient. Through this atom-based architecture, Jotai automatically optimizes renders for components that consume these states, avoiding unnecessary re-renders.

With useContext, as the project grows and shared state increases, any change in context can force a re-render of all consumer components, even if only a small part of the tree actually uses the updated data. This negatively impacts performance and increases code complexity. Jotai avoids this problem by allowing for granular and independent states through atoms. In the project I am currently working on, we migrated from useContext to Jotai and saw a significant performance gain, as well as eliminating phantom bugs caused by excessive re-renders.

Main Challenges in React State Management 🗯️

One of the biggest challenges in managing state in modern React applications is the increasing complexity of user interfaces and the need to efficiently share data between components. It is crucial to control UI updates to guarantee performance and avoid bugs caused by unnecessary re-renders.

Prop drilling is a common problem: it happens when data or functions are passed through many layers of components, even if some do not use them directly. This creates a chain of information passing that makes the code more complex and prone to errors.

To tackle these challenges, several libraries like Redux, MobX, Zustand, Jotai, and Recoil have emerged, each created for specific solutions and with their own complexities. Although React offers native features such as the Context API, it may present limitations, especially in larger and more scalable projects.

Practical Examples ✍️

There are several ways to implement atoms; here are three examples:

Primitive Atom (Read/Write)
In Jotai, it is possible to create a primitive atom for reading and writing, functioning similarly to useState, but globally and immutably. This pattern is ideal for simple states shared across components.

import { atom, useAtom } from 'jotai'

// Creating a primitive atom
const counterAtom = atom(0)

function Counter() {
  const [counter, setCounter] = useAtom(counterAtom)
  return (
    <div>
      <p>Value: {counter}</p>
      <button onClick={() => setCounter(counter + 1)}>Increment</button>
    </div>
  )
}

Read-only Atom
This atom is ideal for derived states, calculations, and some projections that depend on other data, without needing to modify its value directly.

import { atom, useAtom } from 'jotai'

const counterAtom = atom(10)
const doubleAtom = atom((get) => get(counterAtom) * 2)

function DoubledValue() {
  const [double] = useAtom(doubleAtom)
  return <span>Double: {double}</span>
}

Write-only Atom
This atom is ideal for global actions, resets, or commands that modify the state without consuming its value.

import { atom, useSetAtom } from 'jotai'

const counterAtom = atom(5)
const resetAtom = atom(null, (get, set) => set(counterAtom, 0))

function ResetButton() {
  const reset = useSetAtom(resetAtom)
  return <button onClick={reset}>Reset Counter</button>
}

Read/Write Atom
This type of atom can be used for scenarios where the value is derived from another state and can be updated in a calculated way.

import { atom, useAtom } from 'jotai'

const counterAtom = atom(3)
const multipliedCounterAtom = atom(
  (get) => get(counterAtom) * 3,
  (get, set, newValue) => set(counterAtom, newValue / 3)
)

function Multiplier() {
  const [multipliedValue, setMultiplied] = useAtom(multipliedCounterAtom)
  return (
    <div>
      <span>Multiplied: {multipliedValue}</span>
      <button onClick={() => setMultiplied(9)}>Set to 9</button>
    </div>
  )
}

Conclusion 🏁

Jotai stands out for its versatility and simplicity. It offers an efficient architecture for state management based on atoms, suitable for projects of all sizes. However, it is essential to evaluate each project’s specific needs before implementing. In the project I am currently working on, Jotai proved to be a great fit for both performance and efficiency, as well as for code organization and maintainability. The most important thing is to choose a solution that best balances performance, scalability, and ease of maintenance for the project’s context. If you’ve read this far, I hope you enjoyed it.

Optimizing Usability and SEO with Loaders

Giovanni Lima — Fri, 21 Mar 2025 11:13:39 +0000

In web development, user experience is fundamental for creating fast and performative applications. These days, applications handle a ton of data that needs to be consumed and presented effectively. This can create a lot of problems on the front-end, so we need to find ways to handle these data efficiently without harming our apps. As our application grows, we need to be faster and more effective to ensure that the user experience remains good

In the context of ReactJS applications, optimizing SEO metrics is one of the most important factors for improving the visibility and engagement of our site

We recognize that applications using Next.js with Server-Side Rendering (SSR) can resolve many of these SEO issues. However, what about Single-Page Applications (SPAs)? Tools like react-router-dom, along with loaders, can help by ensuring that content is loaded efficiently, providing a better user experience and assisting
search engines in crawling and indexing dynamic content more effectively. This can be particularly useful in SPAs, where content is often loaded dynamically, and loaders can help manage the loading state to improve both user engagement and SEO metrics

What are Loaders in react-router-dom ?

React Router v6.4 introduced a key feature that improves how data is fetched and rendered in applications. This version allows us to fetch data in real-time before rendering the UI, based on specific routes.

Recently at work, I had to handle data from an API that was crucial for my page, both for enhancing the user experience by providing this data on the first render and for SEO metrics.

Let's Code!

To get started, we will set up the routes for our application using Vite. Let's create a file called router.tsx. This file will be responsible for defining all the routes of the application. We will use createBrowserRouter

// router.tsx
import { createBrowserRouter, RouterProvider } from "react-router-dom";
import Home from "./pages/Home";
import Products from "./pages/products";
import Contact from "./pages/Contact";

const router = createBrowserRouter([
  {
    path: "/",
    element: <Home />,
  },
  {
    path: "/products",
    element: <Products />,
  },
  {
    path: "/contact",
    element: <Contact />,
  },
]);

export default router;

Rendering Router

To render the router, we will need to use the RouterProvider component in the main file app.tsx.

// App.tsx
import React from "react";
import { RouterProvider } from "react-router-dom";
import router from "./router";

function App() {
  return <RouterProvider router={router} />;
}

export default App;

Pratical Example: Route configuration with Loaders

Think of a situation where you are developing an application that displays product information. You want the data for a specific product to be available on the screen as soon as the user accesses its page, enhancing the user experience and facilitating search engine indexing. This method can help improve this scenario.

// router.tsx
import { createBrowserRouter } from "react-router-dom";
import Home from "./pages/Home";
import Products from "./pages/Products";
import Contact from "./pages/Contact";

const productsLoader = async () => {
  const response = await fetch('/api/products');  
  const productsData = await response.json();
  return productsData;
};

const router = createBrowserRouter([
  {
    path: "/",
    element: <Home />,
  },
  {
    path: "/products",
    element: <Products />,
    loader: productsLoader,
  },
  {
    path: "/contact",
    element: <Contact />,
  },
]);

export default router;

By doing so, we can consume our API route directly within the loader, which allows us to fetch data before rendering the component.

Consuming data in component Products ↩️

To use the data loaded by the loader in our Products component, we will use the useLoaderData hook.

import React from "react";
import { useLoaderData } from "react-router-dom";

function Products() {
  const productsData = useLoaderData();

  return (
    <div>
      <h1>Produtos</h1>
      <ul>
        {productsData.map((product) => (
          <li key={product.id}>{product.name}</li>
        ))}
      </ul>
    </div>
  );
}

export default Products;

This way, we can fetch data in React Router using data loaders. This is simple, right? This improves not only the user experience of viewing data on the screen but also helps with app indexing. Additionally, we can also work with scripts being inserted into the page before rendering. This solved a real problem we were having in the project, where scripts were loaded after the first render

Important Note 🔴

The loader should not be used in every scenario. It's crucial to evaluate based on your application and context so that it can be used in the best possible way.

Conclusion

I hope you enjoyed this article. If you have any feedback or notice any errors, please feel free to share in the comments. ❤️

Entendendo algoritmos - Notação Big O

Giovanni Lima — Wed, 14 Jun 2023 02:30:07 +0000

Notação Big O: Medindo a Eficiência dos Algoritmos

A notação Big O representa a velocidade de um algoritmo. No nosso dia a dia, é comum nos depararmos com algoritmos desenvolvidos por outras pessoas e é interessante entender se eles são rápidos ou lentos.

Mas como podemos medir essa velocidade? 🤔

Utilizamos dois algoritmos diferentes para realizar um cálculo e cronometramos o tempo de execução? Na verdade, não. Os tempos de execução crescem com velocidades diferentes.
Vamos usar o exemplo apresentado no livro para ilustrar essa ideia de maneira mais simples.

Exemplo de como o tempo de execução de dois algoritmos pode crescer a taxas diferentes 📈

Jake é um estudante de ciência da computação e está participando de uma competição de algoritmos. Seu primeiro desafio é buscar um número específico em uma lista ordenada de 100 elementos.
Jake precisa decidir qual algoritmo utilizar para a busca. O algoritmo precisa ser rápido e correto, pois ele tem um tempo limitado para resolver o desafio e obter uma boa nota.
Por um lado, a busca binária é mais rápida, mas, por outro lado, a busca simples é mais fácil de implementar.
Vamos considerar que Jake leva 1 milissegundo para verificar um elemento. Se ele usar a busca simples, levaria 100 milissegundos para executar o algoritmo, pois ele teria que verificar os 100 elementos. No entanto, se ele usar a busca binária, ele verificará apenas 7 elementos, pois log de 100 na base 2 é aproximadamente 7.
Agora, imagine se a lista crescer ainda mais. Se Jake precisar verificar mais de 1 milhão de elementos, utilizando a busca binária, seriam necessários cerca de 20 milissegundos para executar o algoritmo. Já utilizando a busca simples, seriam necessários 1 milhão de milissegundos, o que equivale a aproximadamente 16 minutos.
Podemos perceber que o tempo de execução não é algo fixo e independente do tamanho dos elementos com os quais estamos trabalhando. O ponto que queremos destacar é que o tempo de execução da busca simples e da busca binária cresce de acordo com suas taxas. Conforme o número de elementos a serem verificados aumenta, a busca binária aumenta apenas um pouco o tempo de execução, enquanto a busca simples aumenta consideravelmente muito mais.
Um exemplo do tempo de execução variando de acordo com a taxa →

Desse modo, entendemos que não basta sabermos quanto tempo um algoritmo demora para ser executado e sim o tempo que leva para ser executado conforme sua taxa aumenta. Portanto, aí que entra a famosa Notação Big O

Vamos supor que temos uma lista de tamanho (n). O tempo de execução na notação Big o é
$O (n)$
A notação não nos fornece o tempo de execução em segundos, mas sim o quão rapidamente o algoritmo cresce. Sendo assim, podemos escrever a notação Big O da seguinte forma:

Esse formato nos mostra o número de operações que um algoritmo realiza. Chamamos de Big O porque colocamos um 'O' maiúsculo na frente do número de operações 🤭
Portanto, podemos definir o tempo de execução de um algoritmo de busca simples como O(n) e o tempo de execução de um algoritmo de busca binária como O(log n), e assim por diante, dependendo do algoritmo que estamos utilizando.

A espera do pior cenário ☠️

Na notação Big O, estabelecemos o tempo de execução para o pior cenário do problema que estamos resolvendo. Por exemplo, para a busca simples, o tempo de execução é O(n), o que significa que, no pior caso, teríamos que verificar todos os 'n' elementos da lista. Se ocorrer de encontrar o elemento que preciso na minha primeira busca, podemos acabar pensando que o algoritmo teve um tempo de O(1), mas na verdade não. Sempre levamos em consideração a pior hipótese, onde analisamos cada item da lista, esse é o tempo de O(n).
💡 No entanto, é importante destacar que podemos analisar não apenas o pior caso, mas também o caso médio.

Precisamos entender que tudo isso é uma simplificação. Não podemos determinar exatamente o tempo de execução na notação Big O em termos de número de operações, mas a aproximação já nos ajuda bastante.
Até agora, discutimos apenas dois algoritmos: busca binária e busca simples. No entanto, existem muitos outros tipos de algoritmos, cada um adequado para diferentes contextos e usos. Por exemplo, a busca binária não pode ser usada como uma solução universal, pois é necessário analisar e identificar qual algoritmo utilizar em cada caso específico

Conclusão

Espero que tenha gostado do artigo e estou aberto a dúvidas e correções também 🤘
Escrevi um artigo anterior a esse sobre pesquisa simples e pesquisa binária caso queira dar uma olhada.

Referências

Conteúdo desse artigo foi retirado do livro "Entendendo algoritmos - Um guia ilustrado para programadores e outros curiosos". Capítulo sobre Notação Big O a partir da página 29.

Entendendo algoritmos - Pesquisa binária

Giovanni Lima — Thu, 06 Apr 2023 03:39:19 +0000

Entendendo problemas de busca

Vamos supor que você esteja procurando o nome de uma pessoa em uma agenda ordenada em ordem alfabética. O nome da pessoa que deseja encontrar começa com a letra "K”, sendo assim, é comum começar a busca pelo meio da lista, certo? Dessa forma, a busca seria mais rápida. Podemos também dar o exemplo do próprio Facebook, quando você faz o login, ele precisa buscar seu nome no banco de dados. Nesse caso, a busca também começa pelo meio caso seu nome comece com a letra “M”, por exemplo.

Esses são exemplos de problemas de busca que podem ser resolvidos usando o algoritmo de pesquisa binária.

Pesquisa binária x Pesquisa simples 🥊

Vamos supor que tenho um número de 1 a 100 e você precisa adivinhar esse número com o menor número de tentativas possíveis. Isso é chamado de pesquisa simples, um método muito lento e ineficaz para buscar um resultado.

No pior cenário, levaríamos 100 tentativas para chegar ao resultado esperado. Portanto, vamos buscar de uma maneira melhor.
Para nos ajudar vamos definir alguns valores: máximo e mínimo. Onde o máximo = 100 (número total dos números) e mínimo = 0.
Vamos supor que o número que você precise adivinhar seja 91 e a cada tentativa vou informar se o número informado é menor ou maior que o resultado. Iremos iniciar nosso chute com o número 50 e com uma pequena fórmula: (min + max) / 2 = 50 onde o valor mínimo começa em 0 e o máximo é o número total. Podemos já notar que reduzimos o número de tentativas pela metade.
Certo! Nesse momento informo para você que o número que você chutou é menor que o resultado esperado, agora sabendo que nosso número é menor vamos atribuir o valor de 50 em nosso valor mínimo e somar + 1, dessa forma →
$51 + 100/2 = 75$

(OBS: Em nossa média sempre devemos arredondar nosso número para baixo)
75 agora é o valor do nosso chute, mas ainda não chegamos no resultado esperado, o resultado que queremos “adivinhar” é 92.
Nesse caso como nosso chute ainda foi menor que o resultado esperado, vamos repetir o processo de atribuir nosso chute em nosso valor mínimo e somar mais 1 para obter a média novamente, vamos lá!
$((75 + 1) + 100) /2 = 88$

Ainda não chegamos, o valor continua baixo, vamos repetir o processo novamente!
$((88 + 1) + 100) /2 = 94$

Humm, quase lá! Nesse caso nosso chute passou o valor esperado, quando o valor ultrapassa o resultado realizamos o oposto. Vamos atribuir o valor do chute no valor máximo e subtrair -1 para obter nossa média novamente.
→ Mantemos nosso valor mínimo e subtraímos -1 do valor do chute anterior substituindo nosso max.
$(89 + (94 - 1)) /2 = 91$

E finalmente chegamos em nosso valor esperado.
Como podemos observar, comparando a busca com a pesquisa simples, reduzimos muitas etapas para chegar no número esperado.
E isso se trata de um algoritmo de pesquisa binária.

Implementação de um algoritmo de busca binária usando javascript

function binarySearch(array, element) {
    let low = 0
    let high = array.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (array[mid] === element) {
            return mid
        }
        if (array[mid] < element) {
            low = mid + 1
        } else {
            high = mid - 1
        }    
    }
    return null    
}

De acordo com o livro, de uma maneira geral, para uma lista de n números a pesquisa binária precisa de
$log_2n$ para retornar o valor correto, enquanto a pesquisa simples precisa de n etapas

Mas o que isso quer dizer ?

Se temos um array com 8 elementos, na busca binária vamos reduzindo o tamanho do array para 4, depois para 2 e por fim 1.
Então, com um array de comprimento 8 nossa busca binária precisa de no máximo quatro suposições onde acrescentamos + 1 em nossas suposições para garantir que todos os elementos do array sejam verificados.

O logaritmo é uma função matemática que representa o número de vezes que reduzimos pela metade um número de forma repetida, onde podemos escrever de uma forma mais adequada essa resolução.

Para explicar logaritmos também podemos falar sobre exponenciais, já que logaritmos são o oposto de exponenciais.

A expressão: $log_10(100)$ → (log de 100 na base 10) representa basicamente com quantos 10 podemos chegar a 100 e a resposta é 2, pois 10x10 = 100.
Podemos considerar esse outro exemplo ->
escrevendo como exponencial:
$a ˆ b = c$
escrevendo como logaritmo:
$log_a(c) = b$

Mas qual a diferença entre logaritmos e exponenciais ?

Na exponenciação conhecemos os valores de A e B, onde queremos obter o C e é isso que a exponenciação faz.
Já no logaritmo, sabemos quanto vale o A e queremos descobrir a qual potência deve elevar "A” para obter "C”, assim determinamos o "B”, são relações escritas de formas diferentes.
Fica claro no livro que quando falamos sobre Big O (onde será abordado no próximo capítulo) iremos utilizar $log_2$ (log na base de 2) por ser mais utilizado nos algoritmos que utiliza uma estratégia de "divisão e conquista”. Quando buscamos um elemento por pesquisa simples no pior dos cenários, necessitamos buscar elemento por elemento. Na pesquisa binária, precisamos verificar $log_n$ elementos para o pior dos casos.
Para uma lista de 1024 elementos, temos → $log_2 1024 == 10$ pois $2ˆ10 == 1024$
Dessa forma, uma lista de 1024 elementos através da pesquisa binária, precisaríamos verificar no máximo dez etapas.

💡Lembrando que para que a pesquisa binária funcione é necessário que a lista esteja ordenada, pois não é possível realizar busca por etapas caso a lista não esteja seguindo uma ordem.

Conclusão

Por fim, se você chegou até esta parte do artigo, espero que tenha gostado e caso tenha sugestões, melhorias, pode deixar nos comentários. Agradeço desde já.
Para ilustrar e demonstrar melhor um algoritmo de pesquisa binária, criei um jogo de adivinhação básico que contém algumas dicas e orientações de como chegar no número através da busca binária.
Link do projeto: https://jogo-adivinhacao-five.vercel.app/
Link do repositório no github: https://github.com/Giovanni-786/jogo-adivinhacao.

Referências

O conteúdo desse artigo foi tirado do livro "Entendendo algoritmos - Um guia ilustrado para programadores e outros curiosos", e da aula de busca binária da plataforma Khan academy