Algorithme en place - In-place algorithm

En informatique , un algorithme en place est un algorithme qui transforme l'entrée en n'utilisant aucune structure de données auxiliaire . Cependant, une petite quantité d'espace de stockage supplémentaire est autorisée pour les variables auxiliaires. L'entrée est généralement écrasée par la sortie lors de l'exécution de l'algorithme. Un algorithme sur place met à jour sa séquence d'entrée uniquement par le remplacement ou l'échange d'éléments. Un algorithme qui n'est pas en place est parfois appelé not-in-place ou out-of-place .

En place peut avoir des significations légèrement différentes. Dans sa forme la plus stricte, l'algorithme ne peut avoir qu'une quantité constante d'espace supplémentaire , en comptant tout, y compris les appels de fonction et les pointeurs . Cependant, cette forme est très limitée car le simple fait d'avoir un index sur un tableau de longueur n nécessite O (log n ) bits. Plus généralement, sur place signifie que l'algorithme n'utilise pas d'espace supplémentaire pour manipuler l'entrée, mais peut nécessiter un espace supplémentaire petit mais non constant pour son fonctionnement. Habituellement, cet espace est O (log n ) , bien que parfois tout ce qui se trouve en O ( n ) soit autorisé. Notez que la complexité de l'espace a également des choix variés pour compter ou non les longueurs d'index dans le cadre de l'espace utilisé. Souvent, la complexité spatiale est donnée en termes de nombre d'indices ou de pointeurs nécessaires, sans tenir compte de leur longueur. Dans cet article, nous nous référons à la complexité spatiale totale ( DSPACE ), en comptant les longueurs de pointeur. Par conséquent, les besoins en espace ici ont un facteur log n supplémentaire par rapport à une analyse qui ignore la longueur des index et des pointeurs.

Un algorithme peut ou non compter la sortie dans le cadre de son utilisation de l'espace. Étant donné que les algorithmes sur place écrasent généralement leur entrée avec la sortie, aucun espace supplémentaire n'est nécessaire. Lors de l'écriture de la sortie dans la mémoire en écriture seule ou dans un flux, il peut être plus approprié de ne considérer que l'espace de travail de l'algorithme. Dans les applications théoriques telles que les réductions d'espace log , il est plus courant de toujours ignorer l'espace de sortie (dans ces cas, il est plus essentiel que la sortie soit en écriture seule ).

Exemples

Étant donné un tableau a de n éléments, supposons que nous voulions un tableau contenant les mêmes éléments dans l'ordre inverse et se débarrassant de l'original. Une façon apparemment simple de le faire est de créer un nouveau tableau de taille égale, de le remplir avec des copies adans l'ordre approprié, puis de supprimer a.

 function reverse(a[0..n - 1])
     allocate b[0..n - 1]
     for i from 0 to n - 1
         b[n − 1 − i] := a[i]
     return b

Malheureusement, cela nécessite O ( n ) d'espace supplémentaire pour avoir les tableaux aet bdisponibles simultanément. De plus, l' allocation et la désallocation sont souvent des opérations lentes. Puisque nous n'avons plus besoin de a, nous pouvons à la place l'écraser avec son propre inversion en utilisant cet algorithme sur place qui n'aura besoin que d'un nombre constant (2) d'entiers pour les variables auxiliaires iet tmp, quelle que soit la taille du tableau.

 function reverse_in_place(a[0..n-1])
     for i from 0 to floor((n-2)/2)
         tmp := a[i]
         a[i] := a[n − 1 − i]
         a[n − 1 − i] := tmp

Autre exemple, de nombreux algorithmes de tri réorganisent les tableaux dans un ordre de tri sur place, notamment : bubble sort , comb sort , selection sort , insertion sort , heapsort et Shell sort . Ces algorithmes ne nécessitent que quelques pointeurs, leur complexité spatiale est donc de O (log n ) .

Quicksort opère en place sur les données à trier. Cependant, quicksort nécessite des pointeurs d'espace de pile O (log n ) pour garder une trace des sous-tableaux dans sa stratégie de division pour régner . Par conséquent, le tri rapide nécessite O (log ² n ) d' espace supplémentaire. Bien que cet espace non constant enlève techniquement le tri rapide de la catégorie sur place, le tri rapide et d'autres algorithmes ne nécessitant que des pointeurs supplémentaires O (log n ) sont généralement considérés comme des algorithmes sur place.

La plupart des algorithmes de sélection sont également en place, bien que certains réorganisent considérablement le tableau d'entrée dans le processus de recherche du résultat final de taille constante.

Certains algorithmes de manipulation de texte tels que le rognage et l'inversion peuvent être effectués sur place.

Dans la complexité de calcul

Dans la théorie de la complexité computationnelle , la définition stricte des algorithmes en place inclut tous les algorithmes de complexité spatiale O (1) , la classe DSPACE (1). Cette classe est très limitée; il est égal aux langues régulières . En fait, il n'inclut même aucun des exemples énumérés ci-dessus.

Nous considérons généralement que les algorithmes de L , la classe de problèmes nécessitant O (log n ) d' espace supplémentaire, sont en place. Cette classe est plus conforme à la définition pratique, car elle permet des nombres de taille n comme pointeurs ou indices. Cette définition élargie exclut toujours le tri rapide, cependant, en raison de ses appels récursifs.

L'identification des algorithmes en place avec L a des implications intéressantes ; par exemple, cela signifie qu'il existe un algorithme en place (plutôt complexe) pour déterminer si un chemin existe entre deux nœuds dans un graphe non orienté , un problème qui nécessite O ( n ) d'espace supplémentaire en utilisant des algorithmes typiques tels que la recherche en profondeur d'abord (un bit visité pour chaque nœud). Cela produit à son tour des algorithmes sur place pour des problèmes tels que déterminer si un graphique est bipartite ou tester si deux graphiques ont le même nombre de composants connectés . Voir SL pour plus d'informations.

Rôle du hasard

Dans de nombreux cas, les besoins en espace d'un algorithme peuvent être considérablement réduits en utilisant un algorithme aléatoire . Par exemple, disons que nous souhaitons savoir si deux sommets d'un graphe de n sommets sont dans la même composante connexe du graphe. Il n'y a pas d'algorithme simple, déterministe, en place pour déterminer cela, mais si nous commençons simplement à un sommet et effectuons une marche aléatoire d'environ 20 n ³ étapes, la chance que nous tombions sur l'autre sommet à condition qu'il soit dans le même composant est très élevé. De même, il existe des algorithmes aléatoires simples sur place pour les tests de primalité tels que le test de primalité de Miller-Rabin , et il existe également des algorithmes simples de factorisation aléatoire sur place tels que l'algorithme rho de Pollard . Voir RL et BPL pour plus de détails sur ce phénomène.

En programmation fonctionnelle

Les langages de programmation fonctionnels découragent souvent ou ne prennent pas en charge les algorithmes explicites sur place qui écrasent les données, car il s'agit d'un type d' effet secondaire ; au lieu de cela, ils permettent seulement de construire de nouvelles données. Cependant, les bons compilateurs de langage fonctionnel reconnaîtront souvent lorsqu'un objet très similaire à un objet existant est créé, puis l'ancien est jeté, et optimiseront cela en une simple mutation "sous le capot".

Notez qu'il est possible en principe de construire soigneusement des algorithmes en place qui ne modifient pas les données (sauf si les données ne sont plus utilisées), mais cela est rarement fait en pratique. Voir les structures de données purement fonctionnelles .

Voir également

• Tableau des algorithmes de tri sur place et non sur place

Les références