Funktion welche Zeichenstring zählt



  • Nicht ganz, aber nah dran.

    #1: summe = summe + i macht keinen sinn, wenn dann wäre das + 1 für jedes Zeichen.
    #2: du hast bereits i was für dich zählt
    #3: Deine Bedingung ist falschrum. Du willst weiterzählen solange das Zeichen nicht '\0' ist

    Nach den 3 kleinen Verbesserungen sieht der Code dann so aus:

    int stringlen(char* pa) 
    { 
        int i;
        for (i = 0; pa[i] != '\0'; i++) {}
        //Leerer Schleifenbody. i wird bereits durch die Schleife erhöht und
        //das Zeichen wird durch die Bedingung geprüft
    
        return i;
    }
    


  • #1,5: summe ist nicht initialisiert. Du hast summe keinen Anfangswert gegeben.

    Und das sollte² dein Compiler als Warnung anmeckern. Und die musst du auch beachten.
    ²Wenn er das nuicht macht, musst du die Einstellungen für die Warnungen verändern.



  • Es funktioniert nun. Ich habe einfach viel zu viel an die normale Schleife mit Stoppwert x gedacht. Jetzt macht das alles auch Sinn 😃

    Vielen Dank an die fleißigen Helfer! 👍



  • Damit auch eine schöne Implementierung dasteht:

    #include <cstddef>
    
    std::size_t strlen( char const * str )
    {
    	char const * p = str;
    	while( *p++ );
    	return p - str - 1;
    }
    


  • Swordfish schrieb:

    Damit auch eine schöne Implementierung dasteht:

    könnte die überlaufen? Ist es garantiert, dass das letzte byte im addressraum nicht belegt werden kann?


  • Mod

    otze schrieb:

    Swordfish schrieb:

    Damit auch eine schöne Implementierung dasteht:

    könnte die überlaufen? Ist es garantiert, dass das letzte byte im addressraum nicht belegt werden kann?

    Da dachte ich auch sofort dran, aber ich meine, dass es erlaubt ist, um Eins hinter das Ende eines Arrays zu zählen. Ich habe aber gerade keine Lust, das im Standard nachzuschlagen und warte stattdessen auf einen Kommentar von den Leuten, die den Standard auswendig können.



  • SeppJ schrieb:

    otze schrieb:

    [
    könnte die überlaufen? Ist es garantiert, dass das letzte byte im addressraum nicht belegt werden kann?

    Da dachte ich auch sofort dran, aber ich meine, dass es erlaubt ist, um Eins hinter das Ende eines Arrays zu zählen. Ich habe aber gerade keine Lust, das im Standard nachzuschlagen und warte stattdessen auf einen Kommentar von den Leuten, die den Standard auswendig können.

    Es ist garantiert.

    §5.7/5 schrieb:

    [...]Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.



  • SeppJ schrieb:

    otze schrieb:

    Swordfish schrieb:

    Damit auch eine schöne Implementierung dasteht:

    könnte die überlaufen? Ist es garantiert, dass das letzte byte im addressraum nicht belegt werden kann?

    Da dachte ich auch sofort dran [...]

    Zählen darf ich, wohin ich will. Nur dereferenzieren nicht.

    // und unsigneds dürfen auch überlaufen soviel sie wollen. Wenn mir dagegen der Benutzer einen String gibt, der nicht Nullterminiert ist, ist er selber schuld.



  • Swordfish schrieb:

    SeppJ schrieb:

    otze schrieb:

    Swordfish schrieb:

    Damit auch eine schöne Implementierung dasteht:

    könnte die überlaufen? Ist es garantiert, dass das letzte byte im addressraum nicht belegt werden kann?

    Da dachte ich auch sofort dran [...]

    Zählen darf ich, wohin ich will. Nur dereferenzieren nich

    Nein, Pointerarithmetik ist nur innerhalb arraygrenzen erlaubt.



  • Swordfish schrieb:

    Zählen darf ich, wohin ich will. Nur dereferenzieren nicht.

    problem ist nur, wenn durch einen Überlauf p=0 ist. Dann gibt p - str - 1 nicht das richtige.

    //edit doch, klar. überlauf ist ja definiert.



  • otze schrieb:

    Swordfish schrieb:

    Zählen darf ich, wohin ich will. Nur dereferenzieren nicht.

    problem ist nur, wenn durch einen Überlauf p=0 ist. Dann gibt p - str - 1 nicht das richtige.

    //edit doch, klar. überlauf ist ja definiert.

    Üherlauf für Pointer ist nicht definiert, da er nie auftreten kann! Es ist legal, bis eins hinters Ende eines Arrays zu zählen, egal wo das Array ist.
    Weitere Pointerarithmetik ist dann UB.



  • Nathan schrieb:

    Üherlauf für Pointer ist nicht definiert, da er nie auftreten kann! Es ist legal, bis eins hinters Ende eines Arrays zu zählen, egal wo das Array ist.
    Weitere Pointerarithmetik ist dann UB.

    Ist mir bekannt, ich war in der lage deinen post zu lesen bevor ich geantwortet hatte. Das war auf Swordfish bezogen.


  • Mod

    Nathan schrieb:

    Weitere Pointerarithmetik ist dann UB.

    Was, ich darf nicht mehr zurück!?
    (~Edit: Wetten du hast die Scheiße schon erwartet?~ :p )



  • Also ich würde an der "schönen" Lösung eher bekritteln dass sie a) unnötig kompliziert ist und b) ne implizite signed -> unsigned Konvertierung enthält.
    Wieso nicht einfach

    std::size_t strlen(char const* str)
    {
        for (std::size_t i = 0; ; ++i)
            if (str[i] == '\0')
                return i;
    }
    

    ?


  • Mod

    hustbaer schrieb:

    Also ich würde an der "schönen" Lösung eher bekritteln dass sie a) unnötig kompliziert ist und b) ne implizite signed -> unsigned Konvertierung enthält.
    Wieso nicht einfach

    std::size_t strlen(char const* str)
    {
        for (std::size_t i = 0; ; ++i)
            if (str[i] == '\0')
                return i;
    }
    

    ?

    Diese Lösung ist aber komplizierter für den Computer, sofern der Compiler sie nicht zu Swordfishs Lösung optimiert, welche (für eine portable Version) bereits ziemlich optimal ist.

    Man kann natürlich noch darüber streiten, dass Swordfishs Version ab schon PTRDIF_MAX aussteigt (zumindest in einer strengen Standardauslegung, bei der die Differenz zweier Pointer jenseits dieses Werts nicht mehr definiert ist), deine erst ab SIZE_MAX. Aber soweit ich weiß verbietet der Standard sowieso nicht, dass nicht irgendein Objekt sogar größer sein darf als SIZE_MAX. Letztlich scheitert also beide Varianten bei theoretisch möglichen Szenarien, die aber praktisch nie vorkommen werden.



  • SeppJ schrieb:

    Diese Lösung ist aber komplizierter für den Computer, sofern der Compiler sie nicht zu Swordfishs Lösung optimiert, welche (für eine portable Version) bereits ziemlich optimal ist.

    Dir war aber schon klar dass ich mit "unnötig kompliziert" gemeint habe: unnötig kompliziert für Menschen die den Code lesen/nachvollziehen wollen.

    Klar, absolut gesehen ist das keine Herausforderung. Aber relativ, also an der Problemstellung gemessen, ist der Code mMn. einfach unnötig kompliziert.

    Dass der Compiler wohl bei beiden Varianten kein Problem haben wird zu optimieren wie er es eben optimieren will, das ist dir genau so klar wie mir.
    Und selbst wenn ein Unterschied besteht würde ich nicht darauf wetten dass die Variante mit Induktionsvariable schlechter abschneidet.
    Genau so wie ich nicht darauf wetten würde dass die Variante mit Induktionsvariable verliert wenn man sie naiv in Maschinensprache übersetzt.


  • Mod

    Ich wäre mir da gar nicht mal so sicher, dass alle Versionen den gleichen Code erzeugen. Besonders das -1 in Swordfishs Version ist schwer weg zu optimieren (und ich hätte es auch ohne -1 programmiert:

    std::size_t strlen( char const * str )
    {
        char const * p = str;
        while( *p ) ++p;
        return p - str;
    }
    

    )

    Mal gucken, was GCC 4.8.2 auf O3 für x86-64 (aber ohne spezielle Prozessoroptimierungen) daraus macht:

    Deine Version:

    xorl	%eax, %eax
    	cmpb	$0, (%rdi)
    	je	.L5
    	.p2align 4,,10
    	.p2align 3
    .L6:
    	addq	$1, %rax
    	cmpb	$0, (%rdi,%rax)
    	jne	.L6
    .L5:
    	rep ret
    

    Swordfish:

    movq	%rdi, %rax
    	.p2align 4,,10
    	.p2align 3
    .L3:
    	addq	$1, %rax
    	cmpb	$0, -1(%rax)
    	jne	.L3
    	subq	%rdi, %rax
    	subq	$1, %rax
    	ret
    

    Meine Version:

    cmpb	$0, (%rdi)
    	je	.L5
    	movq	%rdi, %rax
    	.p2align 4,,10
    	.p2align 3
    .L4:
    	addq	$1, %rax
    	cmpb	$0, (%rax)
    	jne	.L4
    	subq	%rdi, %rax
    	ret
    .L5:
    	xorl	%eax, %eax
    	ret
    

    Wir sehen: Die Schleife selbst ist bei allen drei Versionen praktisch identisch (und das ist auch gut so!), aber die kleinen Dinge drumherum sind jeweils komplett unterschiedlich. Ich vermute sogar, dass Swordfishs Version hier theoretisch am schnellsten ist, weil ich die Effektivität der Prä-Prüfung, die für unsere beiden Versionen erzeugt wurde, anzweifle. Aber das ist ein sinnloser Vergleich einzelner Anweisungen, wenn der innere Loop praktisch identisch ist. Swordfish hat auf jeden Fall den Größenvergleich für den kürzesten Maschinencode gewonnen.


Anmelden zum Antworten