улучшение эффективности heapq

Question

Поэтому для некоторых расчетов я пользуюсь heapq. Однако для проблемы, над которой я работаю, она работает медленно, потому что куча становится довольно большой.

Я думал, что у меня есть возможность ускорить его. Вместо того, чтобы создавать гигантскую кучу, сделайте ее кучей куч. Но, что удивительно, «более эффективный» код значительно медленнее. В этом более эффективном коде есть немного больше накладных расходов, но я действительно думал, что выиграет много. Устранив проблему, у меня есть две функции, которые выполняют один и тот же расчет. f1 - это «наивная» (и более быстрая) версия. f2 - это «улучшенная» (но более медленная) версия. Я делаю некоторое генерирование случайных чисел в обоих, но я использую одно и то же семя, поэтому на самом деле это одно и то же.

import random 
import heapq 
def f1(): 
    random.seed(1) 
    Q=[0] 
    while Q: 
     value = heapq.heappop(Q) 
     #print value 
     if value<0.5: 
      for counter in range(16): 
       heapq.heappush(Q,value + 0.1 + (random.random()/1000)) 
    print value 

def f2(): 
    random.seed(1) 
    Q=[[0]] 
    while Q: 
     subQ = heapq.heappop(Q) 
     value = heapq.heappop(subQ) 
     #print value 
     if subQ: 
      heapq.heappush(Q,subQ) 
     newQ = [] 
     if value<0.5: 
      for counter in range(16): 
       newQ.append(value + 0.1 + (random.random()/1000)) 
      heapq.heapify(newQ) 
      heapq.heappush(Q,newQ) 
    print value 

Почему куча куч (f2) работают значительно медленнее? Он должен вызывать heappush столько же раз, сколько и два раза. Но размер куч должен быть значительно меньше, поэтому я ожидал, что он будет работать быстрее.

Answer 1

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

def f1(m,n): 
    random.seed(1) 
    Q=[0] 
    for counter in range(m): 
     value = heapq.heappop(Q) 
     #print value 
     for newcounter in range(n): 
      heapq.heappush(Q,random.random()) 
    print value #should be the same for both methods, so this is just a test 

def f2(m,n): 
    random.seed(1) 
    Q=[[0]] 
    for counter in range(1000000): 
     subQ = heapq.heappop(Q) 
     value = heapq.heappop(subQ) 
     #print value 
     if subQ: 
      heapq.heappush(Q,subQ) 
     newQ = [] 
     for newcounter in range(n): 
      newQ.append(random.random()) 
     heapq.heapify(newQ) 
     heapq.heappush(Q,newQ) 
    print value #should be the same for both methods, so this is just a test 

Когда я профиль f1(1000000,10) и f2(1000000,10) я получаю время наработки на 10,7 секунды и 14,8 секунды. Соответствующие детали:

f1:

ncalls tottime percall cumtime percall Имя файла: LINENO (функция)

+1000000 1,793 0,000 1,793 0,000 {_heapq.heappop}

10000000 3,856 0,000 3,856 0,000 {_heapq.heappush}

f2:

1000000 1,095 0,000 1,095 0,000 {_heapq.heapify}

2000000 2,628 0,000 2,628 0,000 {_heapq.heappop}

1999999 2,245 0,000 2,245 0,000 {_heapq.heappush}

10000000 1,114 0,000 1,114 0,000 {метод «добавить» из «списка» объектов}

так чистая f2 проигрывает из-за дополнительного heappop, а также heapify и append. Это лучше на heappush.

Но когда я иду, и оспорить его с большим внутренним контуром и запустить f1(1000,100000) и f2(1000,100000) мы получаем

f1:

1000 0,015 0,000 0,015 0,000 {_heapq.heappop}

100000000 28,730 0,000 28,730 0,000 {_heapq.heappush}

f2:

1000 19,952 0,020 19,952 0,020 {_heapq.heapify}

2000 0,011 0,000 0,011 0,000 {_heapq.heappop}

1999 0,006 0,000 0,006 0,000 { _heapq.heappush}

100000000 6.977 0.000 6.977 0.000 {метод 'добавить' из объектов списка}

Итак, теперь мы делаем намного лучше на heappush, и теперь достаточно, чтобы f2 работал быстрее (69 секунд против 75 секунд).

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