python - 比较多维列表范围的最快方法

Question

上下文:我正在尝试在未知环境中编写 A* 搜索。为此，我维护了一个 2 维或 3 维列表(取决于环境)中的环境表示，以及另一个代表智能体对环境的了解的 n 维列表。

当代理人移动时，我会根据实际环境检查他们周围的区域。如果存在差异，他们的 map 会更新，然后我再次运行 A*。

问题:检查这两个列表的范围是否存在差异的最快方法是什么？

简单的解决方案:

from itertools import product
from random import randint

width, height = 10, 10
known_environment = [[0 for x in range(width)] for y in range(height)]
actual_environment = [[0 for x in range(width)] for y in range(height)]

# Populate with obstacles
for i in xrange(10):
    x = randint(0, len(actual_environment) - 1)
    y = randint(0, len(actual_environment[x]) - 1)
    actual_environment[x][y] += 1

# Run A* and get a path
path = [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4),
        (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)]  # dummy path

# Traverse path, checking for "new" obstacles
for step in path:
    x, y = step[0], step[1]

    # check area around agent
    for (i, j) in product([-1, 0, 1], [-1, 0, 1]):
        # don't bother checking out-of-bounds
        if not 0 <= x + i < width:
            continue
        if not 0 <= y + j < height:
            continue
        # internal map doesn't match real world, update
        if not known_environment[x + i][ y + j] == actual_environment[x + i][ y + j]:
            known_environment[x + i][ y + j] = actual_environment[x + i][ y + j]
            # Re-run A*

这可行，但感觉效率低下。我想我可以用 set(known_environment).intersection(actual_environment) 之类的东西替换循环以检查是否存在差异，然后然后根据需要进行更新；但这可能也可以改进。

想法？

编辑:我已经切换到 numpy 切片，并使用 array_equal 而不是集合。

# check area around agent
left = x - sight if x - sight >= 0 else 0
right = x + sight if x + sight < width else width - 1
top = y - sight if y - sight >= 0 else 0
bottom = y + sight if y + sight < height else height - 1

known_section = known_environment[left:right + 1, top:bottom + 1]
actual_section = actual_environment[left:right + 1, top:bottom + 1]
if not np.array_equal(known_section, actual_section):
    known_environment[left:right + 1, top:bottom + 1] = actual_section

Answer 1

当您从我对问题的评论中给出的链接中使用解决方案概念时，它应该已经快了一点。

我修改/修改了一些给定的代码并尝试:

#! /usr/bin/env python
from __future__ import print_function
from itertools import product
from random import randint

width, height = 10, 10
known_env = [[0 for x in range(width)] for y in range(height)]
actual_env = [[0 for x in range(width)] for y in range(height)]

# Populate with obstacles
for i in xrange(10):
    x = randint(0, len(actual_env) - 1)
    y = randint(0, len(actual_env[x]) - 1)
    actual_env[x][y] += 1

# Run A* and get a path
path = [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4),
        (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)]  # dummy path


def effective_slices(i_w, j_h):
    """Note: Depends on globals width and height."""
    w, h = width - 1, height - 1
    i_w_p, j_h_p = max(0, i_w - 1), max(0, j_h - 1)
    i_w_s, j_h_s = min(w, i_w + 1), min(h, j_h + 1)
    return slice(i_w_p, i_w_s), slice(j_h_p, j_h_s)


# Traverse path, checking for "new" obstacles
for step in path:
    x, y = step[0], step[1]
    # check area around agent
    dim_w, dim_h = effective_slices(x, y)
    actual_set = set(map(tuple, actual_env[dim_w][dim_h]))
    known_set = set(map(tuple, known_env[dim_w][dim_h]))
    sym_diff = actual_set.symmetric_difference(known_set)
    if sym_diff:  # internal map doesn't match real world, update
        for (i, j) in product(range(dim_w.start, dim_w.stop + 1), 
                              range(dim_h.start, dim_h.stop + 1)):
            if known_env[i][j] != actual_env[i][j]:
                known_env[i][j] = actual_env[i][j]
                # Re-run A*

(已编辑):在急切的更新循环中添加了某种索引重用。

第二次编辑以适应评论 w.r.t.更新的问题(参见下面的评论):

查看修改后的问题，即现在与 numpy 相关的片段基于实现，我建议至少让代码对我来说更清晰的两个更改:

1. 避免文字 + 1 clutter 解决了不包括 stop 的切片问题通过为 right 引入 supreme 值和 bottom
2. 用 min 定义截面边界框和 max明确关系。

像这样:

# ... 8< - - 
# check area around agent (note: uses numpy)
sight = 1
left, right_sup = max(0, x - sight), min(x + sight + 1, width)
top, bottom_sup = max(0, y - sight), min(y + sight + 1, height)

known_section = known_environment[left:right_sup, top:bottom_sup]
actual_section = actual_environment[left:right_sup, top:bottom_sup]
if not np.array_equal(known_section, actual_section):
    known_environment[left:right_sup, top:bottom_sup] = actual_section
# - - >8 ... 

... 或摆脱结肠炎(抱歉):

# ... 8< - - 
h_slice = slice(max(0, x - sight), min(x + sight + 1, width))
v_slice = slice(max(0, y - sight), min(y + sight + 1, height))

known_section = known_environment[h_slice, v_slice]
actual_section = actual_environment[h_slice, v_slice]
if not np.array_equal(known_section, actual_section):
    known_environment[h_slice, v_slice] = actual_section
# - - >8 ... 

应该是简洁的阅读、易于运行的和漂亮的 Playground 。

...但是图像处理(例如使用固定掩码)和交错网格处理算法应该比比皆是，以提供现成的解决方案