更快的输入扫描

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从原始字节获取an的转换器函数：

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