How Can bufio.Scanner and Optimized Number Conversion Speed Up Input Scanning in Go Programs?

Improving Input Scanning Speed for Faster Program Execution

Problem Statement

The given code attempts to solve a SPOJ problem by iterating over a list of numbers and determining if each number is divisible by a constant k. However, the execution times out due to perceived slow input scanning.

Solution

Utilizing bufio.Scanner

To enhance input scanning efficiency, we can leverage bufio.Scanner, which is tailored for high-speed line-by-line input handling. Instead of the default fmt.Scan, we employ bufio.Scanner to retrieve input lines.

Optimizing Number Conversion

For improved number conversion, we introduce the toInt() function, which directly extracts numbers from raw input bytes. This avoids the slower conversion method of Scanner.Text() and eliminates unnecessary string creation.

toInt() achieves this by iterating through the input bytes and incrementally multiplying the result by 10. The bytes correspond to the UTF-8 encoded sequence of the number's decimal representation.

Code Snippet

The revised code snippet below incorporates these optimizations:

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
}

Additional Notes

This optimized solution demonstrates a significant improvement in execution speed compared to previous methods. It assumes valid input, including the presence of n lines after the initial input.

For scenarios involving closed input, a simplified for loop can be used:

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

The above is the detailed content of How Can bufio.Scanner and Optimized Number Conversion Speed Up Input Scanning in Go Programs?. For more information, please follow other related articles on the PHP Chinese website!