как избежать использования _siftup или _siftdown в heapq

Question

Я понятия не имею, как эффективно решить следующую проблему без использования _siftup или _siftdown:

Как восстановить инвариант кучи, когда один элемент вышел из строя?

Другими словами, обновите old_value в heap до new_value и оставьте heap работоспособным. Вы можете предположить, что в куче есть только один old_value. Определение функции выглядит так:

def update_value_in_heap(heap, old_value, new_value):

Вот мой реальный сценарий, прочитайте его, если вам интересно.

• Вы можете себе представить, что это небольшая система автозаполнения. Мне нужно посчитать частота слов, и поддерживать верхние k слов с максимальным количеством слов, которые подготовиться к выходу в любой момент. Поэтому я использую heap здесь. Когда одно слово Считайте ++, мне нужно обновить его, если он в куче.

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

• когда пользователь вводит слово, оно сначала читает из кучи, а затем обновляет
  Это. Для повышения производительности можно рассмотреть уменьшение частоты обновления по обновлению в пакете.

Так как же обновлять кучу, когда увеличивается количество слов?

Вот простой пример _siftup или _siftdown версии (не мой сценарий):

>>> from heapq import _siftup, _siftdown, heapify, heappop

>>> data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
>>> heapify(data)
>>> old, new = 8, 22              # increase the 8 to 22
>>> i = data.index(old)
>>> data[i] = new
>>> _siftup(data, i)
>>> [heappop(data) for i in range(len(data))]
[1, 2, 3, 5, 7, 10, 18, 19, 22, 37]

>>> data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
>>> heapify(data)
>>> old, new = 8, 4              # decrease the 8 to 4
>>> i = data.index(old)
>>> data[i] = new
>>> _siftdown(data, 0, i)
>>> [heappop(data) for i in range(len(data))]
[1, 2, 3, 4, 5, 7, 10, 18, 19, 37]

стоит O (n) для индексации и O (logn) для обновления. heapify - другое решение, но менее эффективно, чем _siftup или _siftdown.

Но _siftup и _siftdown являются защищенными членами в heapq, поэтому им не рекомендуется доступ извне.

Так есть ли лучший и более эффективный способ решения этой проблемы? Лучшая практика для этой ситуации?

Спасибо за чтение, я действительно ценю это, чтобы выручить меня. :)

уже ссылается на heapq python - как изменить значения, для которых сортируется куча , но нет ответа на мою проблему

Answer 1

Одна важная вещь, которую вы должны иметь в виду, состоит в том, что теоретическая сложность и производительность - это две разные вещи (даже если они связаны).Другими словами, реализация тоже имеет значение.Асимптотические сложности дают вам некоторые нижние границы , которые вы можете видеть как гарантии, например, алгоритм в O (n) гарантирует, что в худшем случае вы будете выполнять ряд инструкций, линейных во входных данныхразмер.Здесь есть две важные вещи: 1) константы игнорируются (константы имеют значение в реальной жизни), 2) сценарий наихудшего случая зависит от алгоритма, который вы рассматриваете, не только от входных данных.Обратите внимание, что в зависимости от того, где вы найдете сложность, наблюдение 1) может быть очень важным.В некоторых доменах константы, скрытые в асимптотических сложностях, настолько велики, что вы не можете построить случай, когда входной размер больше, чем «константы».Это не тот случай, но вы всегда должны помнить об этом.

При этих двух наблюдениях нельзя сказать, что «реализация A быстрее, чем B, потому что A получается из алгоритма O (n), а B - из алгоритма O (log n)».Даже если это вообще хороший аргумент для начала, этого не всегда достаточно.

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

При этом давайте выполним некоторые тесты производительности для следующего класса, которыйбудет реализовывать три разные стратегии (здесь на самом деле четыре стратегии, но Invalidate and Reinsert не кажется правильным в вашем случае, так как вы аннулируете каждый элемент столько раз, сколько видитеданное слово).Я включу большую часть своего кода, чтобы вы могли дважды проверить, что я не испортил (вы можете даже проверить полный блокнот ):

from heapq import _siftup, _siftdown, heapify, heappop

class Heap(list):
  def __init__(self, values, sort=False, heap=False):
    super().__init__(values)
    heapify(self)
    self._broken = False
    self.sort = sort
    self.heap = heap or not sort

  # Solution 1) repair using the knowledge we have after every update:        
  def update(self, key, value):
    old, self[key] = self[key], value
    if value > old:
        _siftup(self, key)
    else:
        _siftdown(self, 0, key)

  # Solution 2 and 3) repair using sort/heapify in a lazzy way:
  def __setitem__(self, key, value):
    super().__setitem__(key, value)
    self._broken = True

  def __getitem__(self, key):
    if self._broken:
        self._repair()
        self._broken = False
    return super().__getitem__(key)

  def _repair(self):  
    if self.sort:
        self.sort()
    elif self.heap:
        heapify(self)

  # … you'll also need to delegate all other heap functions, for example:
  def pop(self):
    self._repair()
    return heappop(self)

Сначала мы можем проверить, чтовсе три метода работают:

data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]

heap = Heap(data[:])
heap.update(8, 22)
heap.update(7, 4)
print(heap.nlargest(len(data)))

heap = Heap(data[:], sort_fix=True)
heap[8] = 22
heap[7] = 4
print(heap.nlargest(len(data)))

heap = Heap(data[:], heap_fix=True)
heap[8] = 22
heap[7] = 4
print(heap.nlargest(len(data)))

Затем мы можем запустить некоторые тесты производительности, используя следующие функции:

import time
import random

def rand_update(heap, lazzy_fix=False, **kwargs):
    index = random.randint(0, len(heap)-1)
    new_value = random.randint(max_int+1, max_int*2)
    if lazzy_fix:
        heap[index] = new_value
    else:
        heap.update(index, new_value)

def rand_updates(n, heap, lazzy_fix=False, **kwargs):
    for _ in range(n):
        rand_update(heap, lazzy_fix)

def run_perf_test(n, data, **kwargs):
    test_heap = Heap(data[:], **kwargs)
    t0 = time.time()
    rand_updates(n, test_heap, **kwargs)
    test_heap[0]
    return (time.time() - t0)*1e3

results = []
max_int = 500
nb_updates = 1

for i in range(3, 7):
    test_size = 10**i
    test_data = [random.randint(0, max_int) for _ in range(test_size)]

    perf = run_perf_test(nb_updates, test_data)
    results.append((test_size, "update", perf))

    perf = run_perf_test(nb_updates, test_data, lazzy_fix=True, heap_fix=True)
    results.append((test_size, "heapify", perf))

    perf = run_perf_test(nb_updates, test_data, lazzy_fix=True, sort_fix=True)
    results.append((test_size, "sort", perf))

Результаты следующие:

import pandas as pd
import seaborn as sns

dtf = pd.DataFrame(results, columns=["heap size", "method", "duration (ms)"])
print(dtf)

sns.lineplot(
    data=dtf, 
    x="heap size", 
    y="duration (ms)", 
    hue="method",
)

Из этих тестов мы видим, что heapify кажется наиболее разумным выбором, он имеет приличную сложность в худшем случае: O (n) и работает лучше на практике.С другой стороны, это, вероятно, хорошая идея - исследовать другие варианты (например, иметь структуру данных, выделенную для этой конкретной проблемы, например, использовать корзины для переноса слов, а затем перемещать их из корзины на следующую, выглядеть как возможный трек дляисследования).

Важное замечание: этот сценарий (соотношение обновления и чтения 1: 1) неблагоприятен как для решений heapify, так и sort.Поэтому, если вам удастся получить соотношение ak: 1, этот вывод будет еще более ясным (вы можете заменить nb_updates = 1 на nb_updates = k в приведенном выше коде).

Данные кадра:

    heap size   method  duration in ms
0        1000   update        0.435114
1        1000  heapify        0.073195
2        1000     sort        0.101089
3       10000   update        1.668930
4       10000  heapify        0.480175
5       10000     sort        1.151085
6      100000   update       13.194084
7      100000  heapify        4.875898
8      100000     sort       11.922121
9     1000000   update      153.587103
10    1000000  heapify       51.237106
11    1000000     sort      145.306110