Wie berechnet man die Länge einer Zeichenfolge in C effizient?

Lesezeit: 4 Minuten

Benutzer-Avatar
Carla Alvarez

Wie berechnet man die Länge einer Zeichenfolge in C effizient (zeitlich)?

Ich mache gerade:

int calculate_length(char *string) {
    int length = 0;
    while (string[length] != '\0') {
        length++;
    }
    return length;
}

Aber es ist sehr langsam im Vergleich zu strlen() zum Beispiel, gibt es eine andere Möglichkeit, dies zu tun?

Vielen Dank.

BEARBEITEN: Ich arbeite in einer freistehenden Umgebung, ich darf keine externe Bibliothek verwenden, einschließlich “string.h”.

  • Warum dann nicht strlen verwenden? Oder ist das eine Übung?

    – SamPost

    15. Januar 2010 um 9:41 Uhr

  • Es ist keine Übung, die Umgebung, in der ich arbeite, erlaubt es mir nicht, andere “libs”, einschließlich “string.h”, einzubinden, also muss ich es implementieren und möchte, dass es so effizient wie möglich und gleichzeitig wartbar ist .

    – Carla Alvarez

    15. Januar 2010 um 9:46 Uhr

  • Möglicherweise möchten Sie Ihren ursprünglichen Beitrag bearbeiten, um zu erwähnen, dass Sie sich in einer freistehenden Umgebung befinden.

    – Matthäus Iselin

    15. Januar 2010 um 9:53 Uhr

  • Berücksichtigen Sie, dass die std-Bibliothek auch mit aktivierten Compiler-Optimierungen kompiliert werden kann und Ihr Code dies nicht tut.

    – Khelben

    15. Januar 2010 um 10:02 Uhr

  • Hier gibt es ausgezeichnete Antworten, aber denken Sie daran, dass dies eine Mikrooptimierung ist und nicht alle Programmierer die Verwendung und die hohe Bedeutung der Makrooptimierung verstehen. Hier ist ein Beispiel für eine 40-fache Beschleunigung in perfekt aussehendem Code: stackoverflow.com/questions/926266/…

    – Mike Dunlavey

    15. Januar 2010 um 14:40 Uhr

Von dem FreeBSD-Quellcode:

size_t
strlen(const char *str)
{
    const char *s;
    for (s = str; *s; ++s);
    return(s - str);
}

Im Vergleich zu Ihrem Code entspricht dies wahrscheinlich sehr gut einer Assembler-Anweisung, die einen großen Leistungsunterschied erklären kann.

  • Der Compiler sollte in der Lage sein, dies ziemlich effektiv zu optimieren, was bedeutet, dass der Code immer noch lesbar ist und immer noch ziemlich schnell laufen sollte.

    – Matthäus Iselin

    15. Januar 2010 um 9:54 Uhr

strlen(). Die Chancen stehen gut, wenn jemand eine bessere, schnellere generische Methode gefunden hätte, wäre strlen durch diese ersetzt worden.

Benutzer-Avatar
Sudhanshu

Schauen Sie sich den Quellcode von strlen in der Standard-Libc an. Funktionen in Standardbibliotheken sind im Allgemeinen stark optimiert. Hör zu hier (in Assembler codiert) – dies ist von der GNU libc.

size_t
DEFUN(strlen, (str), CONST char *str)
{
  int cnt;

  asm("cld\n"                   /* Search forward.  */
      /* Some old versions of gas need `repne' instead of `repnz'.  */
      "repnz\n"                 /* Look for a zero byte.  */
      "scasb" /* %0, %1, %3 */ :
      "=c" (cnt) : "D" (str), "0" (-1), "a" (0));

  return -2 - cnt;
}

Benutzer-Avatar
Michael Burr

Schauen Sie sich an GNU C-Bibliotheken strlen() Quelle.

Es verwendet eine Reihe nicht offensichtlicher Tricks, um Geschwindigkeit zu gewinnen, ohne auf die Montage zu verzichten, darunter:

  • zu einem Charakter zu gelangen, der richtig ausgerichtet ist
  • Lesen dieser ausgerichteten Teile der Zeichenfolge in ein int (oder einen größeren Datentyp), um mehrere Zeichen gleichzeitig zu lesen
  • Verwenden Sie Bit-Twiddling-Tricks, um zu überprüfen, ob eines der in diesen Zeichenblock eingebetteten Zeichen Null ist

usw.

Der einfachste Weg ist anzurufen strlen(). Ernsthaft. Es wurde bereits von Ihrem Compiler- und/oder Bibliotheksanbieter optimiert, um für Ihre Architektur so schnell wie möglich zu sein.

Eine häufige Optimierung besteht darin, die Notwendigkeit zu beseitigen, einen Zähler zu erhöhen und die Länge aus dem Zeiger zu berechnen:

size_t my_strlen(const char *s)
{
  const char *anchor = s;

  while(*s)
   s++;

  return s - anchor;
}

Benutzer-Avatar
Clifford

C-Saiten sind an sich ineffizientgibt es zwei Gründe für die Verwendung der ASCIZ-Konvention:

  • Die Standard-C-Bibliothek verwendet es
  • Der Compiler verwendet es für wörtliche Zeichenfolgenkonstanten

Die erste davon ist in diesem Fall akademisch, da Sie die Standardbibliothek nicht verwenden, die zweite lässt sich leicht überwinden, indem Sie Funktionen oder Makros erstellen, die Konvertierungen von C-Strings in eine effizientere Konvention wie Pascal-Strings ermöglichen. Der Punkt ist, dass Sie kein Sklave der C-Konvention sein müssen, wenn Sie die C-Bibliothek nicht verwenden.

Benutzer-Avatar
wenig

Eine weitere Möglichkeit, das Zählen von Zeichen zu beschleunigen, ist die Vektorisierung!

Hier ist ein Beispiel dafür, wie dies in Bezug auf UTF8-codierte Zeichenfolgen zu tun ist:

Noch schnellere UTF-8-Zeichenzählung,

http://www.daemonology.net/blog/2008-06-05-faster-utf8-strlen.html

1353840cookie-checkWie berechnet man die Länge einer Zeichenfolge in C effizient?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy