Text file processing speed

Question

So I have a text file containing about 666 000 lines of maximum 10 numbers/line separated by a space. Example:

8 38 62 39 4 50 86 43
53 78 38 22 39 29 78 5
24 13 58 92
.......
53 78 38 22 39 29 78 5

Given a sequence of n numbers, I have to verify if a line has all its elements from the sequence.

I have tried something like this:

int check()
{
    int nrelem = 0, nr, line_int[11];
    int found_counter = 0, sw = 0;
    char *p;

    f = fopen("temp.txt", "rt");

    while (!feof(f))
    {
        nrelem = 0; found_counter = 0; sw = 0;

        fgets(line, 256, f);

        p = strtok(line, " ");
        while (p != NULL)
        {
            sscanf(p, "%d", &line_int[nrelem++]);
            p = strtok(NULL, " ");
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < nrelem; j++)
            {
                if (seq[i] == line_int[j])
                {
                    sw = 1;
                    break;
                }
            }
            if (sw)
                found_counter++;
        }
        if (found_counter == nrelem)
            return 0;
    }
    fclose(f);
    return 1;
}

The problem is that the running time for this function, at 600 000 lines / file is about 14 seconds. I guess it is the way I get my elements from each line of the file with strtok and the implementation with files. Do you guys know a better approach to this, that can reduce the running time below 1 second without the need of a quantum computer? :D Thank you in advance.

Answer 1

As I suggested in comments, using a hash map in your algorithm would lower the time complexity in checking if a number is in the sequence seq. I also changed the signature of the function to something that made a little more sense, as well as incorporating some suggestions from other comments.

Note that this function has not been tested, other than compiling without errors. It requires <stdbool.h>, <stdio.h>, <stdlib.h>, and <string.h> in order to compile:

bool check(char *filename, int *seq, size_t seqSize) {
    size_t lookupSize = 100;
    char lookup[lookupSize];
    FILE *fp;
    char *line = NULL;
    size_t len = 0;
    long int num;
    bool result = true;

    memset(hash, 0, lookupSize);

    for (size_t index = 0; index < seqSize; index++) {
        hash[seq[index]] = 1;
    }

    fp = fopen(filename, "r");

    if (fp != NULL) {
        while (getline(&line, &len, fp) != -1 && result) {
            char *cp = line;
            result = false;

            while (*cp != '\0' && !result) {
                num = strtol(cp, &cp, 10);
                result = num < lookupSize && !lookup[num];
            }
        }

        fclose(fp);
        free(line);
    }

    return result;
}

I set lookupSize to 100, since it appears that your numbers are in the range of 0 to 99. If you have larger numbers, you'll need to declare an array for your lookup table with a size equal to one more than the max integer value in the range you're using, which is why I only recommended this approach for a relatively small range.