OJ Board

I like optimisation, in fact, I try to optimize my programs while writing them... however, some of them, like 280 (where there are no AC in 0.00) motivate me to optimize even more and go up in the ranklist.... however there are some points I didn't get, first of all, do you guys use two buffers to store the input / output with fread/fwrite ?? is memory enough? and another thing, what's the faster method to convert from string -> int and int -> string, for string->int I use the multiplication thing, like this:

[c]
n = 0;
ptr = buf;
while (*ptr++) n = n * 10 + *ptr - '0';
[/c]

and for int->string I do this:

[c]
ptr = buf;
while (n) {
*ptr = n%10;
n/=10;
ptr++;
}
*ptr = '\0';
reverse(buf);
[/c]

am I doing this the right way?...

I did this pervert code writing for a while...

In "string-int" there is a faster way (performing less arithmetic operations using a look-up table). In "int-string" you can speed this up considerably. Let me give you a hint: get rid of two divisions (very expensive operation) and reverse(buffer).

Good luck!

Aleksandrs Saveljevs wrote:In "string-int" there is a faster way (performing less arithmetic operations using a look-up table).

Hmmm, I'm not entirely sure about this. Looking up a table involves pointer arithmetics, so I don't think you gain anything by exchanging an integer subtraction with a pointer addition...

Aleksandrs Saveljevs wrote:In "int-string" you can speed this up considerably. Let me give you a hint: get rid of two divisions (very expensive operation) and reverse(buffer).

In many probs you can write ints without divisions...

Ciao!!!

Claudio

playerX wrote:do you guys use two buffers to store the input / output with fread/fwrite ?? is memory enough?

Mostly it depends on the size of the input and the output.
When both are huge I prefer to use bigger buffers for input than for output.

However I think that in some cases faster times can only be achieved by writing hand-optimized asm code. I tried in some cases to optimize my C code and in fact got better times on my machine, but got worse times on the OJ. So, as far as C is concerned, simple code is better.

Anyway, consider always that there can be something you haven't considered yet

Ciao!!!

Claudio

Hello.

Claudio wrote:Hmmm, I'm not entirely sure about this. Looking up a table involves pointer arithmetics, so I don't think you gain anything by exchanging an integer subtraction with a pointer addition...

You know, I thought about this too, but I remember that it gave me a little boost on one of the problems. I tried testing it and here is what I found:
[cpp]#include <cstdio>
using namespace std;

#define MAX_TRY 50000000

int lookup[59];
volatile int i, j;
char *number="123456789", *pointer;

int main() {
for (i=0; i<10; i++) lookup[i+48]=i;
for (i=0; i<MAX_TRY; i++)
for (j=0, pointer=number; *pointer;) j=j*10+*(pointer++)-48;
for (i=0; i<MAX_TRY; i++)
for (j=0, pointer=number; *pointer;) j=j*10+lookup[*(pointer++)];
return 0;
}[/cpp]
My compiler (C++Builder) likes the first more (4 seconds to 5). However, OJ compiler says it's 8.3 to 8.1. So I tend to think it's compiler dependent.

Claudio wrote:In many probs you can write ints without divisions...

Really? How's that?

Aleksandrs.

Aleksandrs Saveljevs wrote:My compiler (C++Builder) likes the first more (4 seconds to 5). However, OJ compiler says it's 8.3 to 8.1. So I tend to think it's compiler dependent.

It may be the compiler, the level of optimization used by the compiler, the target processor of the compiler and the processor the compiled program runs on.

Aleksandrs Saveljevs wrote:

Claudio wrote:In many probs you can write ints without divisions...

Really? How's that?
Aleksandrs.

If ints are small lookup tables will do

Ciao!!!

Claudio