更快的输入扫描

Question

我试图解决可以在这里找到的SPOJ问题

以下是我的解决方案:

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)
}

代码工作正常.这里的问题是我在SPOJ中执行它时会出现超时.

我是第一次使用,fmt.Scan但后来我遇到了这个线程,建议我使用bufio更快的输入扫描.

但我仍然遇到超时问题.我只是循环以获取所有输入,并且在此循环内我确定输入是否可被整除.所以,我认为它不是循环,而是输入扫描需要时间.如何改进这一点以更快地读取输入？或者是其他地方的问题？

Answer 1

您可以使用bufio.Scanner从输入中读取行.

由于我们总是在阅读数字,因此我们可以创建一个高度优化的转换器来获取数字.我们应该避免使用Scanner.Text()哪个创建一个,string因为我们可以从返回的原始字节中获取数字Scanner.Bytes().Scanner.Text()返回相同的令牌,Scanner.Bytes()但它首先转换string为明显较慢并生成"垃圾"并为gc工作.

所以这是一个转换器函数,它int从原始字节中获取:

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

这是toInt()有效的,因为[]byte它包含数字十进制格式的字符串表示的UTF-8编码字节序列,其仅包含'0'..'9'UTF-8编码字节一对一映射范围内的数字(使用一个字节)一位数).从数字到字节的映射是一个简单的移位:'0' -> 48,'1' -> 49等

使用此完整的应用程序:

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
}

该解决方案比例如调用快约4倍strconv.Atoi().

笔记:

在上面的解决方案中,我假设输入是有效的,即它总是包含有效数字,并且至少包含n第一个之后的行(它给出了我们n和k).

如果输入在行之后关闭n+1,我们可以使用简化for(我们甚至不需要减少和依赖n):

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