Реализация более быстрого Fifo в SML - PullRequest
Новая
       11

Реализация более быстрого Fifo в SML

0 голосов
/ 25 апреля 2019

Может ли быть реализация Fifo, поддерживающая подмножество его функций, а именно просто Enqueue, Dequeue, isEmpty, и инициализация empty с общими 'a объектами с использованием некоторого вида изменяемого указатели, так что не будет понесено затрат на копирование одного списка в определенные моменты времени, которые использует текущая реализация из двух списков (ни одна, когда сложность принимается амортизированной, так как это все еще амортизированная стоимость операций O (1), но все еще неадекватная для одного из моих приложений) и если да, то как именно?

1 Ответ

0 голосов
/ 25 апреля 2019

Вы можете использовать Array для решения с динамическим массивом , что также приведет к амортизированной стоимости, или вы можете внедрить двусвязные списки используя типы ref и option.Я связался с решениями C, поскольку такие решения аналогичны, хотя синтаксически более сложны в SML, и потому что я не смог найти никаких примеров в SML.Решение с двусвязным списком повлечет за собой затраты памяти, поскольку каждый узел упакован, но не будет амортизированной стоимости решения с динамическим массивом или полностью функциональной deque, которую вы описываете.

Функциональный двустороннийочереди были предметом многих исследований;в этой статье Википедии есть ссылки на несколько структур данных и подходы, основанные как на лени, так и нет.Я не знаю, кто из них O (1) ;кажется, что все они либо O (1) амортизируются, либо O (lg n) , но все еще эффективны.

Вот как нефункционально вдвойнеТип данных связанного списка может выглядеть следующим образом: 

datatype 'a node = Node of { elem : 'a
                           , prev : 'a node option ref
                           , next : 'a node option ref
                           }

datatype 'a deque = Empty | NonEmpty of 'a node

У такой реализации есть некоторые недостатки:

  • Отслеживание ссылок не является синтаксически хорошим.В C вы можете написать 

    if (nd->prev) nd->prev->next = nd;

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

  • Вы заново изобретаете нулевые указатели.Сама реализация хрупка, так как у вас могут быть случаи, когда предыдущий / следующий узел является ссылкой на NONE, когда это не должно быть.Операции не будут выходить за пределы push, pop, shift и unshift, поэтому, когда вы их выполнили, вы можете положиться на тестирование (на основе единиц или свойств).Вы должны обязательно проверить это, я бы сказал, не покупая сильные стороны, обычно используемые ML.

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

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

...