5
\$\begingroup\$

I have a big txt file containing some specific IP addresses, and all of them appear more than once (the file has around 13 million lines). The file looks like this (the first octet is set to zero for anonimity):

0.169.252.233
0.140.165.113
0.112.0.44
0.89.149.36

What I want is to read all those addresses and print in an output file only the unique values of each IP, removing the duplicates. Below is the code I am using

int main(){
    FILE *in;
    FILE *out;

    in = fopen("in.csv", "r");
    out = fopen("out.csv", "w");
    char line[17];
    char IPdone[100000][17];   // IP addresses already in the output file
    int nIPs = 0;              // number of IPs in the output file
    int k = 0;
    int bol = 0;

    if(in == NULL) printf("ERROR");

    while (fgets(line, sizeof(line), in)) {    //reads input file line by line
        for (k=0; k<100000; k++){              // checks if the IP is already in the output file
            if(!strcmp(IPdone[k], line)){
                bol=1;
                break;
            }
            bol=0;
        }

        if(bol==0){      // if the IP is not in the output file, print and add to IPdone
            fprintf(out, line); 
            strcpy(IPdone[nIPs], line);
            nIPs++;
        }else{          // if it is, continue
            continue;
        }
    }

    fclose(in);
    fclose(out);
}

I am not usually a programmer guy and, although I know this code is not efficient at all, I could not implement any other algorithm with success. This code does work, however, it takes really long to do its job (really really long), and I know there is a much better way of doing it. Also, this code limits the number of IP addresses to 100000 (size of IPdone), and I would rather have a code that can deal with limitless number of different addresses.

I tried the idea of sorting the in file but I had the problem: to sort the file, I need to store all the lines in a vector (right? not sure), but creating a vector[13000000][17] gave me memory problems.

As I said, I am not much into programming, so I would appreciate a help.

\$\endgroup\$
3
  • \$\begingroup\$ IMHO this is your bottleneck for (k=0; k<100000; k++){ // checks if the IP is already in the output file if(!strcmp(IPdone[k], line)){. Keeping the stored ip table sorted will reduce search times form linear to logarithmic. \$\endgroup\$
    – Vorac
    Apr 18, 2017 at 16:02
  • \$\begingroup\$ Second point - it depends on the underlying filesystem, but it seems inefficient to write single ip addresses to a file. Work entirely in ram, then write the list to a file in one go. \$\endgroup\$
    – Vorac
    Apr 18, 2017 at 16:04
  • 1
    \$\begingroup\$ @Vorac Comments are for seeking clarification to the question. All suggestions should be put into answers. \$\endgroup\$ Apr 18, 2017 at 16:22

1 Answer 1

6
\$\begingroup\$

For all practical reasons, you should

    > sort in.csv | uniq > out.csv

from the command line, unless the goal is the programming exercise.

As mentioned in the comments, the bottleneck is a linear search over the list of encountered IPs. It drives time complexity quadratic. Sorting is a way to reduce the complexity.

If the file is indeed too large to fit into RAM (which I seriously doubt; these days 13M records shouldn't be a problem), use an external sort (merge works the best). You can also greatly reduce the memory consumption by keeping IPs as numbers (4 bytes per IP), instead of strings:

    in_addr_t addr;
    while(fgets(line, sizeof(line), in)) {
        bool rc = inet_aton(line, &addr);
        if (!rc) {
            // Deal with malformed address
        } else {
            // Business as usual. Work with addr.
        }
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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