В поисках оптимальной модели итераторов01.09.2024 00:00


В процессе разработки мини-библиотеки файлового ввода я изучал код реализации функций/методов работы с файлами в стандартных библиотеках различных языков программирования, в том числе и Rust.

Глаз зацепился за реализацию итератора чтения файла по строкам. Для реализации итератора в Rust достаточно определения всего одной функции next()!
Это маленькое открытие сподвигло меня к изучению того, как реализованы итераторы в других языках программирования.

В данной статье я поделюсь результатами этого небольшого исследования, а также представлю новую модель итераторов, которую я планирую сделать основной для языка 11l, и которую можно уже сейчас использовать в C++ проектах посредством простого адаптера (вот пример использования).
Но сначала хотелось бы устранить путаницу в терминологии, которую внёс C++. То, что в C++ принято называть итератором, в других языках называют чаще курсором. А итератор лишь обеспечивает возможность обхода итерируемого объекта. Его можно получить напрямую у контейнера [или любого другого итерируемого объекта] методом iter() в Rust, __iter__() в Python, iterator() в Java, GetEnumerator() в C# или аналогичным (в этом случае будет производиться обход по всем элементам этого контейнера). Его [итератор] возвращают методы наподобие reversed()/rev() [позволяет обойти все элементы контейнера в обратном порядке], filter() [обходит только элементы, удовлетворяющие определённому условию/предикату] и т.п.

Мне было интересно, есть ли похожая на C++ модель итераторов в родственных языках, например в D, и поиском «d lang end iterator» я вышел на тему форума языка D под названием «Iterators and Ranges: Comparing C++ to D to Rust». Тема посвящена одноимённому докладу, наиболее интересную часть которого можно выразить в табличке на одном из слайдов.

Вот в этой.
pkbs8gwwydlw0qcbfb2c4_ng9zi.png


Автор доклада выделяет 3 базовые операции, которые должны быть реализованы в итераторе:

  1. read — получение текущего элемента итерируемого объекта;
  2. advance — переход к следующему элементу итерируемого объекта;
  3. done? — проверка, остались ли ещё элементы в итерируемом объекте или нет.


В таблице на примере реализации этих трёх операций представлено сравнение моделей итераторов в языках программирования C++, D, C#, Rust, Python и Java.

Как можно заметить, C++ выделяется из всех остальных представленных в таблице языков необходимостью в дополнительной сущности last [точнее after_last, он же end()], т.к. в C++ под «итератором» понимается навороченный указатель.

Данная табличка, хоть и красивая, но, к сожалению, не достаточно исчерпывающая. К примеру, новая модель итераторов в 11l в логике данной таблицы совпадает с моделью C#. Однако, фактически эти модели итераторов отличаются. Поэтому для более наглядного сравнения моделей итераторов я приведу псевдокод их обхода во всех языках программирования, представленных в этой таблице:

C++: 

for (auto it = collection.begin(); it != collection.end(); ++it) {
    ...*it...
}


D: 

for (auto r = collection.range(); !r.empty(); r.popFront()) {
   ...r.front()...
}


Python: 

var it = collection.__iter__();
while (true) {
    try {
        let current = it.__next__();
        ...current...
    }
    catch (StopIteration) {
        break;
    }
}


Rust: 

auto it = collection.iter();
while (auto current = it.next()) {
    ...*current...
}


Java: 

Iterator it = collection.iterator();
while (it.hasNext()) {
    var current = it.next();
    ...current...
}


C#: 

var it = collection.GetEnumerator();
while (it.MoveNext()) {
    ...it.Current...
}


11l: 

if (auto it = collection.iter()) do {
    ...it->current()...
} while (it->advance());


Для сравнения удобства различных моделей итераторов на практике я реализовал итераторы для нескольких типовых задач и результаты этого сравнения свёл в следующую таблицу. (»+» означает «удобно»,»−» — неудобно и »0» — не очень удобно.)

  1. В последнем узле связного списка в поле next_node удобно хранить просто нулевой указатель, который и является признаком окончания списка. Но если метод end() будет возвращать нулевой итератор, то для сравнения он сгодится, но такой итератор нельзя назвать полноценным C++-итератором, т.к. операцию -- к нему применить так просто не получится. Впрочем, для односвязного списка это не актуально, т.к. итератор односвязного списка в любом случае не поддерживает операцию --.
  2. Из-за того, что метод next() возвращает текущий элемент после того, как переходит к следующему, текущий элемент приходится предварительно запоминать/сохранять во временной вспомогательной переменной result.
  3. Неудобство в том, что MoveNext() не только выполняет проверку существования следующего элемента итерируемого объекта, но и переходит к следующему элементу, поэтому итератор изначально должен указывать на «минус первый» элемент, либо в итератор необходимо добавить специальный флаг, чтобы при первом вызове MoveNext() перехода к следующему элементу не происходило.
  4. Приходится хранить в итераторе дополнительный флаг has_next и при конструировании итератора осуществлять чтение строки с инициализацией этого флага.
  5. Необходимость реализации метода hasNext() значительно усложняет [по сравнению с Python и Rust] код итератора, т.к. приходится хранить следующую строку, которую необходимо запоминать/сохранять во временной вспомогательной переменной для возврата методом next().
  6. Требуется дополнительная логика [не сложная, но и не тривиальная] в методе получения итератора.


