Python, heapq, как эффективно изменить минимальный элемент в heapq? - PullRequest
Новая
       25

Python, heapq, как эффективно изменить минимальный элемент в heapq?

0 голосов
/ 08 декабря 2018

Я использую heapq в Python 3.7
У меня есть два вопроса о heapq:

  1. Я не знаю, как эффективно сохранить инвариант кучи, если я просто хочу изменитьэлемент min.
    А вот и моя реализация.(Это довольно медленно) 

    q= [5,8,9,10]
heapq.heapify(q)
q[0] = 1200
heapq.heapify(q)

  2. для чего используются эти два метода _siftdown () и _siftup ()?И в чем разница между ними?Как использовать эти два метода для поддержки инварианта кучи?

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

s = time.time()
q = []
for i in range(0, 10000):
    heapq.heappush(q, i)
for i in range(0, 10000):
    q[0] = 10000+i
    heapq._siftup(q,0)
print(q[0])
e2 =time.time()

print(e2-s)

s = time.time()
q = []
for i in range(0, 10000):
    heapq.heappush(q, i)
for i in range(0, 10000):
    q[0] = 10000+i
    heapq.heapify(q)
print(q[0])
e2 =time.time()

print(e2-s)

Вывод: 

10000
0.09700560569763184
10000
7.193411350250244

1 Ответ

0 голосов
/ 08 декабря 2018

Используйте heapq.heapreplace.Самый маленький элемент всегда находится на q[0], поэтому измените его, если необходимо, и затем вызовите: 

heapq.heapreplace(q, q[0])

Я проверил ваше время и переписал его на скорость: 

import time
import heapq

s = time.time()
q = list(range(0, 10000))
heapq.heapify(q)

for i in range(0, 10000):
    heapq.heapreplace(q, 10000+i)

print(q[0])
e2 = time.time()

print(e2 - s)


s = time.time()
q = list(range(0, 10000))
heapq.heapify(q)

for i in range(0, 10000):
    q[0] = 10000+i
    heapq._siftup(q, 0)

print(q[0])
e2 = time.time()

print(e2 - s)

Производит: 

10000
0.006845951080322266
10000
0.06091189384460449

Быстрее создать список и затем вызвать heapify, затем использовать heappush.

heapq.heapreplace быстрее, чем heapq._siftup, так как heapreplace используетМодуль C для heapq, где _siftup в Python._siftup и _siftdown появляются только в heapq.py, а не в _heapq модуле

Не звоните ни _siftup, ни _siftdown.Они являются внутренними для реализации Python heapq.

Я тестировал это с Python 3.2.3

...