c - Read from file fast -


i have txt file contains 2 graphs , number of vertices in following format:

6 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 

the matrices represent vertice adjacency. if 2 vertices adjacent, pair gets 1. although graphs not separated visually, second graph starts after 6th row of first. each graph can have lot of vertices, 5000 , both of same size (the graphs). wrote algorithm checks if 2 graphs isomorphic , noticed reading graphs takes 8 seconds , actual algorithm takes 2.5 (for 5000 vertices). since goal optimize overall speed of program, i want know if can improve (in terms of speed) current code of reading file:

file* file = fopen ("input.txt", "r"); fscanf (file, "%d", &i); int n = i; while (!feof (file)) {       fscanf (file, "%d", &i);      if (j < (n*n)) {  // first graph         if (i==1) {             adj_1[j/n][v_rank_1[j/n]] = j - (j/n)*n; // add vertice adjacents of current vertice             v_rank_1[j/n] += 1;         }     }     else if (j>=(n*n)) {   // second graph         if (i==1) {             adj_2[(j-(n*n))/n][v_rank_2[(j-(n*n))/n]] = (j-(n*n)) - ((j-(n*n))/n)*n; // add vertice adjacents of current vertice             v_rank_2[(j-(n*n))/n] += 1;         }     }     j++; } fclose (file); 

the adj_* table holds indexes of adjacent vertices of vertice

the v_rank_* table holds number of vertices adjacent vertice

it important acquire , information graph.

the first optimization read whole file in memory in 1 shot. accessing memory in loops faster calling fread.

the second optimization less arythmetic operations, if means more code.

third optimization treating data file characters avoid integer conversion.

the result be:

// bulk read file memory fseek(file, 0, seek_end); long fsize = ftell(file); fseek(file, 0, seek_set); char *memfile = malloc(fsize + 1); if (memfile == null) return; // not enough memory !! handle wish fscanf(file, "%d", &n); fread(memfile, fsize, 1, file); fclose(file); memfile[fsize] = 0;  // more code less arythmetic operations int lig, col; char *mem = memfile, c; (int lig = 0; lig < n; lig++) { // first graph     (int col = 0; col < n; col++) {         (;;)         {             c = *mem;             if (c == 0) break;             mem++;             if (c == '1') {                 adj_1[lig][v_rank_1[lig]++] = col; // add vertice adjacents of current vertice                 k++; // ??                 break;             }             if (c == '0') break;         }      } } (int lig = 0; lig < n; lig++) { // second graph     (int col = 0; col < n; col++) {             c = *mem;             if (c == 0) break;             mem++;             if (c == '1') {                 adj_2[(lig][v_rank_2[lig]++] = col; // add vertice adjacents of current vertice                 l++;  // ??                 break;             }             if (c == '0') break;         }     } } free(memfile); 

remarks: said nothing variables k , l.


Comments

Popular posts from this blog

twig - Using Twigbridge in a Laravel 5.1 Package -

jdbc - Not able to establish database connection in eclipse -

firemonkey - How do I make a beep sound in Android using Delphi and the API? -