8 replies to this topic

[chili5]

The problem I am having is this, you are given two numbers of length M and you want to find the sum of them. However, the numbers are given in columns like this:

Quote

1 3
2 4
5 6
7 8

The program would then respond with the sum of 1257 + 3468. Since M can be at most 1 million digits, it makes sense to use a big integer. I did that and what I find is my program takes too long. It's not the addition that is taking too long, is the fact that I am looping 1 million times to build the nums.

Adding is fast and easy. I thought what I would do is instead of building strings is I would add the two digits and then a second iteration would deal with carries. However that is even worse because it would perform two 0(n) iterations. My first program required one 0(n) iteration but that still took way too long.

The problem is input takes way too long. The program has to run in 3 seconds but it takes 30 seconds to read the input. Does anybody know any faster way to read input?

Anyway my two attempts are:

import java.util.*;

import java.io.*;


class Main {


    /**

     * @param args the command line arguments

     */

    public static void main(String[] args) throws IOException {

        //Scanner fin =new Scanner(new FileReader("sums.txt"));

        Scanner fin = new Scanner(System.in);

        int[] nums;


        int N;

        int length; // length of each number



        N = fin.nextInt();


        while (N > 0) {


            length = fin.nextInt();


            nums = new int[length];


            for (int i=0;i<length;i++) {

                nums[i] = fin.nextInt() + fin.nextInt();

            }


            for (int i=length-1;i>0;i--) {

                nums[i-1] += (nums[i]/10);

                nums[i] %= 10;

                System.out.print(nums[i]);

            }

            System.out.println();

                  

            N--;



            if (N != 0) {

                System.out.println();

            }

        }

        

        fin.close();

    }

}

Big Integer:

import java.util.*;

import java.io.*;

import java.math.BigInteger;


class Main {


    /**

     * @param args the command line arguments

     */

    public static void main(String[] args) throws IOException {

        //Scanner fin =new Scanner(new FileReader("sums.txt"));

        Scanner fin = new Scanner(System.in);


        int N;

        int length; // length of each number

        String sNum1 = "";

        String sNum2 = "";


        N = fin.nextInt();


        while (N > 0) {


            length = fin.nextInt();

            sNum1 = "";

            sNum2 = "";


            for (int i=0;i<length;i++) {

                sNum1 += fin.nextInt();

                sNum2 += fin.nextInt();

            }


            System.out.println(new BigInteger(sNum1).add(new BigInteger(sNum2)));

           

                  

            N--;



            if (N != 0) {

                System.out.println();

            }

        }

        

        fin.close();

    }

}

I'm sure my algorithms are correct. They get the correct answer but they don't run quick enough. Thoughts? I thought to use buffered input. Would that make it fast enough? There is a lot that I do not know about input. I know enough to be functional but it is evident that the Scanner is not efficient for large inputs.

What about scanf or cin? It's a different language but is it possible that methods in Java just aren't fast enough?

[debtboy]

Can you "shell out" of Java or extend it to include shell commands.

You need a very fast way to extract large vertical numbers from the horizontal lines of a file.

I believe there is no faster way than this:

First number:
cut -c1 file | paste -s -d ""  

second number:
cut -c1 file | paste -s -d ""

Here it is in action:




Could easily script the whole function with just a few more lines of code.
Got to love the Linux kernel :D

[chili5]

Quote

Can you "shell out" of Java or extend it to include shell commands.

No! When I submit my program, I have no access to the settings of the compiler. Plus, the judge disables functions like this.

I would love to be able to read data column at a time. It would be so easy.

Would buffered input be any faster?

[ZekeDragon]

You can start at the end of an input file, right? Why not iterate from the bottom of the file instead of the top, adding and using simple mathematics all the way up, that way you're just seeking to the bottom, then adding the two numbers that you getline, and if you need to carry a one, you add that to the next iteration one line up all the way to the top. That should be pretty efficient and if you put the results into a char array/string = # of lines in file + 1 you should be able to do everything with one memory allocation. :)

[Aereshaa]

assuming each line is strictly in a format like "00\n", then you can memory map the file and iterate the pointers to digits backwards, 3 at a time.

[chili5]

Still looking for a way to do this in Java.

By the way, in C++ this works with just using cin and cout. The problem is the Scanner is java. However, I'm not going to worry about it. Thanks for the help everyone! It's more important that I got a functional algorithm not the stupid input problem with Java.

[ZekeDragon]

Don't use scanner. Use a CharacterStream instead, that should be much faster. You'll have to parse it yourself, but nonetheless it'll be pretty easy to do. :)

[chili5]

Thanks for that. I'll see if I can find something to do. I've used BufferedReader before. Do you think buffered input would be faster?

The scanner is so convenient to use though. Really really slow though.

[ZekeDragon]

BufferedReader on a CharacterStream would be fast. One load up for everything and immediate use of the character input. :)

Well you can also read line by line, parsing the String as input, and iterating through it. I don't know if that'd be slower or not. It'd be a LITTLE more convenient than CharacterStream.