Pourquoi std :: list :: reverse a-t-il une complexité O (n)?

192

Pourquoi la fonction inverse de la std::listclasse dans la bibliothèque standard C ++ a-t-elle une exécution linéaire? Je pense que pour les listes à double liaison, la fonction inverse aurait dû être O (1).

Inverser une liste à double lien devrait simplement impliquer de changer la tête et les pointeurs de queue.

Curieuse
la source
18
Je ne comprends pas pourquoi les gens votent contre cette question. C'est une question parfaitement raisonnable à poser. L'inversion d'une liste doublement liée devrait prendre un temps O (1).
Curieux
46
malheureusement, certaines personnes confondent les concepts de «la question est bonne» avec «la question a une bonne idée». J'adore les questions comme celle-ci, où fondamentalement «ma compréhension semble différente d'une pratique communément acceptée, aidez-nous à résoudre ce conflit», car développer votre façon de penser vous aide à résoudre beaucoup plus de problèmes sur la route! Il semblerait que d'autres adoptent l'approche de "c'est un gaspillage de traitement dans 99,9999% des cas, n'y pensez même pas". Si c'est une consolation, j'ai été critiqué pour beaucoup, beaucoup moins!
corsiKa
4
Oui, cette question a reçu un nombre excessif de votes négatifs pour sa qualité. C'est probablement le même que celui qui a voté pour la réponse de Blindy. En toute honnêteté, "inverser une liste à double chaînage devrait simplement impliquer de changer les pointeurs tête et queue" n'est généralement pas vrai pour la liste chaînée standard implicite que tout le monde apprend au lycée, ou pour de nombreuses implémentations que les gens utilisent. Souvent, dans la réaction instinctive immédiate des SO à la question ou à la réponse, la décision de vote positif / négatif est souvent motivée. Si vous aviez été plus clair dans cette phrase ou si vous l'aviez omise, je pense que vous auriez obtenu moins de votes contre.
Chris Beck
3
Ou laissez-moi mettre le fardeau de la preuve avec vous, @Curious: j'ai créé une implémentation de liste à double lien ici: ideone.com/c1HebO . Pouvez-vous indiquer comment vous vous attendez à ce que la Reversefonction soit implémentée dans O (1)?
CompuChip
2
@CompuChip: En fait, selon l'implémentation, ce n'est peut-être pas le cas. Vous n'avez pas besoin d'un booléen supplémentaire pour savoir quel pointeur utiliser: utilisez simplement celui qui ne pointe pas vers vous ... qui pourrait bien être automatique avec une liste chaînée XOR. Donc oui, cela dépend de la façon dont la liste est mise en œuvre, et la déclaration OP pourrait être clarifiée.
Matthieu M.

Réponses:

187

Hypothétiquement, reverseaurait pu être O (1) . Il pourrait y avoir (encore une fois hypothétiquement) un membre de liste booléenne indiquant si la direction de la liste chaînée est actuellement la même ou opposée à celle d'origine où la liste a été créée.

Malheureusement, cela réduirait les performances de pratiquement toute autre opération (mais sans changer le runtime asymptotique). Dans chaque opération, un booléen devrait être consulté pour déterminer s'il faut suivre un pointeur "suivant" ou "précédent" d'un lien.

Comme cela était vraisemblablement considéré comme une opération relativement peu fréquente, la norme (qui ne dicte pas les implémentations, seulement la complexité), spécifiait que la complexité pouvait être linéaire. Cela permet aux pointeurs "suivants" de toujours signifier la même direction sans ambiguïté, accélérant ainsi les opérations courantes.

