Ist die Verwendung von strlen() in der loop-Bedingung langsamer als nur die überprüfung für das null-Zeichen?

Habe ich gelesen, dass die Verwendung von strlen teurer ist als in solchen Tests wie dieser:

Wir haben einen string x 100 Zeichen lang sein.

Ich denke, dass

for (int i = 0; i < strlen(x); i++)

ist teurer als dieser code:

for (int i = 0; x[i] != '\0'; i++)

Ist es wahr? Vielleicht ist der zweite code funktioniert nicht in manchen situation ist es also besser, das erste?

Wird es besser sein, mit den unten?

for (char *tempptr = x; *tempptr != '\0'; tempptr++)
die zweite Schleife in etwa das tut, was strlen hat intern; dennoch sehe ich nicht den Punkt der Frage
Schreiben und testen es. Metriken sind der beste Weg, zu wissen, was besser ist.
Wenn Sie verbringen Zeit und Mühe, sich Gedanken über Dinge wie diese, Sie können Geld sparen durch den Kauf einen schnelleren computer.
mögliche Duplikate von strlen hier berechnet werden mehrmals verwenden?

InformationsquelleAutor dato datuashvili | 2010-08-02

  1. 27
    for (int i=0;i<strlen(x);i++)

    Dieser code ruft strlen(x) jeder iteration. Also, wenn x Länge 100, strlen(x) aufgerufen wird 100 mal. Das ist sehr teuer. Auch strlen(x) ist auch der Iteration über x jedes mal in der gleichen Weise, dass deine for-Schleife macht. Dies macht es O(n^2) Komplexität.

    for (int i=0;x[i]!='\0';i++)

    Dieser code ruft keine Funktionen, so wird Sie viel schneller, als im vorangegangenen Beispiel. Da durchläuft er die Schleife nur einmal, es ist O(n) Komplexität.

    Obwohl es ist nichts falsch in der Antwort, wieder gibt es keinen Punkt im Vergleich der beiden Versionen, da Sie nicht zwei verschiedene Versionen des gleichen Algorithmus. Sie sind nur zwei Beispiel-codes, verschiedene Dinge zu tun
    Diese Methoden können zu einem anderen Ergebnis, wenn die Länge des Strings ändert sich während der iteration, andernfalls werden Sie das gleiche tun.
    Die meisten Compiler (einschließlich gcc) sind schlau genug, um cache das Ergebnis von strlen, also wird die Leistung so ziemlich das gleiche für beide Schleifen.
    R: Der zweite wird immer noch schneller, als strlen iteriert einmal, dann die OP geht wieder in seine Schleife, während in der zweiten Schleife es gibt nur eine iteration. Doch auf der Skala der Dinge, es ist eine ziemlich micro-Optimierung.
    Sind Sie sicher, dass GCC das in allen Fällen? Es hat keine Möglichkeit zu wissen, was passieren wird, wenn mehrere threads und einen globalen string; einem anderen thread könnte die Zeichenfolge ändern, während es eine Schleife. Oder vielleicht ist es auch nicht tun, die Optimierung, wenn Sie einen globalen string.

    InformationsquelleAutor MatthewD

  2. 11

    Den ersten code überprüft die Länge von x in jeder iteration i und es dauert O(n) zu finden, die Letzte 0, also O(n^2), der zweite Fall ist O(n)

    also sind die Leute glücklich Abstimmung, weil O(n^2) > O(n) ? 😉
    Pakosz bitte helfen Sie mir weil ich nicht weiß, auch Unterschied zwischen Ihnen, also warum so wütend ?ich bin glücklich, denn Sie helfen mir nicht, weil der upvoting
    Ich bin nicht wütend, ich bin helfen Sie, indem Sie erkennen, Ihre Frage ist keine echte Frage, und daher ist dies nicht eine "wirkliche Antwort", obwohl es ist nichts falsch in dem, was @Artjom sagte
    Ich sehe nicht, was falsch mit dieser Antwort.

    InformationsquelleAutor Artyom

  3. 4

    Ja Ihre zweite funktioniert möglicherweise nicht 100% Prozent der Zeit, aber es wäre ganz leicht. Dies ist, weil bei der Verwendung von strlen() müssen Sie die Methode aufrufen, jedes mal. Ein besserer Weg wäre, wie so

    int strLength = strlen(x);
