Обновление PriorityQueue - PullRequest
Новая
       10

Обновление PriorityQueue

3 голосов
/ 08 апреля 2020

Я очень озадачен различным поведением PriorityQueue, когда элемент является целым числом по сравнению со строкой. Но прежде чем обратиться к этому, я хотел бы понять следующее поведение (используя элементы в качестве целых чисел).

Предположим, у меня есть очередь приоритетов со следующими данными (для каждого элемента первое значение является приоритетом, а второе значение - это элемент):

Изображение 1:

enter image description here

После выполнения следующих команд: 

pq.put(pq.get())

Элементы сортируются следующим образом:

Изображение 2:

enter image description here

Почему некоторые элементы поменялись местами? Что происходит с сортировкой?

Вот код для воспроизведения этих скриншотов из отладчика: 

from sys import maxsize
from queue import PriorityQueue

items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 15, 16]
INFINITY = maxsize
minDist = {k: INFINITY for k in items}
minDist[3] = 0

pq = PriorityQueue(len(minDist))

for v in minDist.keys():
    pq.put([minDist[v], v])

# At this point, pq has the elements as shown in Image 1

pq.put(pq.get())

# Now, pq has elements scrambled as shown in Image 2

ИЗУЧЕННЫЕ УРОКИ

На основе исследования и обсуждения ниже, каждый вызов pq.put(pq.get()) будет перестраивать структуру данных очереди приоритетов. Не ясно, есть ли способ контролировать это. Пожалуйста, прокомментируйте ниже, если вы знаете, как!

Моя специфика c проблема, кажется, связана с сортировкой предметов. Как показано на рисунках 1 и 2, элементы являются целыми числами от 1 до 17. Если они преобразованы в строки (т. Е. "1", "2", ..., "17"), я получаю другое поведение из основной функции в моем исходном коде. Однако, если я использую zfill(2) для каждой клавиши, так что у меня есть "01", "02", ..., "17", я могу получить те же конечные результаты, что и я, если я использую целые числа вместо этого.

1 Ответ

1 голос
/ 08 апреля 2020

Мне не ясно, что происходит на скриншотах, которые вы показываете, но ниже показан пример сеанса с интерпретатором, который пытается воссоздать проблему с немного другим подходом: 

Python 3.8.2 (tags/v3.8.2:7b3ab59, Feb 25 2020, 23:03:10) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>> import math, pprint, queue
>>> min_dist = {x: math.inf for x in range(1, 17)}
>>> min_dist[3] = 0
>>> pq = queue.PriorityQueue(len(min_dist))
>>> for key, value in min_dist.items():
    pq.put((value, key))


>>> pq_items = []
>>> while not pq.empty():
    pq_items.append(pq.get())


>>> pprint.pprint(pq_items)
[(0, 3),
 (inf, 1),
 (inf, 2),
 (inf, 4),
 (inf, 5),
 (inf, 6),
 (inf, 7),
 (inf, 8),
 (inf, 9),
 (inf, 10),
 (inf, 11),
 (inf, 12),
 (inf, 13),
 (inf, 14),
 (inf, 15),
 (inf, 16)]
>>> for key, value in min_dist.items():
    pq.put((value, key))


>>> pq.put(pq.get())
>>> pq_items.clear()
>>> while not pq.empty():
    pq_items.append(pq.get())


>>> pprint.pprint(pq_items)
[(0, 3),
 (inf, 1),
 (inf, 2),
 (inf, 4),
 (inf, 5),
 (inf, 6),
 (inf, 7),
 (inf, 8),
 (inf, 9),
 (inf, 10),
 (inf, 11),
 (inf, 12),
 (inf, 13),
 (inf, 14),
 (inf, 15),
 (inf, 16)]
>>>

Вы Возможно, вы захотите адаптировать свой код, чтобы использовать аналогичный подход, чтобы получить то, что вы ищете. Если у вас возникли проблемы со строками, вы можете проверить, как будут упорядочены ваши элементы, если они были помещены в список, а затем отсортированы.

...