Коллекции Haskell с гарантированными границами наихудшего случая для каждой отдельной операции?

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

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

Интересно, есть ли такая реализация стандартных коллекций (Map, Set и т.д.) в Haskell?

Пакет контейнеры говорит

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

поэтому нет гарантии наихудших оценок для одной операции. Существуют строгие варианты, такие как Data.Map.Strict, но они строги в своих ключах и значениях:

Аргументы ключа и значения оцениваются как WHNF; Ключи и значения оцениваются как WHNF до того, как они будут сохранены на карте.

нет ничего о (возможной) строгости его структуры.


collections haskell amortized-analysis
person Petr    schedule 12.09.2012    source источник
comment
Асимптотические границы наихудшего случая для вашей структуры данных могут трансформироваться или не трансформироваться в поведение в реальном времени. Вы работаете на языке со сборщиком мусора, поэтому ваша модель затрат в любом случае работает только в амортизированном случае. Произвольные паузы GC по-прежнему будут возможны.   -  person Philip JF    schedule 12.09.2012

Ответы (1)


arrow_upward
11
arrow_downward

нет ничего о (возможной) строгости его структуры.

Ищите источник, например. для Data.Map.Map< /а>

-- See Note: Order of constructors
data Map k a  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
              | Tip

Вы видите, что Map является полностью строгим по стержню (и строгим по ключам, даже с Data.Map.Lazy), если вы оцениваете его как WHNF, полный стержень принудительно. То же самое верно для IntMaps, Sets и IntSets.

Таким образом, вы можете легко предотвратить создание больших санков (за исключением сопоставленных/содержащихся значений), заставив контейнер использовать WHNF перед каждой операцией. Предотвращение больших переходов для содержащихся значений [частая причина утечек времени (и пространства)] выполняется автоматически для вариантов Data.XYZ.Strict (предостережение: значения оцениваются только до WHNF, если вам нужно больше, вы должны сделать это самостоятельно, например, deepseqобновление любых измененных значений сразу после операции), то, что вам нужно сделать самостоятельно с Data.XYZ.Lazy вариантами.

Таким образом

Пользователей не волнует, занимает ли нажатие кнопки 0,1 с или 0,2 с, но их волнует, вызывает ли 100-й щелчок невыполнимые ленивые вычисления и для продолжения требуется 10 с.

легко избежать проблемы с этими контейнерами.

Однако может случиться так, что 100-й щелчок обрабатывается гораздо дольше, чем в среднем, не из-за выдающихся ленивых вычислений, а из-за алгоритма (рассмотрим классическую реализацию очереди с двумя списками, передним , где вы удаляете элементы из очереди на dequeue (Q (x:xs) ys) = (x, Q xs ys) за O(1), а заднее — на enqueue y (Q xs ys) = Q xs (y:ys) за O(1), ну, за исключением того, что удаление из очереди занимает O(size), когда передний список пуст, а задний нужно сначала перевернуть, но он по-прежнему амортизируется на O(1) без изменения амортизированной стоимости.

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

person Daniel Fischer    schedule 12.09.2012
comment
Очереди объявлений: это именно то, что решает Окасаки. Он планирует обращение в нужное время, а затем вызывает постоянную часть обращения при каждом обновлении, чтобы, когда требуется обращение, оно полностью оценивалось. - person Petr; 12.09.2012