String-Durchlaufprogramm in C

  • Meine Aufgabe war es, eine Funktion in C zu schreiben, in der eine Zeichenfolge wie {2210090,34566,87234,564676} als Eingabe angegeben werden würde und die Funktion die Anzahl der durch Kommas getrennten Zahlen ermitteln musste, deren Durchschnitt aus einzelnen Ziffern bestand ist größer oder gleich 5.

    Im folgenden Beispiel ist der Durchschnitt von 2210090 2, der Durchschnitt von 34566 ist 4,8, der Durchschnitt von 87234 ist 4,8 und der Durchschnitt von 564676 ist 5,6, daher ist die Zählung 1.

     void GetCount(int n,char* input2)
    {
        int sum=0;
        n=0;
        h:
        *input2++;  
        if((*input2) && !isdigit(*input2))
        {
            if(sum>n<<2)
                output1++;
            sum=0;
            n=0;
            goto h;
        }
        else if(*input2!='\0')
        {
            sum+=*input2-'0';
            n++;
            goto h;
        }
    }
     

    Der erste Parameter n ist die Gesamtanzahl von Nummer. Das Programm funktioniert einwandfrei und ich wollte nur wissen, ob jemand etwas zur Verbesserung der zeitlichen Komplexität des Programms beitragen kann. Ich würde mich auch über eine bessere Lösung für dieses Problem freuen, indem Sie die Anzahl von if s und goto s reduzieren oder die Notwendigkeit von if oder goto. Vollständig beseitigen

    16 April 2014
    Jamal
