Chaîne C ++ :: trouver la complexité

Pourquoi le c++de mise en œuvre string::find() ne pas utiliser le Algorithme KMP (et ne fonctionne pas dans O(N + M)) et s'exécute en O(N * M)? Est que les corrigés en C++0x?
Si la complexité de courant de trouver n'est pas O(N * M), c'est quoi?

PS:
Désolé je veux dire string::find()

de sorte que l'algorithme est mis en œuvre dans gcc? c'est que KMP? si non, pourquoi?
Je l'ai testé et le temps d'exécution montre qu'il fonctionne dans O(N * M)

source d'informationauteur Farzam

  1. 27

    Pourquoi le c++de mise en œuvre de la chaîne::substr() n'utilise pas l'algorithme KMP (et ne pas s'exécuter en O(N + M)) et s'exécute en O(N * M)?

    Je suppose que vous voulez dire find()plutôt que de substr() qui n'a pas besoin de rechercher et d'effectuer en temps linéaire (et seulement parce qu'il a copier le résultat dans une chaîne de caractères).

    La norme C++ ne précise pas les détails de l'implémentation, et ne spécifie des exigences de complexité dans certains cas. Les seules exigences de complexité sur std::string opérations sont que size()max_size()operator[]swap()c_str() et data() sont tous à temps constant. La complexité de quoi que ce soit d'autre dépend des choix effectués par quiconque en œuvre de la bibliothèque que vous utilisez.

    La raison la plus probable pour le choix d'une simple recherche sur quelque chose comme KMP est d'éviter d'avoir besoin de stockage supplémentaire. À moins que la chaîne est très longue, et la chaîne à rechercher contient beaucoup de correspondances partielles, le temps pris pour allouer et libérer qui serait susceptible d'être beaucoup plus que le coût de la complexité supplémentaire.

    Est corrigé dans c++0x?

    Non, C++11 ne pas ajouter de la complexité des exigences de std::stringet certainement ne pas ajouter de mise en œuvre obligatoire de détails.

    Si la complexité de l'actuelle substr n'est pas en O(N * M), ce qui est?

    C'est le pire des cas, la complexité, lorsque la chaîne de caractères à rechercher contient beaucoup de correspondances partielles. Si les personnages ont un raisonnablement uniforme de la distribution, alors la moyenne de la complexité serait plus proche de O(N). Ainsi en choisissant un algorithme avec une meilleure pire-la complexité de l'affaire, vous pouvez bien faire plus de cas typiques de beaucoup plus lent.

  2. 7

    Où obtenez-vous l'impression de que std::string::substr() ne pas utiliser un algorithme linéaire? En fait, je ne peux même pas imaginer comment mettre en œuvre d'une manière qui a la complexité que vous avez cité. Aussi, il n'y a pas beaucoup d'un algorithme impliqués: est-il possible que vous pensez que cette fonction n'est autre chose qu'il fait? std::string::substr() crée une nouvelle chaîne de caractères à partir de son premier argument et en utilisant soit le nombre de caractères spécifié par le deuxième paramètre ou les caractères jusqu'à la fin de la chaîne.

    Vous pouvez peut-être se référant à std::string::find() qui n'a pas toute la complexité des exigences ou des std::search() qui est en effet autorisé à le faire en O(n * m) comparaisons. Cependant, c'est un donnant les responsables de l'implémentation de la liberté de choisir entre un algorithme qui a le plus théorique de la complexité par rapport à un qui n'a pas n'a pas besoin de mémoire supplémentaire. Depuis l'attribution de l'arbitraire des quantités de mémoire est généralement pas souhaitable, sauf sur demande expresse, cela semble une chose raisonnable à faire.

  3. 2

    Pour info,
    Le string::trouver dans les deux gcc/libstdc++ et llvm/libcxx étaient très lents. Il a été amélioré de façon très significative par 20x dans certains cas. Vous voudrez peut-être consulter la nouvelle de la mise en œuvre:

    GCC: PR66414 optimiser std::string::find
    https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65

    LLVM: https://reviews.llvm.org/D27068

  4. 1

    La norme C++ ne dicte pas les caractéristiques de performance de substr (ou de plusieurs autres parties, y compris le find vous êtes plus susceptible de référence avec un M*N complexité).

    Surtout dicte fonctionnelle les aspects de la langue (à quelques exceptions près, comme les non-legacy sort fonctions, par exemple).

    Implémentations sont gratuits à mettre en œuvre qsort comme un tri à bulles (mais seulement si elles veulent être ridiculisé et éventuellement aller hors de l'entreprise).

    Par exemple, il y a seulement sept (très petit) sous-points dans la section 21.4.7.2 basic_string::find de C++11, et aucun de leur spécifier les paramètres de performance.

  5. 1

    Regardons vers le PLC livre. Sur la page 989 de la troisième édition, nous avons l'exercice suivant:

    Supposons que le pattern P et le texte T sont choisis au hasard, les chaînes de
    longueur m et n, respectivement, de la d-ary alphabet
    Ʃd = {0; 1; ...; d}, où j >= 2. Montrer que l'
    nombre de personnage à personnage à des comparaisons faites par le
    boucle implicite à la ligne 4 de l'algorithme naïf est
    Chaîne C ++ :: trouver la complexité

    sur toutes les exécutions de cette boucle. (Supposons que l'algorithme naïf
    s'arrête la comparaison des caractères pour un shift une fois qu'il trouve une incompatibilité
    ou correspond à l'ensemble du motif.) Ainsi, pour choisis au hasard, les cordes, les
    naïfs algorithme est très efficace    .

    NAIVE-STRING-MATCHER(T,P)
1 n = T:length
2 m = P:length
3 for s = 0 to n - m
4     if P[1..m] == T[s+1..s+m]
5         print “Pattern occurs with shift” s

    Preuve:

    Pour un seul quart de travail nous attend pour 1 + 1/d + ... + 1/d^{m-1} comparaisons. Maintenant utiliser la formule de sommation et de le multiplier par le nombre de quarts de travail, qui est n - m + 1.

  6. 0

    Où tenez-vous vos informations sur la bibliothèque C++? Si vous ne signifie string::search et il n'a pas vraiment d'utiliser l'algorithme KMP, alors je suggère que c'est parce que l'algorithme n'est pas généralement plus rapide qu'une simple recherche linéaire due à la construction d'une correspondance partielle de la table avant que la recherche puisse continuer.