Новая модель итераторов


Как видно из вышеприведённой таблицы, новая модель итераторов [используемая в 11l] показывает себя в целом немного лучше моделей других языков, находясь примерно на одном уровне по удобству с моделью итераторов языка D (которые называют диапазонами). И хотя диапазоны в D требуют реализации трёх методов (empty, front, popFront), а итераторы 11l — всего двух (current и advance), это различие нивелируется тем, что логика метода empty () переходит в метод получения итератора, который, в отличие от D и всех остальных языков, возвращает не Iterator, a Iterator? (Nullable[Iterator] или std::optional в C++).

Расскажу вкратце, как я пришёл к новой модели итераторов. Большей частью, это было интуитивное решение, которое родилось в процессе реализации наиболее сложного типа итераторов из представленных — итератора по директории с фильтром для различных операционных систем. Мне нравилась модель Rust, и для простых случаев она работает хорошо, но реализовать итератор обхода директории в этой модели оказалось очень не удобно (можете сами посмотреть на код реализации метода next). Модель D более практична и достаточно удобна во всех случаях, но показалась мне избыточной — метод empty () в итераторе смотрится неуместно.
В попытке «избавиться от него» мне сначала пришла такая безумная идея — чтобы при попытке итерирования контейнера сначала вызывался метод empty() (не у итератора/диапазона, а у самого контейнера!) и итерация начиналась только в случае, когда он вернул false.

if (!collection.empty()) {
    auto it = collection.iter();
    do {
        ...it.current()...
    } while (it.advance());
}

Но в таком случае возникает проблема с итерируемыми объектами, у которых нет метода empty (). Например, с тем же итератором обхода директории или с итератором чтения файла по строкам. В итоге, я не придумал ничего лучше, чем вынести логику метода empty () в метод получения итератора [iter ()]. Считаю, это более правильно, чем в диапазонах D, т.к. метод empty () должен вызываться всего один раз перед началом итерирования и в итераторе ему делать нечего.

В качестве названия метода для получения текущего элемента итерируемого объекта я рассматривал варианты item() и current_element(), но остановился на current(), т.к. именно такое имя используется в языках C# [только с большой буквы — Current] и PHP. Для перехода к следующему элементу можно было бы использовать имя из C# — moveNext(), но это какое-то странное редкое словосочетание и работает MoveNext() из C# немного не так, как аналогичный метод в новой модели. Поэтому я решил взять название из доклада «Iterators and Ranges: Comparing C++ to D to Rust» для операции, соответствующей этому методу — «advance». Хотя метод advance() в новой модели выполняет также и операцию «done?», я решил не отражать это в его названии.

yield


Но безусловным лидером по удобству несомненно является yield. Просто посмотрите на код функции iterate() для любого итератора из моей реализации. Обход директории реализуется всего 8-ю строками понятного и легко читаемого кода, в то время как большинство реализаций итераторов требуют более 40-ка строк кода, и все эти реализации достаточно трудны для понимания.

Почему тогда я не стал поступать так же, как автор языка Nim, в котором никаких моделей итераторов нет, а есть только yield?
Потому, что эффективно реализовать yield в компилируемом языке программирования не так просто. Иначе бы yield давно уже был в C++. Особенно непросто учесть случаи вызова yield в рекурсивных функциях (а это может использоваться например при рекурсивном обходе директорий). В том же Nim пришлось разделять итераторы функции с yield на 2 вида: первый приводит к раздуванию кода и не поддерживает рекурсию, а второй — менее производителен.

Размышления на тему [не]оптимальности модели итераторов в Python


Почему в Python не сделано как в Rust? Т.е. почему бы вместо порождения исключения StopIteration не возвращать None?
Потому, что в контейнере вполне может оказаться элемент со значением None.
И дело в том, что [хорошо это или плохо, но] в Python нет такой вещи как Some(None), а есть только просто None. Т.е. если в Rust функция next() может вернуть None (что будет означать окончание итерирования), а может вернуть Some(None) (что будет означать следующий элемент, имеющий значение None), то в Python так сделать не получится (но и следующий элемент в Python можно возвращать просто как el, а не Some(Some(el)) как приходится делать в Rust [для контейнеров, элементы в которых имеют тип Option, т.е. могут быть None]).

На первый взгляд решение Python кажется неудачным: возбуждать исключение — ведь это очень дорого, и это приходится делать в каждом цикле в программе [кроме тех, где срабатывает ранний выход из цикла по break/return].

Но, во-первых, конкретно в Python это не очень дорого. И, во-вторых, это всего лишь стереотип [то, что возбуждение исключения — это всегда очень дорого], который 11l пытается разрушить посредством разделения исключений на два рода (подробнее про два рода исключений можно почитать в документации к 11l). При этом StopIteration разумно сделать исключением первого рода. В этом случае «порождение» этого исключения будет фактически означать возврат функцией next() специального значения, являющегося признаком окончания итерации. Производительность при этом будет на уровне функции next() в языке Rust, возвращающей Option.

P.S. Недавно я опубликовал итоги голосования/опроса [про получение системного времени с помощью std: chrono] в комментарии к моей предыдущей статье.

© Habrahabr.ru