JAVA-Difficulties We Face

Write here if you have problems with your Java source code

Moderator: Board moderators

pepak
New poster
Posts: 5
Joined: Sat Apr 08, 2006 8:25 am

Post by pepak » Fri May 12, 2006 8:13 pm

Never mind, looking at the runtime sources it seems that read(Byte[]) is just using read() repeatedly so it is useless for optimalization purposes. Still, I wonder... Is it moral to cheat against a cheater?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri May 12, 2006 9:36 pm

Is it moral to cheat against a cheater?
What do you mean by that? More precisely - who do you think is cheating?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon May 15, 2006 9:58 pm

Here is one more:
WA

Code: Select all

people[i] = new Person(parseInt(st.nextToken()),parseInt(st.nextToken()));
AC

Code: Select all

int x = parseInt(st.nextToken());
int y = parseInt(st.nextToken());
people[i] = new Person(x, y);
This is confusing...

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Wed May 17, 2006 4:30 pm

Darko wrote:Here is one more:
WA

Code: Select all

people[i] = new Person(parseInt(st.nextToken()),parseInt(st.nextToken()));
AC

Code: Select all

int x = parseInt(st.nextToken());
int y = parseInt(st.nextToken());
people[i] = new Person(x, y);
This is confusing...
Wait a minute... I think this code will not even compile. It should be Integer.parseInt yes? I always use the parseInt method in Integer class this way.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed May 17, 2006 7:10 pm

Sorry, should've mentioned that parseInt() is my own. I ended up writing a bunch of standard library methods for one reason or another.

I still submit in Java, you know (unlike some! :))

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Jul 05, 2006 3:47 am

...and another one:
AC

Code: Select all

st = new StringTokenizer(readLine());
			String s = st.nextToken();
			int val = parseInt(st.nextToken());
			list.put(s, new Integer(val));
WA

Code: Select all

st = new StringTokenizer(readLine());
			list.put(st.nextToken(), new Integer(parseInt(st.nextToken())));
It's not even a case of multiple dereferencing, I have no idea why the latter one fails.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Wed Jul 05, 2006 3:23 pm

Darko wrote:...and another one:
AC

Code: Select all

st = new StringTokenizer(readLine());
			String s = st.nextToken();
			int val = parseInt(st.nextToken());
			list.put(s, new Integer(val));
WA

Code: Select all

st = new StringTokenizer(readLine());
			list.put(st.nextToken(), new Integer(parseInt(st.nextToken())));
It's not even a case of multiple dereferencing, I have no idea why the latter one fails.
With regards to the code you posted, UVA's Java compiler gcj will compile Java to C. And for parameters passed to C functions, they are passed from right to left (__cdecl keyword, default) usually unless it is specified using __stdcall keyword (the Pascal way of passing parameters to functions, left to right)

So therefore the first token might have been passed to the parseInt function because of the behaviour of parameter passing to C functions, instead of what you intended - as the first parameter to the put function.

Correct me if I am wrong.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Jul 05, 2006 4:47 pm

Oh, man, that makes perfect sense - I just hope they are getting rid of this gcj nonsense with the new Judge.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Sep 14, 2006 6:57 pm

Well, I guess it will take a while until we see "normal" Java, so I will share what I just found out about the I/O:

You don't have to read input byte by byte - you can use a (sort of a) buffered input with System.in.read(byte[],int,int).

Recently there were some problems in which I couldn't even read the input within time limit. So I played around with some I/O and found out that read(byte[],int,int) for some reason doesn't work for lengths > 2048.

So this is how I read those types of inputs.
Note 1: input file must be small enough so you don't get MLE - but it should be ok up to ~27MB. Pick powers of two - 8388608 is better than 7800000, for instance.
Note 2: This code deals with ints only and it will fail to read -2^31 - if you need something like that, change to longs or something. I haven't used it to read Strings... I will eventually. It is best to use it for inputs containing ints in which you are given the number of test cases (so you don't look for the end of input)
Note 3: It can be modified to read lines - take that code from nextInt() and fiddle with it...

Code: Select all

import java.io.IOException;

class MainReadAll {

	int inputIndex;

	int inputSize;

	byte[] input;

