结构切片使用太多内存

Question

我尝试用 BFS 解决 this 问题，但是对于输入“99 100”，我的程序使用了超过 260 Mb 并且在线判断系统抛出 MEMORY_LIMIT_EXCEEDED。我想问题是我使用 QUEUE 的方式。那么你认为问题是什么？我该如何解决？

这是我的代码。提前致谢！:

package main

import (
    "fmt"
)

type pair struct {
    nn int
    dd int
}

func main() {
    var n, m int
    fmt.Scanf("%d%d", &n, &m)

    if n >= m {
        fmt.Println(n - m)
    } else {
        device := make([]pair, 1)
        device[0] = pair{n, 0}

        ans := 0
        for {
            // pop front element
            tmp := device[0]
            device = device[1:]

            if tmp.nn == m { // reached destination
                ans = tmp.dd
                break
            }

            // add neighbors to the queue
            device = append(device, pair{tmp.nn - 1, tmp.dd + 1})
            device = append(device, pair{tmp.nn * 2, tmp.dd + 1})
        }

        fmt.Println(ans)
    }
}

编辑：更具可读性和工作性（已接受）的代码：

package main

import (
    "fmt"
)

type pair struct {
    location int
    dist     int
}

func main() {
    var n, m int
    fmt.Scanf("%d%d", &n, &m)

    if n >= m {
        fmt.Println(n - m)
    } else {
        visited := make([]bool, m+2)

        queue := make([]pair, 1)
        queue[0] = pair{n, 0}

        ans := 0
        visited[n] = true
        for {
            // pop front element
            tmp := queue[0]
            queue = queue[1:]

            // reached destination
            if tmp.location == m {
                ans = tmp.dist
                break
            }

            // add neighbors to the queue
            if tmp.location*2 <= m+1 && visited[tmp.location*2] == false {
                queue = append(queue, pair{tmp.location * 2, tmp.dist + 1})
                visited[tmp.location*2] = true
            }
            if tmp.location-1 >= 0 && visited[tmp.location-1] == false {
                queue = append(queue, pair{tmp.location - 1, tmp.dist + 1})
                visited[tmp.location-1] = true
            }
        }

        fmt.Println(ans)
    }
}

Answer 1

你的算法不是BFS，因为，同一个状态你可以访问不止一个。

例如，4 -> 3 -> 6 和 4 -> 8 -> 7 -> 6，其中 6 最终会被处理两次。

其次，对于大于target的数字x，最小步数总是

x - target + step to reach x

所以你不应该将它添加到队列中。

通过这两个修改，space 复杂度将限制为 O(m)，这应该可以帮助您解决问题。

示例代码

ans := -1
dist := make([]int, m + 1)
q := make([]int,1)
q[0] = n

for i := 0; i < len(q); i++ {
    node := q[i]
    if node == m {
       if ans == -1 || ans > dist[m]{
          ans = dist[m]
       }
       break;
    }
    a := node*2
    b := node - 1
    if a >= m {
       if ans == -1 || ans > (1 + dist[node] + a - m) {
          ans = 1 + dist[node] + a - m
       }
    }else if dist[a] == 0 && a != n {
       q = append(q, a)
       dist[a] = 1 + dist[node]
    }
    if dist[b] == 0 && b != n {
       q = append(q, b)
       dist[b] = 1 + dist[node]
    } 
}
return ans

Answer 2

第一眼告诉我，对于每个 dd，队列中将有一个 2^dd 个元素。并且答案预计大于，比如说，50，这是一个保证的内存限制超过。

一个非常简单和常见的优化是跟踪访问过的节点（nn 在你的例子中）。创建一个 map[int]bool（因为 dd 只会增加，所以没有理由记录最后访问的值）并且不要添加到队列中。

如评论中所述，另一个优化是不将大于 targets 的 nn 添加到队列中。这有点复杂，因为您需要记录一个值 res = min(res, dd+nn-target)，其中 nn 是大于目标的值，而 dd 是获得该值的步骤。如果当前的 dd 大于 res，你也想中断。

已接受答案的代码有错误。它从不尝试确定 b 是否小于零。给定设计的测试用例，可能会发生范围索引的运行时恐慌。

结构切片使用太多内存

slice of struct uses too much memory

algorithm

go

memory-management

breadth-first-search