5 answers
  • Bevor ich auf Effizienz fokussiere, würde ich einige Verbesserungen empfehlen:

    • Hier brauchen Sie keine goto. Dies lässt sich leicht in eine for -Schleife umwandeln.

    • Sagen Sie const char *input2, um eine versehentliche Änderung Ihrer Eingabezeichenfolge zu vermeiden.

    • Verwenden Sie Leerzeichen, um die Reihenfolge der Operationen zu bestimmen:

      • if(sum > n<<2) Relationale Operatoren und Verschiebungen befinden sich direkt neben einander in der Operator-Vorrang-Tabelle .

      • sum += *input2 - '0';

    • Nehmen Sie das Sternchen in *input2++; heraus. Sie verwenden den Charakter nicht.

    Und noch etwas subtiler:

    • isdigit erwartet ein unsigned char mit einem int. char ist normalerweise signiert (auf einigen Plattformen ist es jedoch nicht signiert). Wenn eines Ihrer Eingangsbytes nicht ASCII ist, kann dies zu undefiniertem Verhalten führen.

       isdigit((unsigned char) *input2)
       

    Hier ist eine redaktionelle Version Ihres Codes:

     void GetCount(const char* input2)
    {
        int sum = 0;    /* Sum of digits in current number */
        int n = 0;      /* Number of digits in current number */
    
        for (;;)
        {
            input2++;
            if (*input2 == '\0')
                break;
    
            /*
             * If we have a digit, increment sum and n appropriately.
             *
             * Otherwise (we ran into a brace or comma), tally the current number,
             * and clear the stats for the next number.
             */
            if(isdigit((unsigned char) *input2))
            {
                sum += *input2 - '0';
                n++;
            }
            else
            {
                if(sum > n<<2)
                    output1++;
                sum = 0;
                n = 0;
            }
        }
    }
     

    Schauen wir uns das an die sum > n<<2 Zeile, die für mich falsch aussieht. Hier ist die Bedingung, die wir testen möchten (einfach, aber ineffizient):

     1. (double)sum / n >= 5.0
     

    Wir können es in Ganzzahlarithmetik ausdrücken als:

     2. sum >= n * 5
     

    Nun bekomme ich das, was Sie versucht haben. Ihre nächsten Schritte wandelten die Multiplikation in eine kostengünstigere Schicht um:

     3. sum > n * 4
    4. sum > n<<2
     

    Schritt 3 ist falsch. sum kann größer als n * 4 sein, aber kleiner als n * 5. Beispiel:

     34566: sum = 24, n = 5
    
    n * 4 = 20      sum >  n * 4 holds
    n * 5 = 25      sum >= n * 5 does not hold
     

    Die gute Nachricht ist, dass wir die Multiplikation und sogar die Verschiebung loswerden können! Erhöhen Sie einfach n um 5 bei jeder Iteration:

             if(isdigit((unsigned char) *input2))
            {
                sum += *input2 - '0';
                n += 5;
            }
            else
            {
                if(sum >= n)
                    output1++;
                sum = 0;
                n = 0;
            }
     

    Zum Schluss wollen wir das isdigit loswerden. Es ist wahrscheinlich ziemlich schnell, aber es muss gegen EOF vorgehen und eine Tabellensuche durchführen. Angenommen, Ihre Eingabe entspricht garantiert der von Ihnen beschriebenen Syntax (nicht negative Ganzzahlen, die durch Kommas getrennt und umschlossen werden)

    15 January 2012
    pix0r
  • Ihre Funktion sollte die Anzahl der Zahlen zurückgeben, die Ihr Kriterium erfüllen, und Sie benötigen nur die Eingabezeichenfolge. Die Schnittstelle sollte also folgendermaßen aussehen:

     int GetCount(const char *str)
     

    Sie brauchen die goto -Anweisungen wirklich nicht. Sie benötigen eine while -Schleife. Ich hätte wahrscheinlich eine Schleife wie:

     while ((c = *str++) != '\0')
    {
        ...
    }
     

    Sie haben nicht gezeigt, wo output1 definiert oder initialisiert ist . Es sollte sich wahrscheinlich um eine lokale Variable handeln, die mit 0 initialisiert wurde, und der Wert sollte zurückgegeben werden.

    Ihre Berechnung ist zweifelhaft. Für eine Anzahl von m -Ziffern sollte die Summe ihrer Ziffern größer oder gleich 5 * m sein.

    Beachten Sie außerdem Folgendes:

     *input2++;  
     

    macht genau dasselbe:

     input2++;  
     

    Der Compiler entfernt zwar die Dereferenzierung (da er sie nicht verwendet), so dass es keine Laufzeitleistung gibt, und es ist sinnlos, einen Wert abzurufen, den Sie niemals verwenden. *input++ hat seine Verwendung, wird aber als alleiniger Ausdruck in einer Anweisung nicht benötigt. GCC set fussy wird Sie darauf hinweisen:

     error: value computed is not used [-Werror=unused-value]
     

    (zusammengestellt mit -Werror), um alle Warnungen in Fehler umzuwandeln ).

    20 August 2014
    Jonathan Leffler
  • Es handelt sich um eine kommentierte Revision. Es ist immer noch O (n) - Sieh nicht, wie es NICHT sein könnte. Es ist idiomatischer und weniger überflüssig. Es wird nicht kompiliert oder getestet.

    Es stellt sich nicht die Frage "Was hat (sum>n<<2) mit etwas zu tun?"

    Es ist ein nicht-ungültiger Rückgabetyp. Es beschreibt die Art des Ergebnisses. Es gibt nichts mit einem globalen wie output1 zu tun, an den Sie sich erinnern müssen, um irgendwo definiert zu werden.

     unsigned int GetCount(char* input2)
    {
        unsigned count = 0;
        int sum = 0;
     

    Es ist ein Kommentar. Es erklärt Dinge, die gar nicht offensichtlich sind, zum Beispiel, was (sum>n<<2) mit irgendetwas zu tun haben kann.

         int saw_a_digit = 0; /* only consider counting (again) after seeing a digit */
     

    Es ist eine Schleife. Es ist besser als ein goto Es ist eine for-Schleife. Es funktioniert gut, wenn ein Zeiger nach jeder Zeit durch die Schleife inkrementiert wird.

    Es wurde ein Test für null erhalten, der nur an einer Stelle sein muss.

    Es hat ein Inkrement, das den Zeiger nicht mit '*' dereferenzieren muss.

         for(; *input2; input2++)
        {
            if(isdigit(*input2))
            {
     

    Es ist eine geringfügige Optimierung gegenüber dem Summieren von Ziffern. Es ist nicht erforderlich, Ziffern zu zählen oder einen Durchschnitt zu berechnen oder etwas aus der Ferne zu berechnen, wie (sum>n<<2). Warum sollte es Es ist etwas schwierig, daher gibt es noch einen Kommentar.

                 /* We don't need the digit, just how it relates to 5.
                 * Amounts > 5 gets canceled out by amounts < 5,
                 * 0s and 9s have more influence than 4s and 6s.
                 * '5' has no effect at all.
                 * This would take a very long string of digits mostly 
                 * on on the same side of 5 to overflow sum. */
     

    Es ist Leerzeichen in einer nicht trivialen Aussage. Es ist lesbar.

                 sum += *input2-'5';
                saw_a_digit = 1;
            }
            else if (saw_a_digit) // found end of digit string
            {
                 if (sum >= 0) // low influence did not dominate
                 {
                     ++count;
                 }
                 sum = 0;
                 saw_a_digit = 0;
            }
        }
    }
     

    Es ist eine Alternative, die zwei kleinere Schleifen verwendet. Es vermeidet Modusvariablen wie saw_a_digit. Es könnte etwas schneller sein.

     unsigned int GetCount(char* input2)
    {
        unsigned count=0;
        int sum;
        while (*input2)
        {
            for (;!isdigit(*input2);input2++) /* skip non-digits */
                if (!*input2)
                    return count;
            sum=0;
            do {
                /* We don't need the digit, just how it relates to 5.
                 * Amounts > 5 get canceled out by amounts < 5,
                 * 0s and 9s have more influence than 4s and 6s.
                 * '5' has no effect at all.
                 * This would take a very long string of digits mostly 
                 * on on the same side of 5 to overflow sum. */
                sum += *input2-'5';
            } while (isdigit(*++input2));
            if (sum>=0) // low influence did not dominate
            {
                ++count;
            }
        }
        return count;
    }
     
    17 July 2015
    jacwahPaul Martel
  • Ich werde mich nicht auf Geschwindigkeit konzentrieren, sondern auf Klarheit in Bezug auf die ursprüngliche Spezifikation:

     int GetCount(const char *str)
    {
        int count = 0;
        int sum_digits = 0;
        int num_digits = 0;
    
        for (int i = 0; str[i]; i++)
        {
            switch (str[i])
            {
                case '{':
                {
                    break;
                }
    
                case '0': case '1': case '2': case '3': case '4':
                case '5': case '6': case '7': case '8': case '9':
                {
                    int digit = str[i] - '0';
                    sum_digits += digit;
                    num_digits++;
                    break;
                }
    
                case ',':
                case '}':
                {
                    if (num_digits > 0)  // Could be 0 if input was "{}",
                        if (sum_digits >= num_digits * 5)  // e.g., sum_digits/num_digits > 5
                            count++;
                    sum_digits = num_digits = 0;  // Reset accumulators for next input number.
                    break;
                }
    
                default:
                {
                    return -1;  // Invalid input character encountered
                }
            }
        }
    
        return count;
    }
     

    Das stellt sich tatsächlich als extrem schnell heraus. Mit einem guten Compiler sollte str[i] genauso schnell sein wie ein Zeiger inkrementieren. Hier gibt es übrigens immer noch eine Tabelle. Es ist in der Anweisung switch verborgen. Aber solche Dinge sind extrem schnell.

    18 July 2015
    R SahuTodd Lehman
  • Erstens: Wozu dient der Parameter n und benötigen Sie ihn? Versuchen Sie, Ihren Code im Wesentlichen wie folgt zu strukturieren:

     function definition
        int n = 0;
        int val = 0;
        int count = 0;
        iterate over the string
            if the character is a numeral
                val += character value
                n++;
            if the character is a ,
                if the avg (which is val / n) is greater than 5
                    count++
                reset n and val to zero
            if the character is a }
                return count
            else
                reset n and val to zero
         return count
     

    Oder etwas dazu

    14 January 2012