Удаление процента приоритетной очереди в python

Question

Есть ли способ удалить определенный процент (скажем, 20) из очереди, как только она достигнет определенного размера?

Этот вопрос связан с проблемой, где используется алгоритм поиска, который сохраняет дочерние узлыкорневая родительская плата в очереди приоритетов.Проходить так много разных узлов, что на поиск решения уходит более 20 часов.Я хотел бы сделать грубые пропуски в очереди, чтобы сократить количество узлов, чтобы быстрее найти решение, с риском отбрасывания важных узлов, которые могли бы привести к этой цели.

Answer 1

Предположим, что вам все равно, какие 20% элементов должны быть удалены, поэтому я решил удалить те, которые непропорционально имеют самые низкие приоритеты в очереди.Предположим также, что приоритетная очередь в стандартной библиотеке Python heapq .Наконец, давайте предположим, что это удаление должно выполняться вызывающими подпрограммами всякий раз, когда они решат сделать это, а не автоматически самой структурой очереди приоритетов.

Очередь приоритетов в heapq являетсястандартный список Python с некоторыми добавленными функциями.Если ваша очередь с приоритетами называется mypqueue, вы можете удалить примерно 20% элементов, взвешенных по отношению к тем с более низким приоритетом, с

mypqueue = mypqueue[:len(mypqueue) * 4 // 5]

или несколько более короткой альтернативой,

mypqueue[len(mypqueue) * 4 // 5:] = []

Это просто усекает список до 4/5 его длины, удаляя конец списка.Это работает, потому что свойства кучи сохраняются в этом усечении, поэтому, если mypqueue была очередью с приоритетом на основе кучи, она все еще есть.

Это можно было бы поместить в собственную функциюкурс.Вы также можете легко создать новый класс на основе списка Python, который будет делать это автоматически, когда размер очереди достигает определенного числа.Я оставлю это тебе.