减少 Go 语言中求和代码的处理时间

huangapple go评论127阅读模式
英文:

Reducing the process time of the sum of numbers code in Go

问题

我写了这段代码,但是代码测试网站因为处理时间的原因拒绝了它。为了减少时间,我使用了双指针算法和Goroutine(我不确定我是否使用正确)。但是仍然因为同样的原因被网站拒绝了。有没有改进的解决方案来通过这个问题?我该如何减少处理时间。请检查我的代码。谢谢你的支持!

问题描述

存在一个由N个数字A[1],A[2],…,A[N]组成的序列。在这个序列中,从i到j的数字之和A[i]+A[i+1]+…编写一个程序,找出+A[j-1]+A[j]等于M的情况的数量。

输入

第一行给出N(1≤N≤10,000)和M(1≤M≤300,000,000)。下一行包含以空格分隔的A[1],A[2],…,A[N]。每个A[x]是不超过30,000的自然数。

输出

在第一行上输出情况的数量。

示例

  • 输入1:

    4 2

    1 1 1 1

  • 输出1:

    3

  • 输入2:

    10 5

    1 2 3 4 2 5 3 1 1 2

  • 输出2:

    3

  1. package main
  2. import "fmt"
  3. func main() {
  4. var n int //数字个数
  5. var m int //目标和
  6. c := make(chan []int)
  7. d := make(chan int)
  8. fmt.Scanf("%d %d\n", &n, &m)
  9. arr := make([]int, n)
  10. go ReadN(arr, n, c)
  11. go checker(<-c, n, m, d)
  12. fmt.Print(<-d)
  13. }
  14. func ReadN(arr []int, n int, c chan<- []int) {
  15. for i := 0; i < n; i++ {
  16. fmt.Scan(&arr[i])
  17. }
  18. c <- arr
  19. }
  20. func checker(arr []int, n, m int, d chan<- int) {
  21. var start int
  22. var end int
  23. var sum int
  24. var result int
  25. for start < n {
  26. if sum > m || end == n {
  27. sum -= arr[start]
  28. start++
  29. } else {
  30. sum += arr[end]
  31. end++
  32. }
  33. if sum == m {
  34. result++
  35. }
  36. }
  37. d <- result
  38. }
英文:

I wrote this code, but the code test site rejected due to process time. To reduce time, I used Two pointers algorism, and Goroutine(I am not sure I used it correctly). But still that site rejected with the same reason. Is there any improvement solution to pass this? How can I reduce processing time.
Please review my code. Thank you for your support!

Problem description

sequence of N numbers A[1], A[2], … , A[N] exists. The sum of numbers from i to j in this sequence A[i]+A[i+1]+… Write a program to find the number of cases where +A[j-1]+A[j] becomes M.

input

In the first line, N(1≤N≤10,000) and M(1≤M≤300,000,000) are given. The next line contains A[1], A[2], … , A[N] is given, separated by spaces. Each A[x] is a natural number not exceeding 30,000.

Print

the number of cases on the first line.

Example

  • input 1 :

    4 2

    1 1 1 1

  • output 1:

    3

  • input 2 :

    10 5

    1 2 3 4 2 5 3 1 1 2

  • output 2 :

    3

  1. package main
  2. import &quot;fmt&quot;
  3. func main() {
  4. var n int //numbers
  5. var m int //target sum
  6. c := make(chan []int)
  7. d := make(chan int)
  8. fmt.Scanf(&quot;%d %d\n&quot;, &amp;n, &amp;m)
  9. arr := make([]int, n)
  10. go ReadN(arr, n, c)
  11. go checker(&lt;-c, n, m, d)
  12. fmt.Print(&lt;-d)
  13. }
  14. func ReadN(arr []int, n int, c chan&lt;- []int) {
  15. for i := 0; i &lt; n; i++ {
  16. fmt.Scan(&amp;arr[i])
  17. }
  18. c &lt;- arr
  19. }
  20. func checker(arr []int, n, m int, d chan&lt;- int) {
  21. var start int
  22. var end int
  23. var sum int
  24. var result int
  25. for start &lt; n {
  26. if sum &gt; m || end == n {
  27. sum -= arr[start]
  28. start++
  29. } else {
  30. sum += arr[end]
  31. end++
  32. }
  33. if sum == m {
  34. result++
  35. }
  36. }
  37. d &lt;- result
  38. }

