Golang代码在Hackerrank上运行太慢了。

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

Golang code too slow for Hackerrank

问题

我一直在尝试解决这个Hackerrank挑战：链接

你需要做以下事情：

你有一个大矩阵：

  1. 1 1 1 1 1 1
  2. 1 1 1 1 1 1
  3. 1 1 1 1 1 1
  4. 1 1 1 1 1 1
  5. 1 1 1 0 1 1

和一个小矩阵：

  1. 1 1 1
  2. 1 1 1
  3. 1 1 0

你需要找出小矩阵是否存在于大矩阵中。

最多有5个测试用例，每个矩阵的大小最大为1000x1000，并且我需要在4秒内解决这个问题。

我的代码在最大输入情况下超时，我想也许是因为我扫描矩阵的方式太慢了。

这是我的代码：

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"strconv"
  6. 	"strings"
  7. )
  9. func main() {
  10. 	var t, rL, cL, rS, cS, temp int
  11. 	var s string
  12. 	var sl []string
  13. 	var mxL, mxS [][]int
  14. 	var found bool
  15. 	fmt.Scanf("%d", &t)
  16. 	for ; t > 0; t-- {
  17. 		// 开始扫描输入
  18. 		// 扫描大矩阵
  19. 		fmt.Scanf("%d%d", &rL, &cL)
  20. 		mxL = make([][]int, rL)
  21. 		for i := range mxL {
  22. 			mxL[i] = make([]int, cL)
  23. 		}
  24. 		for i := 0; i < rL; i++ {
  25. 			fmt.Scanf("%s", &s)
  26. 			sl = strings.Split(s, "")
  27. 			for j, v := range sl {
  28. 				temp, _ = strconv.Atoi(v)
  29. 				mxL[i][j] = temp
  30. 			}
  31. 		}
  32. 		// 扫描小矩阵
  33. 		fmt.Scanf("%d%d", &rS, &cS)
  34. 		mxS = make([][]int, rS)
  35. 		for i := range mxS {
  36. 			mxS[i] = make([]int, cS)
  37. 		}
  38. 		for i := 0; i < rS; i++ {
  39. 			fmt.Scanf("%s", &s)
  40. 			sl = strings.Split(s, "")
  41. 			for j, v := range sl {
  42. 				temp, _ = strconv.Atoi(v)
  43. 				mxS[i][j] = temp
  44. 			}
  45. 		}
  46. 		// 停止扫描输入
  47. 		// 开始在大矩阵中搜索小矩阵
  48. 		found = true
  49. 		for iL := 0; iL <= rL-rS; iL++ {
  50. 			for jL := 0; jL <= cL-cS; jL++ {
  51. 				found = true
  52. 				if mxL[iL][jL] == mxS[0][0] {
  53. 					for iS := 0; iS < rS; iS++ {
  54. 						for jS := 1; jS < cS; jS++ {
  55. 							if mxS[iS][jS] != mxL[iS+iL][jS+jL] {
  56. 								found = false
  57. 								break
  58. 							}
  59. 						}
  60. 						if !found {
  61. 							break
  62. 						}
  63. 					}
  64. 					if found {
  65. 						break
  66. 					}
  67. 				} else {
  68. 					found = false
  69. 				}
  70. 			}
  71. 			if found {
  72. 				fmt.Println("YES")
  73. 				break
  74. 			}
  75. 		}
  76. 		if !found {
  77. 			fmt.Println("NO")
  78. 		}
  79. 		// 停止在大矩阵中搜索小矩阵
  80. 	}
  81. }

我使用了一个整数切片的切片来存储输入。

mxL是大矩阵，mxS是小矩阵。

rL和cL表示大矩阵的行和列。

rS和cS表示小矩阵的行和列。

英文:

I've been trying to solve this Hackerrank challenge: Link

This is what you have to do:

You have one large matrix:

  1. 1 1 1 1 1 1
  2. 1 1 1 1 1 1
  3. 1 1 1 1 1 1
  4. 1 1 1 1 1 1
  5. 1 1 1 0 1 1

and one small matrix:

  1. 1 1 1
  2. 1 1 1
  3. 1 1 0

You have to find out if the small matrix is present in the large matrix.

There are up to 5 testcases and each matrix can be of max 1000x1000 size and I need to solve this in under 4 seconds.

My code timeouts for the largest possible input, I thought that maybe how I'm scanning the matrix is too slow.

