Dans cet article, nous allons apprendre pourquoi chaque programmeur devrait apprendre les structures de données et les algorithmes à l'aide d'exemples.
Cet article s'adresse à ceux qui viennent de commencer à apprendre les algorithmes et se demandent à quel point il sera important de booster leur carrière / leurs compétences en programmation. C'est également pour ceux qui se demandent pourquoi de grandes entreprises comme Google, Facebook et Amazon embauchent des programmeurs exceptionnellement doués pour optimiser les algorithmes.
Que sont les algorithmes?
De manière informelle, un algorithme n'est rien d'autre qu'une mention des étapes pour résoudre un problème. Ils sont essentiellement une solution.
Par exemple, un algorithme pour résoudre le problème des factorielles pourrait ressembler à ceci:
Problème: trouver la factorielle de n
Initialize fact = 1 Pour chaque valeur v comprise entre 1 et n: Multipliez le fait par v fact contient la factorielle de n
Ici, l'algorithme est écrit en anglais. S'il était écrit dans un langage de programmation, nous l'appellerions plutôt coder . Voici un code pour trouver la factorielle d'un nombre en C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
La programmation concerne les structures de données et les algorithmes. Les structures de données sont utilisées pour contenir des données tandis que des algorithmes sont utilisés pour résoudre le problème en utilisant ces données.
Les structures de données et les algorithmes (DSA) étudient en détail les solutions aux problèmes standard et vous donnent un aperçu de l'efficacité de l'utilisation de chacun d'entre eux. Il vous apprend également la science de l'évaluation de l'efficacité d'un algorithme. Cela vous permet de choisir le meilleur des différents choix.
Utilisation de structures de données et d'algorithmes pour rendre votre code évolutif
Le temps est precieux.
Supposons qu'Alice et Bob essaient de résoudre un problème simple de trouver la somme des 10 11 premiers nombres naturels. Pendant que Bob écrivait l'algorithme, Alice l'a implémenté, prouvant que c'est aussi simple que de critiquer Donald Trump.
Algorithme (par Bob)
Initialiser la somme = 0 pour chaque nombre naturel n compris entre 1 et 1011 (inclus): ajouter n à la somme somme est votre réponse
Code (par Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice et Bob se sentent euphoriques d'eux-mêmes, car ils pourraient construire quelque chose de leur propre chef en un rien de temps. Faufilons-nous dans leur espace de travail et écoutons leur conversation.
Alice: Lançons ce code et trouvons la somme. Bob: J'ai exécuté ce code il y a quelques minutes mais il ne montre toujours pas la sortie. Qu'est ce qui ne va pas avec ça?
Oups, un problème est survenu! Un ordinateur est la machine la plus déterministe. Revenir en arrière et essayer de l'exécuter à nouveau n'aidera pas. Analysons donc ce qui ne va pas avec ce code simple.
Deux des ressources les plus précieuses pour un programme informatique sont le temps et la mémoire .
Le temps mis par l'ordinateur pour exécuter le code est:
Temps d'exécution du code = nombre d'instructions * temps d'exécution de chaque instruction
Le nombre d'instructions dépend du code que vous avez utilisé et le temps nécessaire pour exécuter chaque code dépend de votre machine et de votre compilateur.
Dans ce cas, le nombre total d'instructions exécutées (disons x) est , qui estx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Supposons qu'un ordinateur puisse exécuter des instructions en une seconde (cela peut varier en fonction de la configuration de la machine). Le temps nécessaire pour exécuter le code ci-dessus esty = 108
Temps nécessaire pour exécuter le code = x / y (supérieur à 16 minutes)
Est-il possible d'optimiser l'algorithme pour qu'Alice et Bob n'aient pas à attendre 16 minutes à chaque fois qu'ils exécutent ce code?
Je suis sûr que vous avez déjà deviné la bonne méthode. La somme des N premiers nombres naturels est donnée par la formule:
Somme = N * (N + 1) / 2
Le convertir en code ressemblera à ceci:
int sum (int N) (retourne N * (N + 1) / 2;)
Ce code s'exécute en une seule instruction et accomplit la tâche quelle que soit la valeur. Laissez-le être supérieur au nombre total d'atomes dans l'univers. Il trouvera le résultat en un rien de temps.
Le temps nécessaire pour résoudre le problème, dans ce cas, est de 1/y(qui est de 10 nanosecondes). À propos, la réaction de fusion d'une bombe à hydrogène prend 40 à 50 ns, ce qui signifie que votre programme se terminera avec succès même si quelqu'un jette une bombe à hydrogène sur votre ordinateur en même temps que vous exécutez votre code. :)
Remarque: les ordinateurs prennent quelques instructions (pas 1) pour calculer la multiplication et la division. J'ai dit 1 juste par souci de simplicité.
En savoir plus sur l'évolutivité
L'évolutivité est l'échelle plus la capacité, ce qui signifie la qualité d'un algorithme / système pour gérer le problème de plus grande taille.
Considérez le problème de la mise en place d'une classe de 50 élèves. L'une des solutions les plus simples est de réserver une chambre, d'obtenir un tableau noir, quelques craies et le problème est résolu.
Mais que faire si la taille du problème augmente? Et si le nombre d'étudiants passait à 200?
La solution tient toujours mais elle a besoin de plus de ressources. Dans ce cas, vous aurez probablement besoin d'une salle beaucoup plus grande (probablement un théâtre), d'un écran de projection et d'un stylo numérique.
Et si le nombre d'étudiants passait à 1000?
La solution échoue ou utilise beaucoup de ressources lorsque la taille du problème augmente. Cela signifie que votre solution n'était pas évolutive.
Qu'est-ce qu'une solution évolutive alors?
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.
Si vous ne connaissez pas bien les algorithmes, vous ne pourrez pas déterminer si vous pouvez optimiser le code que vous écrivez en ce moment. On s'attend à ce que vous les connaissiez à l'avance et que vous les appliquiez dans la mesure du possible et de manière critique.
Nous avons spécifiquement parlé de l'évolutivité des algorithmes. Un système logiciel se compose de nombreux algorithmes de ce type. Optimiser l'un d'entre eux conduit à un meilleur système.
Cependant, il est important de noter que ce n'est pas le seul moyen de rendre un système évolutif. Par exemple, une technique connue sous le nom de calcul distribué permet à des parties indépendantes d'un programme de s'exécuter sur plusieurs machines ensemble, ce qui le rend encore plus évolutif.