答案1

得分: 1

问题出在Scan和Scanf上。它们不进行任何缓冲,如果输入很多,会导致速度非常慢。所以我将所有的Scan和Scanf都改成了Fscan和Fscanf。另外,我使用了bufio包。然而,即使使用了Fscanf(),如果你对速度还不满意,你应该考虑使用Scanner。

以下是修改后的代码:

  1. package main
  2. import (
  3. "bufio"
  4. "fmt"
  5. "os"
  6. )
  7. func main() {
  8. var n int // 数字个数
  9. var m int // 目标和
  10. var bufin *bufio.Reader = bufio.NewReader(os.Stdin)
  11. fmt.Fscanf(bufin, "%d %d\n", &n, &m)
  12. arr := make([]int, n)
  13. arr = ReadN(arr, n, bufin)
  14. result := checker(arr, n, m)
  15. fmt.Print(bufout, result)
  16. }
  17. func ReadN(arr []int, n int, bufin *bufio.Reader) []int {
  18. for i := 0; i < n; i++ {
  19. fmt.Fscan(bufin, &arr[i])
  20. }
  21. return arr
  22. }
  23. func checker(arr []int, n, m int) int {
  24. var start int
  25. var end int
  26. var sum int
  27. var result int
  28. for start < n {
  29. if sum > m || end == n {
  30. sum -= arr[start]
  31. start++
  32. } else {
  33. sum += arr[end]
  34. end++
  35. }
  36. if sum == m {
  37. result++
  38. }
  39. }
  40. return result
  41. }
英文:

Problem was from Scan and Scanf. It doesn't do any buffering, which makes it very slow if you get a lot of input. So I changed all Scan, Scanf to Fscan, Fscanf. Instead, I used bufio package. However, if you are not satisfied with the speed even with Fscanf(), you should seriously consider using a Scanner.
See below code.

  1. package main
  2. import (
  3. &quot;bufio&quot;
  4. &quot;fmt&quot;
  5. &quot;os&quot;
  6. )
  7. func main() {
  8. var n int //numbers
  9. var m int //target sum
  10. var bufin *bufio.Reader = bufio.NewReader(os.Stdin)
  11. fmt.Fscanf(bufin, &quot;%d %d\n&quot;, &amp;n, &amp;m)
  12. arr := make([]int, n)
  13. arr = ReadN(arr, n, bufin)
  14. result := checker(arr, n, m)
  15. fmt.Print(bufout, result)
  16. }
  17. func ReadN(arr []int, n int, bufin *bufio.Reader) []int {
  18. for i := 0; i &lt; n; i++ {
  19. fmt.Fscan(bufin, &amp;arr[i])
  20. }
  21. return arr
  22. }
  23. func checker(arr []int, n, m int) int {
  24. var start int
  25. var end int
  26. var sum int
  27. var result int
  28. for start &lt; n {
  29. if sum &gt; m || end == n {
  30. sum -= arr[start]
  31. start++
  32. } else {
  33. sum += arr[end]
  34. end++
  35. }
  36. if sum == m {
  37. result++
  38. }
  39. }
  40. return result
  41. }

答案2

得分: 0

你可以使用前缀和算法来解决这种类型的问题,它可以在O(n)的时间和空间复杂度内完成。
你还可以参考这篇文章

如果想在这种类型的问题上进行练习,可以参考这个

英文:

You can solve this type of question using prefix-sum algorithm, which can do this in O(n) time and space.
You can also refer to this article.

For practice on this type of questions, refer this

huangapple
  • 本文由 发表于 2022年2月15日 19:16:20
  • 转载请务必保留本文链接:https://go.coder-hub.com/71125515.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定