12 сент. 2012 г., 17:03 от Petr Pudlák

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

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

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

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

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

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

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

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

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

Ответы на вопрос (0)

12 сент. 2012 г., 17:53 от Daniel Fischer

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

Ищите источник, например за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,Setс иIntSets.

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

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

Пользователи нене волнует, если нажатие кнопки занимает 0,1 с или 0,2 с, но им все равно, если сотый щелчок вызовет выдающиеся ленивые вычисления и потребуется 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 (размер), когда передний список пуст, и задняя часть должна быть сначала изменена, но это 's O (1) амортизируется еще) без изменения амортизированной стоимости.

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

ВАШ ОТВЕТ НА ВОПРОС