Пересекая heapified список

Question

Я делаю симуляцию Монте-Карло. И как часть этой задачи я генерирую сэмплы, равномерно распределенные по интервалу (0,100).

generate = lambda: uniform(0,100)

Итерации прекращаются, когда все пары ближайших сгенерированных точек соответствуют критериям.

check = lambda a,b: True if (b-a)<5 else False

Мне нужно иметь некоторую структуру, чтобы эффективно сохранять все сгенерированные точки и иметь возможность проходить их в порядке возрастания, чтобы выполнить check на всех последующих парах.

В Python есть модуль heapq, который поддерживает очень эффективную структуру кучи. И я решил использовать это.

Я столкнулся с проблемой. Я не нашел процедуры обхода, поддерживаемой этим модулем. Единственный способ найти значения кучи в порядке возрастания - использовать heapq.heappop. Но это удаляет значения из кучи.

Я нашел обходной путь для этого и просто скопировал объект кучи в новый и повторил с heappop поверх нового. Но я не думаю, что достаточно эффективно копировать всю структуру в памяти каждую итерацию.

Есть ли другой способ сделать то, что я пытаюсь сделать более эффективно?

---

Упрощенный код для иллюстрации.

import heapq
from random import uniform
from itertools import tee, izip, count
from copy import copy


def pairwise(iterable): #get values from iterator in pairs
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)


check = lambda a,b: True if (b-a)<5 else False
generate = lambda: uniform(0,100)


def iterate_heap(heap):
    heap = copy(heap) #Here I have to copy the heap to be able to traverse
    try:
        while True:
            yield heapq.heappop(heap)
    except IndexError:
        return


def trial():
    items = []

    for i in count():
        item = generate()
        heapq.heappush(items, item)

        it = iterate_heap(items)
        it = pairwise(it)

        if i>0 and all(check(a,b) for a,b in it): #if i==0 then 'it' returns no values and 'all' returns True
            return i

print "The solution is reached. It took %d iterations." % trial()

paiwise функция взята из рецепта здесь .

---

Обновление: В этой реализации с heappop сложность на каждой итерации составляет O(n*log(n)):

Копирование кучи: O(n)

Добавление нового значения в кучу: O(log(n))

Обход: n элементов * O(log(n)) при извлечении каждого значения из кучи -> O(n*log(n)).

Результат: O(n+log(n)+n*log(n)) = O(n*log(n)

Но я ожидаю, что обход будет O(n), поэтому итоговая сложность будет O(n).

Кстати, если мы используем только отсортированный список, нам нужно будет сортировать список при каждом добавлении, поэтому O(n*log(n)), но обход будет n*O(1) -> O(n). Таким образом, результирующая сложность по-прежнему O(n*log(n)).

Я нашел решение. Это использовать модуль bisect. Найти место для добавления было бы O(log(n)). Добавление в список O(n) (из-за реализации все значения после вставки на месте должны быть перемещены). Обход O(n). Таким образом, результирующая сложность составляет O(n).

Тем не менее, я удивляюсь, если есть способ решить эту задачу, используя кучи в Python.

Answer 1

Я бы использовал list.sort () в куче. Это оставляет условие кучи без изменений и позволяет выполнять итерацию по основному списку напрямую.

FWIW, алгоритм Timsort , используемый list.sort , использует частичное упорядочение, которое уже существует в куче.

Answer 2

Из документов Python :

Эти два позволяют просматривать кучу как обычный список Python без сюрпризов: heap [0] - это самый маленький элемент, а heap.sort () поддерживает инвариант кучи!

Есть ли причина, по которой вы не можете просто рассматривать кучу как список и перебирать ее?

Answer 3

Я сделал несколько расчетов эффективности.

Наилучшая производительность достигается при использовании модуля bisect: В моем списке 10000 вставок в середине списка 0,037 сек на моем компьютере (Python 2.7).

При использовании sortedlist из blist модуль тактируется 0,287 сек для того же количества вставок.

И использование традиционных list с sort, применяемым после каждого append тактирования 2,796 сек. (В настоящее время алгоритм Timsort используется в Python и считается очень эффективным в почти отсортированном списке; тем не менее он оказывается не таким эффективным, как при использовании bisect).

---

Код, который я использовал для этих вычислений:

import bisect
import timeit
import __main__
import blist

N = 10000 #Number of executions
L = 1000 #Length of initial list

def test_f_bisect(a):
    bisect.insort_right(a,500)


def test_f_list_sort(a):
    a.append(500)
    a.sort()


test_f_blist_init = '''
from __main__ import test_f_blist
import blist
a = blist.sortedlist(range({L}))
'''.format(L=L)
def test_f_blist(a):
    a.add(500)


names = dir(__main__)
for name in names:
    attr = getattr(__main__,name)
    if hasattr(attr,'__call__'):
        if name.startswith('test_f_'):
            init_name = name + '_init'
            if hasattr(__main__, init_name):
                init = getattr(__main__,init_name)
            else:
                init = 'from __main__ import {name}; a = list(range({L}))'.format(name=name, L=L)
            t = timeit.Timer(stmt='{name}(a)'.format(name=name),
                             setup=init)

            time = t.timeit(N)
            print('{name}: {time}'.format(name=name,time=time))

Answer 4

Для записи, правильной структурой данных в этом случае является B-дерево. Существует реализация :

 from blist import sortedlist

Сложность среды выполнения настолько мала, что получается: O (n * logn) для построения списка, O (n) для итерации.