This is my code:

  1. package main
  2. import (
  3. &quot;fmt&quot;
  4. &quot;strconv&quot;
  5. &quot;strings&quot;
  6. )
  7. func main() {
  8. var t, rL, cL, rS, cS, temp int
  9. var s string
  10. var sl []string
  11. var mxL, mxS [][]int
  12. var found bool
  13. fmt.Scanf(&quot;%d&quot;, &amp;t)
  14. for ; t &gt; 0; t-- {
  15. // Start scanning input
  16. // Scanning large matrix
  17. fmt.Scanf(&quot;%d%d&quot;, &amp;rL, &amp;cL)
  18. mxL = make([][]int, rL)
  19. for i := range mxL {
  20. mxL[i] = make([]int, cL)
  21. }
  22. for i := 0; i &lt; rL; i++ {
  23. fmt.Scanf(&quot;%s&quot;, &amp;s)
  24. sl = strings.Split(s, &quot;&quot;)
  25. for j, v := range sl {
  26. temp, _ = strconv.Atoi(v)
  27. mxL[i][j] = temp
  28. }
  29. }
  30. // Scanning small matrix
  31. fmt.Scanf(&quot;%d%d&quot;, &amp;rS, &amp;cS)
  32. mxS = make([][]int, rS)
  33. for i := range mxS {
  34. mxS[i] = make([]int, cS)
  35. }
  36. for i := 0; i &lt; rS; i++ {
  37. fmt.Scanf(&quot;%s&quot;, &amp;s)
  38. sl = strings.Split(s, &quot;&quot;)
  39. for j, v := range sl {
  40. temp, _ = strconv.Atoi(v)
  41. mxS[i][j] = temp
  42. }
  43. }
  44. // Stop scanning input
  45. // Start searching for small matrix in large matrix
  46. found = true
  47. for iL := 0; iL &lt;= rL-rS; iL++ {
  48. for jL := 0; jL &lt;= cL-cS; jL++ {
  49. found = true
  50. if mxL[iL][jL] == mxS[0][0] {
  51. for iS := 0; iS &lt; rS; iS++ {
  52. for jS := 1; jS &lt; cS; jS++ {
  53. if mxS[iS][jS] != mxL[iS+iL][jS+jL] {
  54. found = false
  55. break
  56. }
  57. }
  58. if !found {
  59. break
  60. }
  61. }
  62. if found {
  63. break
  64. }
  65. } else {
  66. found = false
  67. }
  68. }
  69. if found {
  70. fmt.Println(&quot;YES&quot;)
  71. break
  72. }
  73. }
  74. if !found {
  75. fmt.Println(&quot;NO&quot;)
  76. }
  77. // Stop searching for small matrix in large matrix
  78. }
  79. }

I'm using a slice of slices of ints to store the input.

mxL is the large matrix and mxS is the small matrix.

rL and cL stand for row and column of the large matrix.

rS and cS stand for row and column of the small matrix.

答案1

得分: 2

好的，以下是翻译好的内容：

我将给你指出一个想法，然后你可以尝试实现它。首先创建一个与你的大数组一样大的新的二维数组，称之为sumArray。现在让sumArray中的每个单元格表示以当前单元格为最左下角单元格时的总和。现在你只需要检查与你的小数组具有相同总和的单元格，而不是检查数组中的每个元素。

所以如果这是你的输入：

  1. 1 1 1 1 1 1     
  2. 1 1 1 1 1 1
  3. 1 1 1 1 1 1
  4. 1 1 1 1 1 1
  5. 1 1 1 0 1 1
  6. 1 1 1
  7. 1 1 1
  8. 1 1 0

首先计算小数组的总和 --> 8

现在让我展示一下你的sumArray会是什么样子：

  1. -1 -1 -1 -1 -1 -1     -1表示我们不能在这个位置求和，因为
  2. -1 -1 -1 -1 -1 -1      尺寸比你的小数组还要小
  3. -1 -1  9  9  9  9      每个单元格表示原始矩阵值的总和。
  4. 9  9  9  9  9  9
  5. 9  9  9  8  9  9

现在如果你只扫描这个数组，你会发现你将把搜索空间从每个可能的位置减少到只有总和相等的位置。这并不能保证数组就在这个位置，你仍然需要添加一个验证步骤，但它减少了你的搜索空间。

英文:

Well I am gonna point out an idea to you and then you can try to implement it. So create a new 2d array as large as your large array. Call it sumArray. Now let each cell in this sumArray represent the sum where the current cell is the most bottom-left cell. Now what you do is check only the cells that has the same sum as your small array instead of checking every element in the array.
<br>

So if those are your inputs

  1. 1 1 1 1 1 1     
  2. 1 1 1 1 1 1
  3. 1 1 1 1 1 1
  4. 1 1 1 1 1 1
  5. 1 1 1 0 1 1
  6. 1 1 1
  7. 1 1 1
  8. 1 1 0

First sum your small array --> 8

Now let me show you how your sum array would look like

  1. -1 -1 -1 -1 -1 -1     -1 means that we can&#39;t sum at this point because
  2. -1 -1 -1 -1 -1 -1      the dimensions are just smaller than your small array
  3. -1 -1  9  9  9  9      each other cell represent the sum of your original 
  4. 9  9  9  9  9  9      matrix values.
  5. 9  9  9  8  9  9

Now if you scan trough this array only you can see that you will reduce your search space from every possible position to only the position where your sum is equal. This doesn't guarantee that the array are in this position you still have to add a verification step but it reduce your search space.

huangapple
  • 本文由 发表于 2015年9月18日 21:20:24
  • 转载请务必保留本文链接：https://go.coder-hub.com/32653087.html
  • algorithm
  • go
  • performance
匿名

发表评论

匿名网友

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

确定