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

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 dutilisation que vous prévoyez de faire pour cette file dattente, la plupart des chances sont que vous soyez couvert.

Une liste de tableaux a le concept de capacité , qui est fondamentalement égale à la plus grande taille / longueur / nombre déléments qui na jamais été exigé de lui jusquà présent. Donc, ce qui se passera, cest quau début, la liste des tableaux continuera à se réallouer pour augmenter sa capacité au fur et à mesure que vous y ajoutez 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,) à quel point le tableau cessera de se réallouer, et tous les ajouts seront satisfaits à un temps constant de O (1).

Cependant , gardez à lesprit que par défaut, la suppression aléatoire dune liste de tableaux nest pas O (1), mais O (N), car les listes de tableaux déplacent tous les éléments après lélément supprimé dune position vers le bas pour prendre la place de lélément supprimé . 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 quaucun élément ne soit déplacé. Mais alors, si vous faites ça, vous navez plus exactement de file dattente.

Commentaires

• Bon sang, bon point sur les suppressions; Je nai pas ‘ considérer cela. Et comme nous ‘ supprimons des éléments au hasard, cela ne signifie pas ‘ techniquement ‘ De toute façon, ce nest plus une file dattente dans ce sens?
• Oui, cela signifie que vous ne la traitez pas vraiment comme une file dattente. Mais je ne sais pas comment vous comptez trouver les éléments à supprimer. Si votre mécanisme pour les trouver sattend à ce quils soient présents dans la file dattente dans lordre dans lequel ils ont été ajoutés, alors vous navez pas de chance.Si vous ne vous souciez pas de savoir si lordre des éléments est brouillé, alors tout va bien.
• Lattente est que mon RandomQueue implémente le Queue, et pour la méthode remove fournie pour supprimer aléatoirement au lieu de faire sauter la tête, donc il ne devrait pas ‘ Il ny a aucun moyen de se fier à une commande spécifique. Je pense que compte tenu de la nature aléatoire de celui-ci, lutilisateur ne devrait pas ‘ sattendre à ce quil garde un ordre spécifique. Jai cité le devoir dans ma question pour clarification. Merci.
• Oui, il semble que tout ira bien si vous vous assurez que la suppression de l’élément est effectuée comme je l’ai suggéré.
• Une dernière chose si vous ne le faites pas ‘ t lesprit. Jai ‘ y réfléchir plus longuement, et cela ‘ ne semble pas ‘ Il est possible davoir à la fois  » true  » O (1) ajouts et  » true  » O (1) suppression aléatoire; il ‘ sera un compromis entre les 2. Vous avez soit une structure allouée individuellement (comme un tableau) qui permet la suppression mais pas l’addition, soit une structure allouée par blocs comme un Linked- Liste qui donne des ajouts mais pas de suppression. Est-ce vrai? Encore une fois, merci.

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 du monde réel?

Le problème typique avec la constante amortie est que parfois vous devez payer la dette accumulée. Ainsi, bien que les insertions soient généralement constantes, vous devez parfois subir la surcharge de tout réinsérer lorsquun nouveau bloc est alloué.

Où la différence entre le temps constant et le temps constant amorti est pertinente pour une application dépend si cette vitesse très lente occasionnelle est acceptable. Pour un très grand nombre de domaines, cest généralement acceptable. Surtout si le conteneur a une taille maximale effective (comme les caches, les tampons temporaires, les conteneurs de travail), vous ne pourriez effectivement payer les coûts quune seule fois pendant lexécution.

En réponse, les applications critiques peuvent être inacceptables. Si vous êtes tenu de respecter une garantie de délai dexécution à court terme, vous ne pouvez pas compter sur un algorithme qui dépassera parfois cela. Jai déjà travaillé sur de tels projets, mais ils sont extrêmement rares.

Cela dépend aussi du coût réel. Les vecteurs ont tendance à bien fonctionner car leur coût de réaffectation est relativement faible. Cependant, si vous utilisez une carte de hachage, la réallocation peut être beaucoup plus élevée. Mais encore une fois, pour la plupart des applications, cest probablement très bien, en particulier les serveurs plus durables avec une limite supérieure sur les éléments du conteneur.

* Il y a cependant un petit problème ici. Afin de créer un conteneur à usage général être un temps constant pour linsertion lune des deux choses doit tenir:

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

Commentaires

•  » liver server  » semble une formulation étrange à utiliser ici. Voulez-vous dire  » serveur en direct  » peut-être?

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

• Latence- les systèmes sensibles nécessitent des performances constantes. Pour un tel scénario, nous devons mettre laccent sur le comportement du système dans le pire des cas. Des exemples sont des systèmes temps réel souples s les jeux qui veulent atteindre un framerate cohérent, ou les serveurs Web qui doivent envoyer une réponse dans un certain laps de temps: il vaut mieux perdre des cycles de processeur que dêtre en retard.
• Les systèmes à débit optimisé ne se soucient pas des blocages occasionnels, à condition que la quantité maximale de données puisse être traitée à long terme. Ici, nous nous intéressons principalement aux performances amorties. Cest généralement le cas pour le calcul des nombres ou dautres travaux de traitement par lots.

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

De plus, la complexité algorithmique na souvent pas autant dimportance que nous le pourrions pensez: Lorsquun problème est limité à un certain nombre, les caractéristiques de performances réelles et mesurées sont plus importantes que le comportement «pour les très grands n ».

Commentaires

• Malheureusement, jai très peu dexpérience.La question se termine par:  » Les opérations add (x) et remove () dans une RandomQueue doivent sexécuter en temps constant par opération « .
• @Carcigenicate sauf si vous savez avec certitude que le système est sensible à la latence, lutilisation de la complexité amortie pour sélectionner une structure de données devrait être absolument suffisante.
• Jai limpression que cela pourrait être un exercice de programmation ou un test. Et certainement pas facile. Absolument vrai que cela compte très rarement.

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

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