Биномиальные списки

Биномиальные списки — частный случай бинарно динамизированной структуры данных. Бинарная динамизация — простой способ «научить» почти любую структуру данных эффективному добавлению новых элементов.

Бинарная динамизация в общем виде

Предположим, у нас имеется некая структура данных foo с операциями:

## новый экземпляр структуры, хранящий указанный набор данных
def foo_new(elements): ...

## список всех данных с указанным ключом
def foo_get(foo, key): ...

## список всех хранимых элементов
def foo_elements(foo): ...

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

Например, для списков пар ключ-значение эти функции могут выглядеть так:

def list_new(elements): return elements[:]
def list_get(l,x): return [v for k,v in l if k==x]
def list_elements(l): return l[:]

А для словарей эти функции могут выглядеть так:

def dict_new(elements): 
    d = {}
    for k,v in elements:
        if k in d: d[k].append(v)
        else:      d[k] = [v]
    return d

def dict_get(d,k): return d[k] if k in d else []
def dict_elements(d): return [(k,v) for k in d for v in d[k]]

Суть динамизации заключается в том, что структура заменяется на набор уровней — аналогичных структур меньшего размера. При этом добавление элементов осуществляется на нижний уровень, а каждый уровень при превышении его вместимости переносится на следующий: ровно тем же образом происходит прибавление единицы к числу методом «в столбик».

Бинарная динамизация характеризуется тем, что каждый уровень вмещает 0 или 1 экземпляр структуры данных. Если на какой-то занятый уровень переносятся данные, они сливаются с имеющейся на этом уровне структурой, а результат слияния переносится на следующий уровень:

def dynfoo_new(): return {}

def dynfoo_append(d,k,v):
    new = foo_new( [(k,v)] )
    level = 0
    while level in d:
        old = d.pop(level)
        new = foo_new(foo_elements(old)+foo_elements(new))
        level += 1
    
    d[level] = new
    
    return d

def dynfoo_get(d,k):
    return [v for level in d for v in foo_get(d[level], k)]

Отметим две вещи:

  1. если необходимо по каждому ключу хранить только одно значение (например, последнее добавленное, как в словарях языка python), то можно перед добавлением элемента искать его и модифицировать соответствующий уровень
  2. если единственное требование — возможность по ключу получить хоть какой-то элемент, который добавлялся по этому ключу — можно особо не заморачиваться насчёт потери части данных при переносе на следующий уровнеь

В частности, вот два способа динамизировать стандартный словарь языка python:

## динамизация с уникальными ключами
def dict1_new(): return {}

def dict1_set(d,k,v):
    for level in d:
        if k in d[level]:
            d[level][k] = v
            return d

    new = {k: v}
    level = 0
    while level in d:
        old = d.pop(level)
        for k in old: new[k] = old[k]
        level += 1
    
    d[level] = new
    
    return d

def dict1_get(d,k):
    for level in d:
        if k in d[level]: return d[level][k]
    return None


## динамизация с потерей устаревших данных
def dict2_new(): return {}

def dict2_set(d,k,v):
    new = {k: v}
    level = 0
    while level in d:
        old = d.pop(level)
        for k in new: old[k] = new[k]  ## заменяем старые данные новыми
        new = old
        level += 1
    
    d[level] = new
    
    return d

def dict2_get(d,k):
    for level in sorted(d.keys()): ## более актуальные данные находятся раньше
        if k in d[level]: return d[level][k]
    return None

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

Анализ времени работы динамизированной структуры

Предположим, что структура данных, которую мы хотим динамизировать, создаётся из списка данных и разбивается на список данных за время, пропорциональное количеству этих данных. Тогда при слиянии двух таких структур одного размера среднее время слияния в пересчёте на один элемент не зависит от размера структуры.

Нетрудно заметить, что в динамизированной структуре, в которую N раз добавляли элемент, количество уровней не превосходит log(N), а размер k-го уровня не превосходит 2**k (если слияние двух структур даёт структуру суммарного размера, то размер k-го уровня всегда будет в точности 2**k).

Отсюда сразу следует, что при добавлении элемента среднее время слияния в пересчёте на один элемент увеличивается (по сравнению со слиянием двух экземпляров динамизируемой структуры одного размера) не более чем в log(N) раз. Ровно то же самое происходит и со временем (уже не средним) поиска элемента.

Биномиальный список

Биномиальный список — результат бинарной динамизации упорядоченного списка. Можно было бы и не приводить здесь соответствующий код (всё, что нужно, есть выше), но мы всё же приведём вариант для списка-множества (когда поиск происходит не по ключу, а по значению): такой вариант нами ещё не рассматривался.

def binlist_new(): return {}

def binlist_append(d,x):
    new = [x]
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

from bisect import bisect_left, bisect_right

def binlist_count(d,x):
    total = 0
    for level in d:
        l = d[level]
        total += bisect_right(l,x) - bisect_left(l,x)
    return total

Удаление элементов

См. решения упражнений.