Faster input scan

Question

I am trying to solve the SPOJ question which can be found here

The following is my solution:

package main import "fmt" import "bufio" import "os" func main() { var n, k int var num int var divisible int in := bufio.NewReader(os.Stdin) fmt.Fscan(in, &n) fmt.Fscan(in, &k) for n > 0 { fmt.Fscan(in, &num) if num%k == 0 { divisible++ } n-- } fmt.Println(divisible) } 

The code is working fine. The problem here is that I get a timeout when I execute it in SPOJ.

At first I used only fmt.Scan , but then I came across this stream, which suggested instead of bufio use bufio to scan input faster.

But I still get a timeout. I just loop to get all the inputs, and inside this loop I determine if the input is divisible or not. Therefore, I believe that this is not a cycle, but an input scan that takes time. How can I improve this to read input faster? Or is the problem elsewhere?

Answer 1

You can use bufio.Scanner to read lines from input.

And since we always read numbers, we can create a highly optimized converter to get the number. We should avoid using Scanner.Text() , which creates a string , since we can only get the number from the raw bytes returned by Scanner.Bytes() . Scanner.Text() returns the same token as Scanner.Bytes() , but first converts to string , which is obviously slower and generates garbage and works for gc.

So, here is a converter function that gets int from raw bytes:

 func toInt(buf []byte) (n int) { for _, v := range buf { n = n*10 + int(v-'0') } return } 

This toInt() works because []byte contains an encoded sequence of UTF-8 bytes of a string representation of the decimal format of the number, which contains only digits in the range '0'..'9' , whose encoded bytes of UTF-8 are mapped one to one ( one byte is used for one digit). The mapping from a digit to a byte is just a shift: '0' -> 48 , '1' -> 49 , etc.

Using this is your complete application:

 package main import ( "bufio" "fmt" "os" ) func main() { var n, k, c int scanner := bufio.NewScanner(os.Stdin) scanner.Scan() fmt.Sscanf(scanner.Text(), "%d %d", &n, &k) for ;n > 0; n-- { scanner.Scan() if toInt(scanner.Bytes())%k == 0 { c++ } } fmt.Println(c) } func toInt(buf []byte) (n int) { for _, v := range buf { n = n*10 + int(v-'0') } return } 

This solution is about 4 times faster than calling strconv.Atoi() .

Notes:

In the above solution, I assumed that the input is valid, that is, it always contains valid numbers and contains at least n lines after the first (which gives us n and k ).

If the input is closed after n+1 lines, we can use a simplified for (and we don’t even need to reduce and rely on n ):

 for scanner.Scan() { if toInt(scanner.Bytes())%k == 0 { c++ } } 

Answer 2

Try using bufio.Scanner (as indicated in the mentioned topic):

 fmt.Scan(&n) fmt.Scan(&k) scanner := bufio.NewScanner(os.Stdin) for n > 0 { scanner.Scan() k, _ := strconv.Atoi(scanner.Text()) ...