做 BFS 时避免深度复制 [英] Avoid a deepcopy when doing a BFS

问题描述

我目前正在解决此作业中的第二个练习 (这不是作业，我其实是想解决这个其他问题).我的解决方案使用 BFS 来搜索熄灯"问题变体的最小解决方案，其中按下一个灯将翻转同一行同一列上每个灯的状态.

I'm currently solving the second exercise in this assignment (this is not homework, I'm actually trying to solve this other problem). My solution uses a BFS to search for the minimal solution to a variant of the "Lights Out" problem, in which pressing a light will flip the state of every light on the same row and the same column.

我认为我的实现是正确的，但它有点太慢了:目前在我的计算机上运行需要 12 秒以上(这对我来说是不可接受的).

I think that my implementation is correct, but it's a bit too slow: it's currently taking 12+ seconds to run on my computer (which is unacceptable for my purposes).

from copy import deepcopy
from itertools import chain
from Queue import PriorityQueue

# See: http://www.seas.upenn.edu/~cis391/Homework/Homework2.pdf
class Puzzle(object):
    def __init__(self, matrix):
        self.matrix = matrix
        self.dim = len(matrix)

    def __repr__(self):
        return str(self.matrix)

    def solved(self):
        return sum([sum(row) for row in self.matrix]) == 0

    def move(self, i, j):
        for k in range(self.dim):
            self.matrix[i][k] = (self.matrix[i][k] + 1) % 2
            self.matrix[k][j] = (self.matrix[k][j] + 1) % 2
        self.matrix[i][j] = (self.matrix[i][j] + 1) % 2

        return self

    def copy(self):
        return deepcopy(self)

    def next(self):
        result = []

        for i in range(self.dim):
            for j in range(self.dim):
                result.append(self.copy().move(i, j))

        return result

    def solve(self):
        q = PriorityQueue()
        v = set()

        q.put((0, self))
        while True:
            c = q.get()

            if c[1].solved():
                return c[0]
            else:
                for el in c[1].next():
                    t = el.tuple()

                    if t not in v:
                        v.add(t)
                        q.put((c[0] + 1, el))

    def tuple(self):
         return tuple(chain.from_iterable(self.matrix))

根据cProfile，罪魁祸首似乎是deepcopy 调用.另一方面，我看不到其他选择:我需要向队列中添加另一个 Puzzle 对象，其中包含 self.matrix 的新副本.

The culprit, according to cProfile, appears to be the deepcopy call. On the other hand, I see no alternatives: I need to add to the queue another Puzzle object containing a fresh copy of self.matrix.

如何加快实施速度?

这是我正在使用的测试用例:

Here's the test case that I'm using:

print Puzzle([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]).solve()

应该返回1(我们只需要按下右下角的灯)

which should return 1 (we only need to press the light in the lower right corner).

这是另一个粗糙的测试用例:

Here's another gnarly test case:

print Puzzle([
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
]).solve()

它的解决方案是最多14个:按下对角线上所有已经亮的灯.不幸的是，@zch 令人印象深刻的加速并不足以解决这个问题，让我相信，由于高分支因子，BFS 不是解决这个问题的正确方法.

Its solution is at most 14: press all lights on the diagonal that were already on. Unfortunately, the impressive speedup by @zch isn't enough to solve this problem, leading me to believe that, due to the high branching factor, a BFS wasn't the right way to solve this problem.

推荐答案

有许多优化要做.

首先，避免deepcopy，实现你自己的复制(这对我来说速度快了5倍):

First, avoid deepcopy, implement it your own copying (this by itself worked for me 5x faster):

class Puzzle(object):
    def __init__(self, matrix):
        self.matrix = [list(row) for row in matrix]
        self.dim = len(matrix)

    def copy(self):
        return Puzzle(self.matrix)

其次，在 BFS 中你不需要优先队列，使用 Queue 或实现你自己的队列.这提供了一些加速.第三，在放入队列之前检查是否已解决，而不是在取出后.这应该能让您在可比的时间内更深入一层:

Second, in BFS you don't need priority queue, use Queue or implement your own queuing. This gives some speedup. And third, check for being solved before putting it into the queue, not after taking things out. This should allow you to go one level deeper in comparable time:

def solve(self):
    v = set()

    q = [(0, self)]
    i = 0
    while True:
        c = q[i]
        i += 1

        for el in c[1].next():
            t = el.tuple()

            if t not in v:
                if el.solved():
                    return c[0] + 1
                v.add(t)
                q.append((c[0] + 1, el))

此外，使用位列表的内存效率非常低.您可以将所有位打包成一个整数并获得更快的解决方案.此外，您可以预先计算允许移动的掩码:

Further, using a list of list of bits is very memory-inefficient. You can pack all the bits into a single integer and get much faster solution. Additionally you can precompute masks for allowed moves:

def bits(iterable):
    bit = 1
    res = 0
    for elem in iterable:
        if elem:
            res |= bit
        bit <<= 1
    return res

def mask(dim, i, j):
    res = 0
    for idx in range(dim * i, dim * (i + 1)):
        res |= 1 << idx
    for idx in range(j, dim * dim, dim):
        res |= 1 << idx
    return res

def masks(dim):
    return [mask(dim, i, j) for i in range(dim) for j in range(dim)]

class Puzzle(object):
    def __init__(self, matrix):
        if isinstance(matrix, Puzzle):
            self.matrix = matrix.matrix
            self.dim = matrix.dim
            self.masks = matrix.masks
        else:
            self.matrix = bits(sum(matrix, []))
            self.dim = len(matrix)
            self.masks = masks(len(matrix))

    def __repr__(self):
        return str(self.matrix)

    def solved(self):
        return self.matrix == 0

    def next(self):
        for mask in self.masks:
            puzzle = Puzzle(self)
            puzzle.matrix ^= mask
            yield puzzle

    def solve(self):
        v = set()

        q = [(0, self)]
        i = 0
        while True:
            c = q[i]
            i += 1

            for el in c[1].next():
                t = el.matrix

                if t not in v:
                    if el.solved():
                        return c[0] + 1
                    v.add(t)
                    q.append((c[0] + 1, el))

最后，对于另一个因子 5，您可以只传递位矩阵，而不是整个 Puzzle 对象，并且还可以内联一些最常用的函数.

And finally for another factor of 5 you can pass around just bit matrices, instead of whole Puzzle objects and additionally inline some most often used function.

def solve(self):
    v = set()

    q = [(0, self.matrix)]
    i = 0
    while True:
        dist, matrix = q[i]
        i += 1

        for mask in self.masks:
            t = matrix ^ mask

            if t not in v:
                if t == 0:
                    return dist + 1
                v.add(t)
                q.append((dist + 1, t))

对我来说，这些优化结合起来使速度提高了大约 250 倍.

For me these optimizations combined give speedup of about 250 times.

这篇关于做 BFS 时避免深度复制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！