Ami Tavory
la source
29
@MooseBoys: Je ne suis pas d'accord avec votre analogie. La différence est que, dans le cas d'une liste, l'implémentation pourrait fournir reversede la O(1)complexité sans affecter le big-o de toute autre opération , en utilisant cette astuce booléenne. Mais, en pratique, une branche supplémentaire dans chaque opération est coûteuse, même si c'est techniquement O (1). En revanche, vous ne pouvez pas créer une structure de liste dans laquelle sortest O (1) et toutes les autres opérations ont le même coût. Le point de la question est que, apparemment, vous pouvez obtenir l' O(1)inverse gratuitement si vous ne vous souciez que du grand O, alors pourquoi n'ont-ils pas fait cela.
Chris Beck
9
Si vous utilisiez une liste liée XOR, l'inversion deviendrait un temps constant. Un itérateur serait cependant plus gros, et l'incrémenter / décrémenter serait légèrement plus coûteux en calcul. Cela pourrait être éclipsé par les accès mémoire inévitables pour tout type de liste liée.
Deduplicator
3
@IlyaPopov: Est-ce que chaque nœud en a réellement besoin? L'utilisateur ne pose jamais de questions au nœud de liste lui-même, uniquement au corps principal de la liste. Ainsi, accéder au booléen est facile pour toute méthode appelée par l'utilisateur. Vous pouvez définir la règle selon laquelle les itérateurs sont invalides si la liste est inversée et / ou stocker une copie du booléen avec l'itérateur, par exemple. Je pense donc que cela n'affecterait pas nécessairement le grand O. J'admets que je n'ai pas parcouru les spécifications ligne par ligne. :)
Chris Beck
4
@Kevin: Hm, quoi? De toute façon, vous ne pouvez pas xor deux pointeurs directement, vous devez d'abord les convertir en entiers (évidemment de type std::uintptr_t. Ensuite, vous pouvez les xor.
Deduplicator
3
@Kevin, vous pourriez certainement créer une liste chaînée XOR en C ++, c'est pratiquement le langage poster-child pour ce genre de chose. Rien ne dit que vous devez utiliser std::uintptr_t, vous pouvez convertir en un chartableau, puis XOR les composants. Ce serait plus lent mais 100% portable. Vous pourriez probablement le faire choisir entre ces deux implémentations et n'utiliser la seconde comme solution de secours que si elle uintptr_test manquante. Certains s'il est décrit dans cette réponse: stackoverflow.com/questions/14243971/…
Chris Beck
61

Ce pourrait être O (1) si la liste stockait un drapeau qui permet d'échanger la signification des pointeurs « prev» et « next» de chaque nœud. Si l'inversion de la liste était une opération fréquente, un tel ajout pourrait en fait être utile et je ne connais aucune raison pour laquelle sa mise en œuvre serait interdite par la norme actuelle. Cependant, avoir un tel drapeau rendrait la traversée ordinaire de la liste plus coûteuse (ne serait-ce que par un facteur constant) car au lieu de

current = current->next;

dans l' operator++itérateur de la liste, vous obtiendrez

if (reversed)
  current = current->prev;
else
  current = current->next;

ce qui n'est pas quelque chose que vous décidez d'ajouter facilement. Étant donné que les listes sont généralement parcourues beaucoup plus souvent qu'elles ne sont inversées, il serait très imprudent pour la norme d' imposer cette technique. Par conséquent, l'opération inverse peut avoir une complexité linéaire. Notez cependant que tO (1) ⇒ tO ( n ) donc, comme mentionné précédemment, implémenter techniquement votre «optimisation» serait autorisé.

Si vous venez d'un environnement Java ou similaire, vous vous demandez peut-être pourquoi l'itérateur doit vérifier l'indicateur à chaque fois. Ne pourrions-nous pas avoir à la place deux types d'itérateurs distincts, tous deux dérivés d'un type de base commun, et avoir std::list::beginet std::list::rbeginrenvoyer de manière polymorphe l'itérateur approprié? Bien que possible, cela rendrait le tout encore pire car l'avancement de l'itérateur serait un appel de fonction indirect (difficile à intégrer) maintenant. En Java, vous payez ce prix régulièrement de toute façon, mais là encore, c'est l'une des raisons pour lesquelles de nombreuses personnes optent pour le C ++ lorsque les performances sont critiques.

Comme le souligne Benjamin Lindley dans les commentaires, puisqu'il reversen'est pas permis d'invalider les itérateurs, la seule approche permise par le standard semble être de stocker un pointeur vers la liste à l'intérieur de l'itérateur ce qui provoque un double accès mémoire indirect.

