Neste artigo, aprenderemos por que todo programador deve aprender estruturas de dados e algoritmos com a ajuda de exemplos.
Este artigo é para aqueles que estão apenas começando a aprender algoritmos e se perguntam como será impactante aumentar suas habilidades de carreira / programação. É também para aqueles que se perguntam por que grandes empresas como Google, Facebook e Amazon contratam programadores que são excepcionalmente bons em otimizar algoritmos.
O que são algoritmos?
Informalmente, um algoritmo nada mais é do que uma menção às etapas para resolver um problema. Eles são essencialmente uma solução.
Por exemplo, um algoritmo para resolver o problema de fatoriais pode ser algo assim:
Problema: Encontre o fatorial de n
Inicializar fato = 1 Para cada valor v no intervalo de 1 a n: Multiplique o fato por v fato contém o fatorial de n
Aqui, o algoritmo é escrito em inglês. Se ele foi escrito em uma linguagem de programação, nós o chamaríamos de código . Aqui está um código para encontrar o fatorial de um número em C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
A programação envolve estruturas de dados e algoritmos. Estruturas de dados são usadas para conter dados enquanto algoritmos são usados para resolver o problema usando esses dados.
Estruturas de dados e algoritmos (DSA) apresenta soluções para problemas padrão em detalhes e oferece uma visão de quão eficiente é usar cada um deles. Também ensina a ciência de avaliar a eficiência de um algoritmo. Isso permite que você escolha o melhor de várias opções.
Uso de estruturas de dados e algoritmos para tornar seu código escalonável
O tempo é precioso.
Suponha que Alice e Bob estejam tentando resolver um problema simples de encontrar a soma dos primeiros 10 11 números naturais. Enquanto Bob escrevia o algoritmo, Alice o implementou provando que era tão simples quanto criticar Donald Trump.
Algoritmo (por Bob)
Inicialize soma = 0 para cada número natural n no intervalo de 1 a 1011 (inclusive): adicione n à soma de soma é sua resposta
Código (por Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice e Bob estão se sentindo eufóricos por poderem construir algo próprio em quase nenhum momento. Vamos entrar em seu espaço de trabalho e ouvir sua conversa.
Alice: Vamos executar este código e descobrir a soma. Bob: Eu executei este código alguns minutos atrás, mas ainda não está mostrando o resultado. O que há de errado com isso?
Ops, algo deu errado! Um computador é a máquina mais determinística. Voltar e tentar executá-lo novamente não ajudará. Então, vamos analisar o que há de errado com esse código simples.
Dois dos recursos mais valiosos para um programa de computador são tempo e memória .
O tempo que o computador leva para executar o código é:
Tempo para executar o código = número de instruções * tempo para executar cada instrução
O número de instruções depende do código que você usou e o tempo gasto para executar cada código depende de sua máquina e compilador.
Neste caso, o número total de instruções executadas (digamos x) são , que éx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Vamos supor que um computador pode executar instruções em um segundo (pode variar dependendo da configuração da máquina). O tempo necessário para executar o código acima éy = 108
Tempo gasto para executar o código = x / y (maior que 16 minutos)
É possível otimizar o algoritmo para que Alice e Bob não tenham que esperar 16 minutos toda vez que executarem esse código?
Tenho certeza que você já adivinhou o método certo. A soma dos primeiros N números naturais é dada pela fórmula:
Soma = N * (N + 1) / 2
Convertê-lo em código se parecerá com isto:
soma int (int N) (retornar N * (N + 1) / 2;)
This code executes in just one instruction and gets the task done no matter what the value is. Let it be greater than the total number of atoms in the universe. It will find the result in no time.
The time taken to solve the problem, in this case, is 1/y (which is 10 nanoseconds). By the way, the fusion reaction of a hydrogen bomb takes 40-50 ns, which means your program will complete successfully even if someone throws a hydrogen bomb on your computer at the same time you ran your code. :)
Note: Computers take a few instructions (not 1) to compute multiplication and division. I have said 1 just for the sake of simplicity.
More on Scalability
Scalability is scale plus ability, which means the quality of an algorithm/system to handle the problem of larger size.
Consider the problem of setting up a classroom of 50 students. One of the simplest solutions is to book a room, get a blackboard, a few chalks, and the problem is solved.
But what if the size of the problem increases? What if the number of students increased to 200?
The solution still holds but it needs more resources. In this case, you will probably need a much larger room (probably a theater), a projector screen and a digital pen.
What if the number of students increased to 1000?
The solution fails or uses a lot of resources when the size of the problem increases. This means, your solution wasn't scalable.
What is a scalable solution then?
Consider a site like Khanacademy, millions of students can see videos, read answers at the same time and no more resources are required. So, the solution can solve the problems of larger size under resource crunch.
If you see our first solution to find the sum of first N natural numbers, it wasn't scalable. It's because it required linear growth in time with the linear growth in the size of the problem. Such algorithms are also known as linearly scalable algorithms.
Our second solution was very scalable and didn't require the use of any more time to solve a problem of larger size. These are known as constant-time algorithms.
Memory is expensive
Memory is not always available in abundance. While dealing with code/system which requires you to store or produce a lot of data, it is critical for your algorithm to save the usage of memory wherever possible. For example: While storing data about people, you can save memory by storing only their age not the date of birth. You can always calculate it on the fly using their age and current date.
Examples of an Algorithm's Efficiency
Here are some examples of what learning algorithms and data structures enable you to do:
Example 1: Age Group Problem
Problems like finding the people of a certain age group can easily be solved with a little modified version of the binary search algorithm (assuming that the data is sorted).
The naive algorithm which goes through all the persons one by one, and checks if it falls in the given age group is linearly scalable. Whereas, binary search claims itself to be a logarithmically scalable algorithm. This means that if the size of the problem is squared, the time taken to solve it is only doubled.
Suppose, it takes 1 second to find all the people at a certain age for a group of 1000. Then for a group of 1 million people,
- the binary search algorithm will take only 2 seconds to solve the problem
- the naive algorithm might take 1 million seconds, which is around 12 days
The same binary search algorithm is used to find the square root of a number.
Example 2: Rubik's Cube Problem
Imagine you are writing a program to find the solution of a Rubik's cube.
This cute looking puzzle has annoyingly 43,252,003,274,489,856,000 positions, and these are just positions! Imagine the number of paths one can take to reach the wrong positions.
Fortunately, the way to solve this problem can be represented by the graph data structure. There is a graph algorithm known as Dijkstra's algorithm which allows you to solve this problem in linear time. Yes, you heard it right. It means that it allows you to reach the solved position in a minimum number of states.
Example 3: DNA Problem
DNA is a molecule that carries genetic information. They are made up of smaller units which are represented by Roman characters A, C, T, and G.
Imagine yourself working in the field of bioinformatics. You are assigned the work of finding out the occurrence of a particular pattern in a DNA strand.
It is a famous problem in computer science academia. And, the simplest algorithm takes the time proportional to
(number of character in DNA strand) * (number of characters in pattern)
A typical DNA strand has millions of such units. Eh! worry not. KMP algorithm can get this done in time which is proportional to
(number of character in DNA strand) + (number of characters in pattern)
The * operator replaced by + makes a lot of change.
Considering that the pattern was of 100 characters, your algorithm is now 100 times faster. If your pattern was of 1000 characters, the KMP algorithm would be almost 1000 times faster. That is, if you were able to find the occurrence of pattern in 1 second, it will now take you just 1 ms. We can also put this in another way. Instead of matching 1 strand, you can match 1000 strands of similar length at the same time.
And there are infinite such stories…
Final Words
Generally, software development involves learning new technologies on a daily basis. You get to learn most of these technologies while using them in one of your projects. However, it is not the case with algorithms.
Se você não conhece bem os algoritmos, não será capaz de identificar se pode otimizar o código que está escrevendo agora. Espera-se que você os conheça com antecedência e os aplique sempre que possível e crítico.
Falamos especificamente sobre a escalabilidade dos algoritmos. Um sistema de software consiste em muitos desses algoritmos. Otimizar qualquer um deles leva a um sistema melhor.
No entanto, é importante observar que essa não é a única maneira de tornar um sistema escalonável. Por exemplo, uma técnica conhecida como computação distribuída permite que partes independentes de um programa sejam executadas em várias máquinas juntas, tornando-o ainda mais escalonável.
