Странные помехи между модулем Heapq и словарем - PullRequest
Новая
       57

Странные помехи между модулем Heapq и словарем

0 голосов
/ 26 марта 2019

С одной стороны, у меня есть grid defaultdict, который хранит соседние узлы каждого узла в сетке и его вес (все 1 в примере ниже). 

        node   (w  nbr_node)
grid = { 0:   [(1, -5), (1, -4), (1, -3), (1, -1), (1, 1), (1, 3), (1, 4), (1, 5)], 
         1:   [(1, -4), (1, -3), (1, -2), (1, 0), (1, 2), (1, 4), (1, 5), (1, 6)], 
         2:   [(1, -3), (1, -2), (1, -1), (1, 1), (1, 3), (1, 5), (1, 6), (1, 7)], 
         3:   [(1, -2), (1, -1), (1, 0), (1, 2), (1, 4), (1, 6), (1, 7), (1, 8)],
        ...
        }

С другой стороны, у меня есть функция Djisktra, которая вычисляет кратчайший путь между 2 узлами в этой сетке. Алгоритм использует модуль heapq и отлично работает. 

import heapq

def Dijkstra(s, e, grid): #startpoint, endpoint, grid
    visited = set()
    distances = {s: 0} 
    p = {} 
    queue = [(0, s)] 

    while queue != []:

        weight, node = heappop(queue) 
        if node in visited: 
            continue

        visited.add(node) 

        for n_weight, n_node in grid[node]: 
            if n_node in visited: 
                continue

            total = weight + n_weight 

            if n_node not in distances or distances[n_node] > total: 

                distances[n_node] = total
                heappush(queue, (total, n_node))
                p[n_node] = node

Проблема : при многократном вызове функции Джикстра heappush означает ... добавление новых ключей в словарь grid без причины!

Вот MCVE: 

from collections import defaultdict

# Creating the dictionnary
grid = defaultdict(list) 
N = 4
kernel = (-N-1, -N, -N+1, -1, 1, N-1, N, N+1)

for i in range(N*N): 
    for n in kernel:
        if i > N and i < (N*N) - 1 - N and (i%N) > 0 and (i%N) < N - 1:
            grid[i].append((1, i+n))



# Calling Djikstra multiple times
keys = [*range(N*N)]

while keys:

    k1, k2 = random.sample(keys, 2)

    Dijkstra(k1, k2, grid) 

    keys.remove(k1)
    keys.remove(k2)

Оригинал grid defaultdict: 

dict_keys([5, 6, 9, 10])

... и после многократного вызова функции Djikstra: 

dict_keys([5, 6, 9, 10, 4, 0, 1, 2, 8, 3, 7, 11, 12, 13, 14, 15])

При многократном вызове функции Djikstra без heappush (просто комментируя heappush в конце): 

dict_keys([5, 6, 9, 10])

Вопрос

  • Как мне избежать этого странного поведения?

Обратите внимание, что я использую Python 2.7 и не могу использовать numpy.

1 Ответ

1 голос
/ 26 марта 2019

Я мог бы воспроизвести и исправить. Проблема в том, как вы строите grid: он содержит значения, которые не находятся в ключах от -4 до 0 и от 16 до 20 в примере. Таким образом, вы нажимаете эти несуществующие узлы на голове, а потом высовываете их.

И вы заканчиваете выполнением for n_weight, n_node in grid[node]:, где node не существует (все еще) в grid. Поскольку grid является значением по умолчанию, новый узел автоматически вставляется с пустым списком в качестве значения.

Исправление тривиально (по крайней мере, для данных примера): достаточно убедиться, что все узлы, добавленные в качестве значения сетки, существуют как ключ с модулем: 

for i in range(N*N): 
    for n in kernel:
        grid[i].append((1, (i+n + N + 1)%(N*N)))

Но даже для реальных данных не должно быть очень сложно убедиться, что все узлы, существующие в значениях сетки, также существуют в ключах ...

Кстати, если бы grid был простым dict, ошибка была бы немедленной с KeyError на grid[node].

...