我正在尝试解决可以在这里找到的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来进行更快的输入扫描。
fmt.Scan
bufio
但是我仍然遇到超时问题。我只是循环获取所有输入,并且在此循环本身中,我确定输入是否可分割。因此,我认为这不是循环而是输入扫描需要时间。如何改善此功能以更快地读取输入?还是这个问题在其他地方?
您可以用来bufio.Scanner从输入中读取行。
bufio.Scanner
由于我们一直在读取数字,因此我们可以创建一个高度优化的转换器来获取数字。我们应该避免使用Scanner.Text()创建一个,string因为我们只能从返回的原始字节中获取数字Scanner.Bytes()。Scanner.Text()返回与相同的令牌,Scanner.Bytes()但首先转换为令牌,该令牌string显然要慢一些并生成“垃圾”并为gc工作。
Scanner.Text()
string
Scanner.Bytes()
因此,这是一个int从原始字节获取an的转换器函数:
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等
toInt()
[]byte
'0'..'9'
'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()。
strconv.Atoi()
笔记:
在上面的解决方案中,我假设输入是有效的,也就是说,它始终包含有效的数字,并且至少包含n第一个之后的行(这给了我们n和k)。
n
k
如果输入在行后关闭n+1,我们可以使用简化的方法for(甚至不需要递减并依赖n):
n+1
for
for scanner.Scan() { if toInt(scanner.Bytes())%k == 0 { c++ } }