5gon12eder
la source
7
@galinette: std::list::reversen'invalide pas les itérateurs.
Benjamin Lindley
1
@galinette Désolé, j'ai mal lu votre commentaire précédent comme «indicateur par itérateur » par opposition à «indicateur par nœud » tel que vous l'avez écrit. Bien sûr, un drapeau par nœud serait contre-productif, car vous devrez, encore une fois, effectuer un parcours linéaire pour tous les inverser.
5gon12eder
2
@ 5gon12eder: Vous pouvez éliminer le branchement à un coût très perdu: stockez les pointeurs nextet prevdans un tableau et stockez la direction sous forme de 0ou 1. Pour itérer vers l'avant, vous suivriez pointers[direction]et itéreriez à l'envers pointers[1-direction](ou vice versa). Cela ajouterait encore un tout petit peu de frais généraux, mais probablement moins qu'une branche.
Jerry Coffin
4
Vous ne pouvez probablement pas stocker un pointeur vers la liste à l'intérieur des itérateurs. swap()est spécifié comme étant un temps constant et n'invalide aucun itérateur.
Tavian Barnes
1
@TavianBarnes Bon sang! Eh bien, triple indirection alors ... (je veux dire, pas réellement triple. Vous auriez à stocker le drapeau dans un objet alloué dynamiquement mais le pointeur dans l'itérateur peut bien sûr pointer directement vers cet objet au lieu de diriger vers la liste.)
5gon12eder
37

Puisque tous les conteneurs qui prennent en charge les itérateurs bidirectionnels ont le concept de rbegin () et de rend (), cette question est sans objet?

Il est trivial de créer un proxy qui inverse les itérateurs et d'accéder au conteneur via cela.

Cette non-opération est bien O (1).

tel que:

#include <iostream>
#include <list>
#include <string>
#include <iterator>

template<class Container>
struct reverse_proxy
{
    reverse_proxy(Container& c)
    : _c(c)
    {}

    auto begin() { return std::make_reverse_iterator(std::end(_c)); }
    auto end() { return std::make_reverse_iterator(std::begin(_c)); }

    auto begin() const { return std::make_reverse_iterator(std::end(_c)); }
    auto end() const { return std::make_reverse_iterator(std::begin(_c)); }

    Container& _c;
};

template<class Container>
auto reversed(Container& c)
{
    return reverse_proxy<Container>(c);
}

int main()
{
    using namespace std;
    list<string> l { "the", "cat", "sat", "on", "the", "mat" };

    auto r = reversed(l);
    copy(begin(r), end(r), ostream_iterator<string>(cout, "\n"));

    return 0;
}

production attendue:

mat
the
on
sat
cat
the

Compte tenu de cela, il me semble que le comité des normes n'a pas pris le temps de mandater O (1) l'ordre inverse du conteneur parce que ce n'est pas nécessaire, et la bibliothèque standard est en grande partie construite sur le principe de ne rendre obligatoire que ce qui est strictement nécessaire tout en éviter la duplication.

Juste mon 2c.

Richard Hodges
la source
18

Parce qu'il doit traverser chaque nœud ( ntotal) et mettre à jour leurs données (l'étape de mise à jour l'est en effet O(1)). Cela rend l'opération entière O(n*1) = O(n).

Aveugle
la source
27
Parce que vous devez également mettre à jour les liens entre chaque élément. Prenez un morceau de papier et tirez-le au lieu de voter contre.
Blindy
11
Pourquoi demander si vous êtes si sûr alors? Vous perdez notre temps à la fois.
Blindy
28
@Curious Les nœuds de la liste à double chaînage ont un sens de l'orientation. Raison à partir de là.
Chaussure du
11
@Blindy Une bonne réponse doit être complète. "Sortez un morceau de papier et tirez-le" ne devrait donc pas être un élément indispensable d'une bonne réponse. Les réponses qui ne sont pas de bonnes réponses sont sujettes à des votes négatifs.
RM
7
@Shoe: Est-ce qu'ils doivent le faire? Veuillez rechercher la liste liée XOR et autres.
Deduplicator
2

Il échange également le pointeur précédent et suivant pour chaque nœud. C'est pourquoi il faut Linear. Bien que cela puisse être fait dans O (1) si la fonction utilisant ce LL prend également des informations sur LL comme entrée, comme si elle accède normalement ou inversement.

techcomp
la source
1

Seulement une explication d'algorithme. Imaginez que vous avez un tableau avec des éléments, alors vous devez l'inverser. L'idée de base est d'itérer sur chaque élément en changeant l'élément de la première position en dernière position, l'élément en seconde position en avant-dernière position, et ainsi de suite. Lorsque vous atteignez le milieu du tableau, vous aurez tous les éléments modifiés, donc en (n / 2) itérations, ce qui est considéré comme O (n).

danilobraga
la source
1

C'est O (n) simplement parce qu'il doit copier la liste dans l'ordre inverse. Chaque opération d'élément individuel est O (1) mais il y en a n dans la liste entière.

Bien sûr, il y a des opérations à temps constant impliquées dans la configuration de l'espace pour la nouvelle liste, et le changement des pointeurs par la suite, etc. La notation O ne prend pas en compte les constantes individuelles une fois que vous avez inclus un facteur n de premier ordre.

SDsolar
la source