# Enormous Input Test

Show 80 post(s) from this thread on one page
Page 2 of 4 First 1234 Last
• 12-30-2008
cyberfish
4.67 with this
Code:

#include <cstdio>

int main() {
unsigned int n, k;
unsigned int count = 0;

unsigned int t[8];

scanf("%u %u", &n, &k);

while (n >= 8) { //first do it in blocks of 8

scanf("%u %u %u %u %u %u %u %u",
&t[0], &t[1], &t[2], &t[3], &t[4], &t[5], &t[6], &t[7]);

for (int i = 0; i < 8; ++i) {
if (!(t[i] % k)) {
++count;
}
}

n -= 8;
}

//do the rest one at a time
for (int i = 0; i < n; ++i) {
scanf("%u", &t[0]);
if (!(t[0] % k)) {
++count;
}
}

printf("%u", count);
}

Out of ideas :).
• 12-30-2008
laserlight
Quote:

Originally Posted by cyberfish
4.67 with this

Yes, I finally decided to let the site do the benchmarking for me, and finished with about the same timing with a similiar approach, since it was the next obvious implementation that actually made use of n.
• 12-30-2008
cyberfish
Using laserlight's idea of ignoring n -

Code:

#include <cstdio>

int main() {
unsigned int dummy, k;
unsigned int count = 0;

unsigned int t[8];

scanf("%u %u", &dummy, &k);

while ((n_read = scanf("%u %u %u %u %u %u %u %u",
&t[0], &t[1], &t[2], &t[3], &t[4], &t[5], &t[6], &t[7]))) {
//first do it in blocks of 8

for (int i = 0; i < n_read; ++i) {
if (!(t[i] % k)) {
++count;
}
}

if (feof(stdin)) break;
}

printf("%u", count);
}

Similar time at 4.76.

Will try to vary the "block size" and see if it changes anything...
• 12-30-2008
cyberfish
Doubling the "block size" to 16 doesn't change anything (4.70).
• 12-30-2008
cyberfish
Quote:

Naive? Straightforward is more like it
hehe. "Naive" because I thought it's got to be harder than this...
• 12-31-2008
iMalc
Try eliminating the most likely often-mispredicted-branch entirely:
Code:

for (int i = 0; i < n_read; ++i) {
count += (t[i] % k) == 0;
}

That should probably give a decent speed boost.
• 12-31-2008
rpet
scanf() contains some sort of (slow) parser, that we do not need here. Replacing scanf() by gets() and atoi() results in 3.4 (s?) instead of 5.4.

Code:

#include <stdio.h>

int main()
{
char b[11];
unsigned int n, k, count = 0;

scanf("%u %u", &n, &k);
while (getchar() != '\n');

while (gets(b))
count += (atoi(b) % k) == 0;

printf("%u", count);
return 0;
}

I believe the key to a really fast solution is to combine the functions "ascii to int" and "is divisible by" but I have no idea how to do this yet.
• 12-31-2008
Elysia
Never ever use gets!
http://cpwiki.sf.net/gets
• 12-31-2008
rpet
Quote:

The next n lines of input contain one positive integer ti, not greater than 10^9, each.
Nothing's wrong with gets() in this special case!
• 12-31-2008
Elysia
No, everything is wrong with it. I is irrelevant if it is faster. It is irrelevant if it safe in this case. Gets is never to be used.
• 12-31-2008
rpet
2.14, using an atoi() replacement

Code:

#include <stdio.h>

int main()
{
char b[11];
unsigned int i, v, n, k, count = 0;

scanf("%u %u", &n, &k);
while (getchar() != '\n');

while (gets(b)) {
for (v = 0, i = 0; b[i]; ++i)
v = 10 * v + (b[i] - '0');

count += (v % k) == 0;
}

printf("%u", count);
return 0;
}

• 12-31-2008
C_ntua
The gets version 3.35
The fgets version 3.39
So there is really not a big difference.
It would be interesting if there was an algorithm that is faster than the %. That just decides if a number is divisible or not without calculating the remainder. But personally I don't know any such algorithm
• 12-31-2008
laserlight
Quote:

Originally Posted by Elysia
No, everything is wrong with it. I is irrelevant if it is faster. It is irrelevant if it safe in this case. Gets is never to be used.

To be fair, the rules in a "competition" are different from the normal rules of programming/software engineering, so I would accept gets() in this case since the input is guaranteed to be correct. Likewise, atoi() is acceptable even though there is no way to check for a parse error.

EDIT:
Quote:

Originally Posted by C_ntua
The gets version 3.35
The fgets version 3.39
So there is really not a big difference.

Yes, if empirical evidence shows that they are effectively equivalent in timing then one might as well use fgets().

Quote:

Originally Posted by C_ntua
It would be interesting if there was an algorithm that is faster than the %. That just decides if a number is divisible or not without calculating the remainder. But personally I don't know any such algorithm

There are many such algorithms, but I believe there is none for the general case other than by computing the remainder.
• 12-31-2008
Elysia
Quote:

Originally Posted by rpet
2.14, using an atoi() replacement

Code:

#include <stdio.h>

int main()
{
char b[11];
unsigned int i, v, n, k, count = 0;

scanf("%u %u", &n, &k);
while (getchar() != '\n');

while (gets(b)) {
for (v = 0, i = 0; b[i]; ++i)
v = 10 * v + (b[i] - '0');

count += (v % k) == 0;
}

printf("%u", count);
return 0;
}

Drop the gets!
You can also use fgets + two strtol to parse and get the numbers instead of scanf.
It saves clearing the input buffer.
But is it faster? That is the question.

And no one has tried std::getline?

Quote:

Originally Posted by laserlight
To be fair, the rules in a "competition" are different from the normal rules of programming/software engineering, so I would accept gets() in this case since the input is guaranteed to be correct. Likewise, atoi() is acceptable even though there is no way to check for a parse error.

EDIT:

Yes, if empirical evidence shows that they are effectively equivalent in timing then one might as well use fgets().

There are many such algorithms, but I believe there is none for the general case other than by computing the remainder.

Perhaps there might be; but as gets is dangerous (and as I thought, not much faster than fgets), there is never a reason for it. It is also bad to use it in case someone peeks in the thread and gets it in their heads to use it. Competition or not, I would never consider gets. It is such an evil that should not exist.
atoi is another story, however, since it does not pose such dangers as gets, but can cause problems in the execution of code. But if it is a simple program, this is acceptable.
• 12-31-2008
C_ntua
This code runs as fast as the already posted code (2.18 vs 2.17, the times vary a bit for every test)
Code:

#include <stdio.h>

int main()
{
char b[11], a[22]; char* end;
unsigned int i, v, n, k, count = 0;
fgets(a, 22, stdin);
n = strtol(a, &end, 10);
k = strtol(end, NULL, 10);

while (fgets(b, 11, stdin)) {
for (v = 0, i = 0; b[i]; ++i)
v = 10 * v + (b[i] - '0');

count += (v % k) == 0;
}

printf("%u", count);
return 0;
}

Show 80 post(s) from this thread on one page
Page 2 of 4 First 1234 Last