5
\$\begingroup\$

The following code reads a .txt file that contain only numbers. Read the first one, create a dynamic array and put the other numbers on it, made some procedures and in the end write a file with the int total.

I want to know if there is a way to run the code faster (the maximum procedure time should be 1s) if I had a .txt file with 1,000,000 numbers.

Is there a more stable way to write this code? Do I have to take all the restrictions I could?

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
static int total = 1;

int process( int *my_array, int *endp) { 
    int a, b; 
    //static int total = 1;
    if ( my_array == 0 ) return 0; 
    if ( my_array == endp ) return INT_MIN;
    else a = *my_array++; 
    if ( (b= process( my_array, endp )) == INT_MIN ) return a; 
    if ( a > b ) 
    {total++; return printf( "%d > %d and total now is %d\n", a, b, total ), a; } 
    return b; 
} 

int main () 
{ 
  int t_size;

  FILE * fp;                                                                        
        fp = fopen ("xxx.txt", "r");
        if (fp == NULL) // error here if there was a problem!
    {
        printf("Opening 'xxx.txt file failed: %s\n",strerror(errno)); // No such file or directory
        getchar();               // wait the user press a key
        return 0;                // returning an int of 0, exit the program
    } 
    else { 

    fscanf(fp, "%d", &t_size); 

    int readch = 0;
        long int filepos = 0L;
        filepos = ftell ( fp);                                                  // get the file position                                                                   
        while ( ( readch = fgetc ( fp)) != EOF) {                               // read each character of the file                                      
        if ( isalpha ( readch)) {                                               // check each character to see if it is a letter                                    
        printf ( "File contains letters\n");                                    // print error message
        fclose ( fp);                                                           // close file
        getchar();                                                              // wait for the user to press a key
        return 1;                                                               // exit the program
        }
        }


    fseek(fp, 0, SEEK_END);                                                 // check to see if the file contains characters!
            if (ftell(fp) == 0) {                                               // if not...
            printf("The file can't be empty\n");                                // empty file error
            getchar();                                                      // wait the user press a key 
                return 1;
            }
            fseek(fp, 0, SEEK_SET);     

        fseek ( fp, filepos, SEEK_SET);     

    if(t_size<1 || t_size>1000000)                                              // set restrictions to integer 
            {
        printf("The number must be 1<= N <= 1.000.000",strerror(errno));        // error with the integer number
        getchar();                                                              // wait the user press a key
        return 0;                                                               // returning an int of 0, exit the program
            }
            else        
            {

        printf("Create a size of %d array\n", t_size);

        int* my_array = NULL; 
        my_array = malloc(t_size*sizeof(*my_array));

        if (my_array==NULL) {
        printf("Error allocating memory!\n"); //print an error message
        return 1; //return with failure
        getchar();
        }
        int i =0;
        for ( i = 0; i < t_size; i++ )
        {
        fscanf(fp, "%d",&my_array[i]);  /*p[i] is the content of element at index i and &p[i] is the address of element at index i */
        }

        //if all working smoothly...
        printf("All up and running! Array created! :D \n\n Array values: \n");
        for(i = 0; i < t_size; i++ )
        {
        printf(" %d : %d\n", i, my_array[i]);
        }

        printf("\n");
        process(my_array, my_array + t_size);
        printf("\n%d kids see the entrance!\n\n\nI made it!!! The program finished! \nCopyright George ", total);
        getchar();

        free(my_array);
        }
        fclose(fp);
        }
        FILE *fp_write;

        fp_write = fopen("test.txt", "w+");
        fprintf(fp_write, "%d", total);
        fclose(fp_write);
}
\$\endgroup\$
6
\$\begingroup\$
int process( int *my_array, int *endp) { 
    int a, b;

My first comment is that process is a weak name for a function. Almost all functions could be said to be processing their parameters. A more descriptive name would make it easier to see what the function is doing.

//static int total = 1;

You should avoid commented code in production. By the time that you are ready to send out for code review, you should have cleaned these things out of the code.

if ( my_array == 0 ) return 0; 

OK, if the array is invalid (a null pointer), return 0. You are doing this check for every recursive call of the function, but this could only happen in the first call. You should actually do this check outside of the process function (looking in main, you already do this) and ensure that you always pass a valid array pointer into the function. That will save you a comparison on every recursive call. Get rid of this call.

Note that the comparison to NULL that you have in main is the correct way to do it. The 0 check will likely work (because NULL is almost always set to 0), but it is less reliable.

if ( my_array == endp ) return INT_MIN;
else a = *my_array++; 

The function is starting to do something here. If the array is at the end, you return the minimum possible integer, which will be a negative number. If the array is not at the end, you grab the first value of the array and move one further back into the array.

if ( (b= process( my_array, endp )) == INT_MIN ) return a; 

Here's the recursive call. You get the result of process on the new smaller array and check if it's equal to INT_MIN. This could happen either because every remaining value in the array is equal to INT_MIN or because there's nothing left in the array. This seems unnecessary. I'm thinking that we could get rid of the comparison and return here. Obviously, the recursive call is necessary.

if ( a > b ) 
{total++; return printf( "%d > %d and total now is %d\n", a, b, total ), a; } 

This is overly complicated and more easily written:

if ( a > b ) 
{
    total++;
    printf("%d > %d and total now is %d\n", a, b, total);
    return a;
}

If a is greater than the recursive result of calling this function on the rest of the array: increment a total variable; print out a statement describing what happened; return a because it is the largest member of my_array.

return b; 
} 

Finally, if b is greater than or equal to a, you return b. We can now say that what this function does is: it sets a global variable to the number of times that an element of the array is greater than all the members to its right; it returns the largest value from the array; and it produces output. That's three things done by one function, but the usual preference is to only do one thing per function.

You mention that you are worried about efficiency. So apparently you put these three responsibilities into one function so as to maximize efficiency. I'll accept that decision. Perhaps someone else wants to argue it, but I think that there's some things that I can tell you within the parameters that you set.

There's basically two things in this function that eat up time. One is that you do a lot of print statements (up to one less than the number of inputs). The other is that you are doing the recursive call. Presumably you have to do the print statements, so we're stuck with those. We don't have to do the recursive call.

int process( int *my_array, int *endp) {
    // this function should only be called if there is at least one value in the array
    int maximum = *(--endp);

    while ( endp > my_array ) {
        int a = *(--endp);

        if ( a > maximum ) {
            total++;
            printf("%d > %d and total now is %d\n", a, b, total);
            maximum = a;
        }
    }

    return maximum;
}

This function sets the maximum to the last element of the array and then updates it as necessary. It iterates over the array from end to beginning. If the current element is greater than the maximum, it updates maximum to be the current element. Because we know that we are starting at the end, we can save most of the checks that we are at or near the end in favor of one check whether we've reached the beginning. Further, because maximum is always maintained from the end, we only have to update when it changes. If the maximum is greater than or equal to the current element, we can simply do nothing.

This function eliminates the need to do any recursive calls. It's purely iterative.

This review seems long enough, so I'll let someone else review your main function. I'll just note that it would be easier to read if you reformatted the indentation so that code inside a block was consistently indented more than the code outside the block. Consistency in formatting makes code easier to read.

\$\endgroup\$
  • \$\begingroup\$ Ok sir you told me enough and I understand the most part of it(as I said in the other solution comment) i'm student. So the function you describe me in the end is a better way to do my process function? You understand my code quiet well! So lets say than I get reed all of these printf commands and I keep only the fwrite code, so I can get a result. Will be that easier to procidure? Remeber I want to test until 1.000.000 numbers! \$\endgroup\$ – Nikos KLon Nov 17 '14 at 13:11
  • \$\begingroup\$ you have a wrong in your code. Lets say that we have 15 sized array and only 14 numbers. Then the output would be wrong. I think you know why. Why is that? \$\endgroup\$ – Nikos KLon Nov 17 '14 at 14:35
5
\$\begingroup\$

Your code structure makes it difficult to test, measure and - if necessary - optimise individual sub functions that your program performs. It also makes it exceedingly difficult to substitute one method of performing a task with another method.

Sub functions that are performance-related:

  • text line input from a file
  • parsing text lines
  • converting text to numbers

Ideally, every function and data structure should have exactly one simple and clear job. That makes programs easier to develop, understand and verify (test), and higher-level functions read more like documentation or like a plan of attack than like a clump of various statements. Ideally, a program should explain itself as you read it, much like a form of documentation that just happens to be executable (and hence verifiable).

If you just need totals then there is no urgent need to fill an array with the numbers - just add numbers as they come in and discard them. On the other hand, the array of numbers can be a convenient interface that makes the code more flexible, and easier to test/verify.

As regards the performance of reading numbers from text files, have a look at the topic Large ASCII file data read. My answer there also contains links to other relevant topics, like fast conversion of text to numbers.

\$\endgroup\$
  • \$\begingroup\$ I understand sir. But I'm student and I can't make such an advance messure. That's why I asked for help here. I also understand your answer as well. But how can I make the program more flexible from the time that I have such many if statements and restrictions? I also can make a code without dynamic arrays but I don't know what is better. Do you tell me that using fread than fcanf can make the program faster to store the nums in the array or should I use strtok to split each line into items. and then convert each item to an integer and store in the next free element of the array.? \$\endgroup\$ – Nikos KLon Nov 17 '14 at 12:59
  • \$\begingroup\$ As an example, your main function should do not much more than opening a file and farming out work to other functions. Instead of inlining code for reading t_size and doing syntax checks and so on, hypothesise the existence of a suitable function and write t_size = read_array_size(f); errors could be represented by negative values, for example. Farm out the creation of the array and the reading of values into the array to separate functions. That way you can keep irrelevant details out of the main function, details that are not necessary for understanding its job. \$\endgroup\$ – DarthGizka Nov 17 '14 at 13:29
  • \$\begingroup\$ One possible way of handling the input is to use fgets() to read lines into a line buffer; from then on you have only text on your hands, and the functions that process the text can be developed and tested without any files whatsoever, by making a small array of test cases (strings). fgets() should be more than fast enough for reading lines in your case. However, should it turn out that it is not then you can easily program something using fread() without changing anything in the rest of your code. That's the whole point of separating responsibilities. Flexibility. Simplicity. Clarity. \$\endgroup\$ – DarthGizka Nov 17 '14 at 13:45
  • \$\begingroup\$ your last sentence is so true! So I use fgets to read the numbers but again I need to put them in the array. You think that is better than fscanf \$\endgroup\$ – Nikos KLon Nov 17 '14 at 13:54
  • 2
    \$\begingroup\$ but if the int<0 then i don't see any return error. This is the first time I read about that macro. Is this to avoid the if statement -I think so- \$\endgroup\$ – Nikos KLon Nov 17 '14 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.