Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Списки ввода и массивы ввода

В HN0 с целью обеспечения высокой производительности планируется использование специализированных реализаций АТД списка - списков ввода.

В С++ STL есть аналог списков ввода - это итераторы ввода (input_iterator). Однако в С++ работать с итераторами крайне неудобно из-за многословности синтаксиса, да и стандартная библиотека была спроектирована на мой взгляд неправильно, так что хорошая идея оказалась загублена.

В HN0 со списками ввода можно будет работать так же, как и с другими видами списков. Рассмотрим реализацию операций map и filter над списком ввода.

Операция map не будет содержать внутри прохода по всем элементам списка, а будет просто декорировать операцию head переданного ей списка ввода и возвращать полученный новый АТД. Операция filter будет декорировать операцию tail.

Аналогично спискам можно реализовать массивы ввода.

Некоторые операции (например, reverse) нельзя реализовать эффективно на списках ввода, но легко на массивах ввода. Операция filter наоборот, эффективна на списках ввода, но неэффективна на массивах ввода из-за необходимости декорировать операцию size. Операции map и fold одинаково эффективны на обоих структурах.

Заметьте, что функция map, например, может всегда возвращать список ввода, независимо от того какой список ей передан - обычный, ленивый, уникальный или ввода, без какой-либо потери производительности.
Tags: compiler design, hn0
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment