StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I tested the following on 28311552 lines of input. It's 10 times faster than your code. What it does is read a large block at once, then finishes up to the next newline. The goal here is to reduce I/O costs, since scanf() is reading a character at a time. Even with stdio, the buffer is likely too small.</p> <p>Once the block is ready, I parse the numbers directly in memory.</p> <p>This isn't the most elegant of codes, and I might have some edge cases a bit off, but it's enough to get you going with a faster approach.</p> <p>Here are the timings (without the optimizer my solution is only about 6-7 times faster than your original reference)</p> <pre><code>[xavier:~/tmp] dalke% g++ -O3 my_solution.cpp [xavier:~/tmp] dalke% time ./a.out < c.dat 15728647 0.284u 0.057s 0:00.39 84.6% 0+0k 0+1io 0pf+0w [xavier:~/tmp] dalke% g++ -O3 your_solution.cpp [xavier:~/tmp] dalke% time ./a.out < c.dat 15728647 3.585u 0.087s 0:03.72 98.3% 0+0k 0+0io 0pf+0w </code></pre> <p>Here's the code.</p> <pre><code>#include <iostream> #include <stdio.h> using namespace std; const int BUFFER_SIZE=400000; const int EXTRA=30; // well over the size of an integer void read_to_newline(char *buffer) { int c; while (1) { c = getc_unlocked(stdin); if (c == '\n' || c == EOF) { *buffer = '\0'; return; } *buffer++ = c; } } int main() { char buffer[BUFFER_SIZE+EXTRA]; char *end_buffer; char *startptr, *endptr; //n is number of integers to perform calculation on //k is the divisor //inputnum is the number to be divided by k //total is the total number of inputnums divisible by k int n,k,inputnum,total,nbytes; //initialize total to zero total=0; //read in n and k from stdin read_to_newline(buffer); sscanf(buffer, "%i%i",&n,&k); while (1) { // Read a large block of values // There should be one integer per line, with nothing else. // This might truncate an integer! nbytes = fread(buffer, 1, BUFFER_SIZE, stdin); if (nbytes == 0) { cerr << "Reached end of file too early" << endl; break; } // Make sure I read to the next newline. read_to_newline(buffer+nbytes); startptr = buffer; while (n>0) { inputnum = 0; // I had used strtol but that was too slow // inputnum = strtol(startptr, &endptr, 10); // Instead, parse the integers myself. endptr = startptr; while (*endptr >= '0') { inputnum = inputnum * 10 + *endptr - '0'; endptr++; } // *endptr might be a '\n' or '\0' // Might occur with the last field if (startptr == endptr) { break; } // skip the newline; go to the // first digit of the next number. if (*endptr == '\n') { endptr++; } // Test if this is a factor if (inputnum % k==0) total += 1; // Advance to the next number startptr = endptr; // Reduce the count by one n--; } // Either we are done, or we need new data if (n==0) { break; } } // output value of total printf("%i\n",total); return 0; } </code></pre> <p>Oh, and it very much assumes the input data is in the right format.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload