Fastest method for comparing ranges of multidimensional lists

Question

Context: I am trying to write an A* search in an unknown environment. To do this, I am maintaining a representation of the environment in a 2-D or 3-D list (depending on the environment), and another n-D list that represents the agent's knowledge of the environment.

When the agent moves, I check the area around them with the actual environment. If there is a discrepancy, their map gets updated, and I run A* again.

Problem: What is the fastest method to check if there is a difference between the ranges of these two lists?

Naive Solution:

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*

This works, but it feels inefficient. I'm thinking I could replace the loop with something like set(known_environment).intersection(actual_environment) to check if there is a discrepancy, and then update if needed; but this can probably be improved upon as well.

Thoughts?

Edit: I've switched over to numpy slicing, and use array_equal instead of sets.

# 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

It should already be a tad faster, when you employ the solution concept from the link given in my comment to the question.

I modified / hacked up a bit the given code and tried:

#! /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*

(Edited): Added some kind of reuse of indexing above in eager update loop.

2nd Edit to accommodate for comment w.r.t. updated question (cf. comment below):

Looking at the amended question i.e. the snippet now relating to a numpy based implementation, I'd suggest two changes that would make the code clearer to me at least:

1. To avoid the literal + 1 clutter address the issue of slices excluding the stop by introducing supreme values for right and bottom
2. Define the section boundary box with minand max to make the relation clear.

Like so:

# ... 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 ... 

... or getting rid of colon-itis (sorry):

# ... 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 ... 

Should be concise read, easy on the run time and nice playground.

... but image processing (e.g. with fixed masks) and staggered grid processing algorithms should be abound to offer ready made solutions