Fast IO

[chili5]

I was working on a UVA problem involving sorting and outputting a large amount of numbers. The problem that I am having is that my program is taking far too long. I've looked around online for faster IO methods but I can't find anything. All I can find is Scanner (which is slow) and BufferedReader (which doesn't help much).

I end up with this code:

CODE:

import java.util.*; import java.io.*; /**  *  * @author James Brocklebank  */ class Main {     /**      * @param args the command line arguments      */     public static void main(String[] args) throws IOException {        //Scanner fin = new Scanner(new FileReader("age.txt"));        Scanner fin = new Scanner(System.in);        Vector<Integer> v = new Vector<Integer>();        int n;        while (true) {            n = fin.nextInt();            if (n == 0) {                break;            }            v.clear();            for (int i=0;i<n;i++) {                v.add(fin.nextInt());            }            Collections.sort(v);            System.out.println(v.toString().replaceAll("[^0-9\\s]", ""));        }        fin.close();     } }

It works correctly but takes far too long because of the input. Does anybody know any faster way to do input in Java?

Sure, I can use C++ and get faster input but my language of choice is Java (and I don't want to be limited by my language). However, this input thing is making me hate Java.

CODE:

#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; #ifndef ONLINE_JUDGE    ifstream in("data.txt");    ofstream out("out.txt"); #else    istream &in = cin;    ostream &out = cout; #endif int main() {     int n;     while (true) {             in >> n;             if (n == 0) {                 break;             }             vector<int> v(n, 0);             for (int i=0;i<n;i++) {                 in >> v[i];             }             sort(v.begin(),v.end());             for (int i=0;i<n;i++) {                     out << v[i];                     if (i != n-1) {                             out << " ";                     }             }             out << endl;     }     return 0; }

[saltpro15]

I think you may be forced into using C++ ...

and for future reference, adding

c++:

ios::sync_with_stdio(false);

makes cin/cout 2-3 times faster, but breaks the sync with stdio (meaning you can't combine cin with scanf or printf with cout)

++i is (marginally) faster than i++

and remember to ALWAYS CHECK OUTPUT FORMATTING. That has caused me many headaches

Enjoy the world of online judges

[Tony]

saltpro15 @ Tue Oct 27, 2009 7:56 pm wrote:

++i is (marginally) faster than i++

So what is that margin, as compared to the IO inside of that ++i loop?

[DemonWasp]

Change Vector<> to List<> / ArrayList<> unless you're dead certain you need the synchronization. Vector<> is thread-safe, which means it does lots of extra work. Secondly, you're providing an initial size to the C++ version, but not the Java version. The gain should be minimal, but will be there.

Next, please supply the input file you're testing with, so we can also test.

Also, ++i isn't any faster than i++ unless:
- You are working with some class that overloads ++, in which case that operator (may) make a duplicate of that class to call the increment operator on.
- Your compiler is set to absolutely-no-optimisations mode (this is -O0 in gcc/g++). I don't even know if you can run Java in that mode.

[chili5]

I changed to Array List but that didn't really help any.

My input file is:

5
3 4 2 1 5
5
2 3 2 3 1
0

However, the problem is that on bigger input sizes it times out. So is there any faster methods of reading input from the command line?

[Tony]

are you sure that you are timing out on IO and not on .sort or .replaceAll ?

[DemonWasp]

That example input shouldn't do anything nasty. Are you sure that the input is valid? If the 0 appears somewhere in one of the lines, rather than as one of the counts, your program will sit there forever, looking for more input on System.in without ever receiving any (and thus fails after timing out).

You should be able to load perhaps a few dozen megabytes per second with a mechanism like you have there, assuming the machine isn't under heavy load. Unless you have a completely ridiculous input file, you should be just fine.