	void work() {

		readAll(65536); // pick estimated size of input - powers of two work the
		                       // best
		int n;
		while((n=nextInt())!= Integer.MIN_VALUE){
			// do stuff
		}
	}

	private void readAll(int bufSize) {
		input = new byte[bufSize];
		int start = 0;
		inputSize = 0;
		while (true) {
			try {
				int read = System.in.read(input, start, 2048);
				inputSize += read;
				if (read < 2048)
					break;
				start += 2048;
			} catch (IOException e) {
			}
		}
		inputIndex = 0;
	}

	private int nextInt() {
		// find first digit
		while (input[inputIndex] < '-') {
			if (inputIndex == inputSize)
				return Integer.MIN_VALUE;
			inputIndex++;
		}
		int k = 0;
		int sign = 1;
		if (input[inputIndex] == '-') {
			inputIndex++;
			sign = -1;
		} else
			k = input[inputIndex++] - 48;
		// read the number
		while (input[inputIndex] >= '0' && input[inputIndex] <= '9') {
			k *= 10;
			k += (input[inputIndex++] - 48);
		}
		return k * sign;
	}

	public static void main(String args[]) {
		MainReadAll myWork = new MainReadAll();
		myWork.work();
	}
}

Please try modifying it to suit your needs or particular problem's I/O, this code is a problem specific one - meaning, please don't complain that it doesn't work for problem #12345 or something

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Java support still inadequate

Post by MAK » Sun Dec 31, 2006 10:48 am

It's sad to see that even after so much time Java support at this OJ is still pathetic. I don't know why the people running this judge have to cripple java in such a way.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Mon Jan 01, 2007 2:51 pm

Is BigInteger class provided here ?

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Post by MAK » Tue Jan 02, 2007 1:09 pm

Is BigInteger class provided here ?
Nope. You have to make your own BigInteger class. I think there is an implementation posted somewhere in these forum Java pages.

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Interesting

Post by MAK » Tue Jan 02, 2007 10:38 pm

I just saw something very interesting at the Bug Fixes forum. Someone (probably one of the system admins) says that

1. Java uses 190+ MB of RAM just for a single System.out.println

2. Java is 'unsecure'. Java classes may illegally access system data or files.

I'm quite sure that the second statement is false.
I have a similar feeling about the first one too, but I've never tried measuring the amount of memory taken up any of my Java programs, so I wouldn't know for sure. Can someone shed some light on this?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Jan 02, 2007 10:52 pm

No, I don't think that the first statement was made by an admin. I think someone saw the memory usage on SPOJ, which allocates 192MB, but that doesn't mean it uses that much.

There is probably a better way (especially with Java 1.6, from what I understand), but you can try how much memory your program uses by limiting the heap memory with -Xmx switch, e.g.:
java -Xmx16m Main.java < in

Play with the number and soon you'll find out how much memory you need. Now, that being said, I ran into couple of problems that, although they run with 16MB heap on my PC they run out of memory on UVa, and it is limited to 32MB.

Why these things happen? No idea, but it probably has something to do with the fact that UVa uses gcj, who knows how that thing compiles Java code to binary (it is compatible with Java 1.1, that's why Java is very limited here).

That probably explains why "Java" is able to access restricted functions, if they were running a bytecode within a JVM, it wouldn't be a problem.

MaVa
New poster
Posts: 6
Joined: Wed Oct 25, 2006 6:01 pm

Some Java speed tricks

Post by MaVa » Fri Feb 09, 2007 2:07 am

I code only java, shure it is a pain in the ... sometimes.
but in real competitions it is a good choice.

Java is not that much slower on input and output, but you must take care!!

1. using System.out.print*() will make the stream flush, which takes time, by using System.out.write() you can save time, and gain work.
(try on 10189)

2. readLn() metods given as examle on the page is slow, because when you make an array such as byte[] java must make shure all bytes are decleared to right initial value, as opposed to C. Using a small array speed thing up.

3. Integer.parseInt() is not optimized either, to many checks for invalid arguments. On this site you can rely on input-format!!
(if it says positive numbers, dont check for minus signs)

I dont know how to best test the difference in input speed, but even on problems with lots of input I think it is possible to make fast java programs.
There is indeed some difference in I/O-speed.

Good Luck
MaVa

Post Reply

Return to “Java”