更快的输入扫描 [英] Faster input scanning
问题描述
我试图解决可以在此处找到的SPOJ问题
以下是我的解决方案：
包主
导入fmt
导入bufio
导入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％k == 0 {
可分++ ++
}
n -
}
fmt.Println（可分割）
}
代码正常工作。这里的问题是，我在SPOJ中执行它时遇到了超时。
我第一次只使用 fmt.Scan 但我碰到了这个线程，这表明我使用 bufio 来代替更快的输入扫描。
但我仍然遇到超时问题。我只循环获取所有输入，并在此循环中确定输入是否可分。所以，我相信它不是循环，而是需要时间的输入扫描。我该如何改进以更快地读取输入？或者问题出在别的地方了？
bufio /＃Scannerrel =noreferrer> bufio.Scanner 可读取输入中的行。
既然我们一直在阅读数字，我们可以创建一个高度优化的转换器来获取数字。我们应该避免使用 Scanner.Text（） ，它会创建一个字符串，因为我们可以从 Scanner.Bytes（） 。 Scanner.Text（）返回与 Scanner.Bytes（）相同的标记，但它首先转换为 string 这显然比较慢，会生成垃圾并为gc工作。
所以这是一个转换器函数，
$ p $ func toInt（buf [] byte）code> int （n int）{
for _，v：= range buf {
n = n * 10 + int（v-'0'）
}
return
}
这个 toInt（） code> [] byte 包含数字的十进制格式的字符串表示形式的UTF-8编码的字节序列，其中只包含'范围内的数字0'..'9'，它们的UTF-8编码字节是一对一映射的（一个字节用于一个数字）。从数字到字节的映射只是一个转换：'0' - > 48 ，'1' - >
$ b 使用这个完整的应用程序：
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（）$ b $如果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
}
此解决方案比调用 <$ c $快4倍c> strconv.Atoi（） 为例。
注释：
在上面的解决方案中，我假定输入是有效的，也就是说它总是包含有效的数字，并且在第一个输入后包含至少 n 这给了我们 n 和 k ）。
输入在 n + 1 行之后关闭，我们可以使用来简化（而且我们甚至不需要以减少并依赖 n ）：
for scanner.Scan ）{
if toInt（scanner.Bytes（））％k == 0 {
c ++
}
}
I am attempting to solve the SPOJ question that can be found here
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 works fine. The issue here is that I get a timeout when I execute it in SPOJ.
I was first using only fmt.Scan but I then came across this thread that suggested that I use bufio instead for faster input scanning.
But I still get a timeout issue. I am only looping to get all the inputs and within this loop itself I determine whether the input is divisible or not. So, I believe that its not the loop but the input scanning that's taking time. How can I improve this to read the input faster? Or is the issue somewhere else?
You can use bufio.Scanner to read lines from the input.
And since we're always reading numbers, we can create a highly optimized converter to get the number. We should avoid using Scanner.Text() which creates a string as we can obtain the number just from the raw bytes returned by Scanner.Bytes(). Scanner.Text() returns the same token as Scanner.Bytes() but it first converts to string which is obviously slower and generates "garbage" and work for the gc.
So here is a converter function which obtains an int from the raw bytes:
func toInt(buf []byte) (n int) {
for _, v := range buf {
n = n*10 + int(v-'0')
}
return
}
This toInt() works because the []byte contains the UTF-8 encoded byte sequence of the string representation of the decimal format of the number, which contains only digits in the range of '0'..'9' whose UTF-8 encoded bytes are mapped one-to-one (one byte is used for one digit). The mapping from digit to byte is simply a shift: '0' -> 48, '1' -> 49 etc.
Using this 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() for example.
Notes:
In the above solution I assumed 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 decrement and rely on n):
for scanner.Scan() {
if toInt(scanner.Bytes())%k == 0 {
c++
}
}
这篇关于更快的输入扫描的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
