Le temps constant et le temps constant amorti sont-ils effectivement considérés comme équivalents?

J'ai besoin d'écrire une RandomQueue qui permet les ajouts et la suppression aléatoire en temps constant (O (1)).

Ma première pensée a été de le sauvegarder avec une sorte de tableau (j'ai choisi une liste de tableaux), car les tableaux ont un accès constant via un index.

En parcourant la documentation, j'ai réalisé que les ajouts d'ArrayLists sont considérés comme du temps constant amorti, car un ajout peut nécessiter une réallocation du tableau sous-jacent, qui est O (n).

Le temps constant amorti et le temps constant sont-ils effectivement les mêmes, ou dois-je examiner une structure qui ne nécessite pas de réaffectation complète à chaque ajout?

Je pose cette question parce que, outre les structures basées sur les tableaux (qui, pour autant que je sache, auront toujours des ajouts à temps constant amorti), je ne pense à rien qui répondra aux exigences:

• Tout arbre basé aura au mieux un accès O (log n)
• Une liste chaînée pourrait potentiellement avoir des ajouts d'O (1) (si une référence à la queue est conservée), mais une suppression aléatoire devrait être au mieux O (n).

Voici la question complète; au cas où je verrais certains détails importants:

Concevez et implémentez une RandomQueue. Il s'agit d'une implémentation de l'interface Queue dans laquelle l'opération remove () supprime un élément qui est choisi uniformément au hasard parmi tous les éléments actuellement dans la file d'attente. (Considérez une RandomQueue comme un sac dans lequel nous pouvons ajouter des éléments ou atteindre et supprimer aveuglément des éléments aléatoires.) Les opérations add (x) et remove () dans une RandomQueue doivent s'exécuter en temps constant par opération.

Le temps constant amorti peut presque toujours être considéré comme équivalent au temps constant, et sans connaître les spécificités de votre application et le type d'utilisation que vous prévoyez de faire dans cette file d'attente, la plupart des chances sont que vous serez couvert.

Une liste de tableaux a le concept de capacité , qui est fondamentalement égale à la plus grande taille / longueur / nombre d'éléments qui lui ait été demandé jusqu'à présent. Donc, ce qui se passera, c'est qu'au début, la liste des tableaux continuera à se réallouer pour augmenter sa capacité à mesure que vous y ajouterez des éléments, mais à un moment donné, le nombre moyen d'éléments ajoutés par unité de temps correspondra inévitablement au nombre moyen d'éléments supprimé par unité de temps, (sinon vous finiriez par manquer de mémoire de toute façon), point auquel le tableau cessera de se réallouer et tous les ajouts seront respectés à temps constant de O (1).

Cependant, gardez à l'esprit que par défaut, la suppression aléatoire d'une liste de tableaux n'est pas O (1), c'est O (N), car les listes de tableaux déplacent tous les éléments après l'élément supprimé d'une position vers le bas pour prendre la place de l'élément supprimé. article. Pour atteindre O (1), vous devrez remplacer le comportement par défaut pour remplacer l'élément supprimé par une copie du dernier élément de la liste de tableaux, puis supprimer le dernier élément, afin qu'aucun élément ne soit déplacé. Mais alors, si vous faites cela, vous n'avez plus exactement de file d'attente.

La question semble demander spécifiquement un temps constant et non un temps constant amorti . Donc, en ce qui concerne la question citée, non, ils ne sont pas effectivement les mêmes *. Sont-ils cependant dans des applications réelles?

Le problème typique avec une constante amortie est que vous devez parfois payer la dette accumulée. Ainsi, alors que les insertions sont généralement constantes, vous devez parfois subir le surcoût de tout réinsérer lorsqu'un nouveau bloc est alloué.

Lorsque la différence entre le temps constant et le temps constant amorti est pertinente pour une application, cela dépend si cette vitesse très lente occasionnelle est acceptable. Pour un très grand nombre de domaines, cela est généralement correct. Surtout si le conteneur a une taille maximale efficace (comme les caches, les tampons temporaires, les conteneurs de travail), vous ne pouvez effectivement payer leurs coûts qu'une seule fois pendant l'exécution.

En réponse aux applications critiques, ces délais peuvent être inacceptables. Si vous devez respecter une garantie de délai d'exécution, vous ne pouvez pas compter sur un algorithme qui dépassera parfois cela. J'ai déjà travaillé sur de tels projets auparavant, mais ils sont extrêmement rares.

Cela dépend également de la hauteur de ce coût. Les vecteurs ont tendance à bien performer car leur coût de réallocation est relativement faible. Cependant, si vous allez sur la carte de hachage, la réallocation peut être beaucoup plus élevée. Encore une fois, pour la plupart des applications, cela va probablement bien, en particulier les serveurs à durée de vie plus longue avec une limite supérieure sur les éléments du conteneur.

* Il y a cependant un petit problème ici. Pour que tout récipient à usage général soit à temps constant d'insertion, l'une des deux choses doit tenir:

• Le conteneur doit avoir une taille maximale fixe; ou
• vous pouvez supposer que l'allocation de mémoire des éléments individuels est à temps constant.

Cela dépend - selon que vous optimisez le débit ou la latence:

• Les systèmes sensibles à la latence nécessitent des performances cohérentes. Pour un tel scénario, nous devons mettre l'accent sur le comportement le plus défavorable du système. Les exemples sont les systèmes en temps réel doux tels que les jeux qui veulent atteindre un taux de rafraîchissement constant, ou les serveurs Web qui doivent envoyer une réponse dans un certain délai: gaspiller les cycles de CPU est mieux que d'être en retard.
• Les systèmes à débit optimisé ne se soucient pas des blocages occasionnels, tant que la quantité maximale de données peut être traitée à long terme. Ici, nous nous intéressons principalement à la performance amortie. C'est généralement le cas pour le calcul des nombres ou d'autres travaux de traitement par lots.

Notez qu'un système peut avoir différents composants qui doivent être classés différemment. Par exemple, un processeur de texte moderne aurait un thread d'interface utilisateur sensible à la latence, mais des threads optimisés pour le débit pour d'autres tâches telles que la vérification orthographique ou les exportations PDF.

En outre, la complexité algorithmique n'a souvent pas autant d'importance qu'on pourrait le penser: lorsqu'un problème est limité à un certain nombre, les caractéristiques de performances réelles et mesurées sont plus importantes que le comportement «pour un très grand n ».

Si on vous demande un algorithme de "temps constant amorti", votre algorithme peut parfois prendre beaucoup de temps. Par exemple, si vous utilisez std :: vector en C ++, un tel vecteur peut avoir alloué de l'espace pour 10 objets, et lorsque vous allouez le 11ème objet, l'espace pour 20 objets est alloué, 10 objets sont copiés et le 11ème ajouté, ce qui prend beaucoup de temps. Mais si vous ajoutez un million d'objets, vous pouvez avoir 999 980 opérations rapides et 20 opérations lentes, le temps moyen étant rapide.

Si l'on vous demande un algorithme à "temps constant", votre algorithme doit toujours être rapide, pour chaque opération. Ce serait important pour les systèmes en temps réel où vous pourriez avoir besoin d'une garantie que chaque opération est toujours rapide. Le «temps constant» n'est très souvent pas nécessaire, mais ce n'est certainement pas la même chose que le «temps constant amorti».