for (int i = 0; i < strLength; i++)

    Hoffe, das hilft.

    Faszinierend. Was ist das Szenario, das Sie im Auge haben, in denen die zweite version funktioniert nicht, aber die erste tut? (Vorausgesetzt, der erstellte loop-Inhalt enthalten, werden keine weiteren änderungen der i oder den string.)
    wenn der Körper der Schleife die Länge des Strings ...
    zum Beispiel einen string der "Welt am besten ist" was ist ' Sie '?
    ist ein Platz, nicht ein null-Zeichen
    Lesen Sie die Annahme erklärt in meinem Kommentar. Wenn man bedenkt, dass Ash ' s Vorschlag unterscheidet sich auch von der OP die erste version, wenn der Körper der Schleife ändert die Länge des Strings, wird davon ausgegangen, dass er hatte etwas anderes im Sinn, indem Sie "Ihre zweite funktioniert möglicherweise nicht 100% Prozent der Zeit". (Wirklich alle Wetten sind aus, durch die Schleife weggelassen Inhalt... aber die Frage ist doch nur interessant, wenn die Schleife nicht die Zeichenfolge ändern oder weiter Bearbeiten i, so dass ich denke, es ist nicht unvernünftig anzunehmen, die für die Zwecke der Diskussion, dass das der Fall ist.)

    InformationsquelleAutor Ash Burlaczenko

  4. 2

    Wenn keine es gibt keine Zusammenstellung Optimierung. Ja, weil strlen iteriert über jedes byte der string jedes mal und die zweite Umsetzung wird es tun, nur einmal.

    InformationsquelleAutor Eric Fortin

  5. 2

    Ich denke, der compiler könnte optimieren (check Gregory Pakosz Kommentar) die erste for-Schleife, so dass Sie würde wie folgt Aussehen:

    int len = strlen(x);
for (int i = 0; i < len; i++)

    Ist noch O(n).

    Jedenfalls denke ich, dass deine zweite for Schleife schneller sein wird.

    ja, aber 2*O(n), während die zweite 1*O(n).
    Der compiler kann nicht verschieben Sie die strlen () - Aufruf aus der Schleife, es sei denn, er weiß, dass strlen() hat keine Nebenwirkungen und dass die Länge des Strings nicht ändern können innerhalb der Schleife.
    tatsächlich GCC optimieren können strlen aus der Schleife, da ist es anerkannt als eine built-in Funktion finden Sie unter ridiculousfish.com/blog/archives/2010/07/23/will-it-optimize
    Aber es ist nicht 2*O(n) es O(n**2). Es läuft eine O(n) jede iteration für n Iterationen.
    McClelland Äh, Nein? Wenn die strlen optimiert ist, aus der Schleife, ist es einmal ausgeführt, so dass es nur bedeutet, dass O(n) - operation, und dann der loop, einem weiteren O(n) - operation, da es nur einen Vergleich zu tun, jetzt. Hast du eigentlich die Antwort Lesen?

    InformationsquelleAutor

  6. 2

    Kann ich annehmen, dass in der ersten Variante finden Sie strlen jeder iteration, während in der zweiten Variante, die Sie nicht tun.

    Versuchen Sie, diese zu überprüfen: 

    int a = strlen(x); 
for (int i = 0; i < a; i++) {...}

    InformationsquelleAutor foret

  7. 0

    Natürlich die erste dauert länger als das zweite. Sie eigentlich gar nicht tun, die gleiche Sache überhaupt-die erste ist die Berechnung der Länge der Zeichenfolge jedes mal; die zweite ist (effektiv), tun es nur einmal.

    Die erste version entspricht:

    for (int i=0; x[i] != 0; i++)
  for (int j=0; j<i; j++)
    ;

    Vielleicht haben Sie gedacht, zu sagen, "ist es effizienter zu nennen, eine Bibliothek strlen() als Implementierung meines eigenen?" Die Antwort ist, natürlich, "es hängt". Dein compiler kann intrinsisch Versionen von strlen (), die optimiert sind und darüber hinaus, was Sie erwarten würden von Quelle, können Sie auf eine Plattform, auf der die Funktionsaufrufe sind teuer (heute selten), etc.

    Die einzige Antwort, die sowohl die Allgemeine und richtige ist "- Profil und finden Sie heraus".

    InformationsquelleAutor Tim Lesher

  8. 0

    Es ist erwähnenswert, dass Sie möglicherweise öffnen sich bis zu buffer-overflow-Probleme, wenn Sie nicht auch testen, den index mit der Größe des Puffers mit der Zeichenkette. Je nachdem, was du tust mit diesem code, dies kann oder kann nicht eine praktische Angelegenheit, aber es nur selten tut weh, zusätzliche Kontrollen, und es ist eine gute Angewohnheit, in zu erhalten.

    Ich würde vorschlagen:
    for (i = 0; i < buf_size && x[i] != '\0'; i++)

    Wo:

    • buf_size ist die vorbestimmte Größe des Puffers. Wenn x ist ein array, dieses wird sizeof(x); wenn x ist ein Zeiger, sollten Sie die Puffer-Größe zur Verfügung.
    • Habe ich entfernt, die Erklärung der i aus der Schleife, da es nur gültig c99. Wenn Sie nur die Kompilierung unter c99, fühlen Sie sich frei, um es wieder in.

    InformationsquelleAutor Thom Smith

Schreibe einen Kommentar