Бесконечные интервалы
Необходимость бесконечных интервалов обосновать чуть сложнее. Программисты на С++ редко сталкиваются с бесконечностями. В других языках это случается сплошь и рядом. В Haskell можно создать бесконечный список целых чисел, просто набрав [1..]. Это просто «ленивый список», элементы в котором создаются по требованию. Все бесконечные интервалы ленивые.
Для чего это может понадобиться? Допустим, в алгоритме, строящем новый список из N первых элементов другого. Или вы захотите «склеить» бесконечный список с конечным. Тогда вы получите конечный список пар элементов. Это совершенно нормальная практика.
Было бы круто иметь поддержку бесконечных списков в библиотеке общего назначения.
Бесконечные интервалы/в STL
Можно представить себе бесконечные интервалы как интервалы с ограничителями, где условие ограничения всегда возвращает ложь. Памятуя об этом, реализуем бесконечный список целых чисел, начинающийся с заданного числа, и заканчивающийся «никогда».
struct iota_range
{
private:
int i_;
public:
using const_iterator = struct iterator
: boost::iterator_facade<
iterator, int const,
std::forward_iterator_tag
>
{
private:
bool sentinel_;
int i_;
friend class boost::iterator_core_access;
friend struct iota_range;
iterator(int i) : sentinel_(false), i_(i) {}
bool equal(iterator that) const
{
return sentinel_ == that.sentinel_
&& i_ == that.i_;
}
void increment()
{
++i_;
}
int const & dereference() const
{
return i_;
}
public:
iterator() : sentinel_(true), i_(0) {}
};
constexpr explicit iota_range(int i = 0)
: i_(i)
{}
iterator begin() const
{
return iterator{i_};
}
iterator end() const
{
return iterator{};
}
constexpr explicit operator bool() const
{
return true;
}
};
С таким списком можно сделать следующее:
// Spew all the ints. WARNING: THIS NEVER ENDS!
for( int i : iota_range() )
std::cout << i << 'n';
iota_range – прямой интервал; то есть, его итераторы построены по модели ForwardIterator. В них хранится целое число и булевское значение, которое говорит о том, является ли итератор сигнальным. Итератор begin не сигнальный, а end – сигнальный. Поэтому они никогда не будут равны, и мы будем считать целые числа целую вечность.
Что случилось по пути в бесконечность
Правда, при работе с таким интервалом вы выясните, что что-то работает, как ожидалось, а что-то улетает в гиперпространство и не возвращается. Простой пример: std::distance. Вам должно хватить ума, чтобы не делать следующее:
iota_range iota;
// Oops!
auto dist = std::distance(iota.begin(), iota.end());
Менее очевидно, что вам нельзя, вообще, никогда, ни за что, передавать такой интервал в любой алгоритм бинарного поиска – binary_search, lower_bound, upper_bound и equal_range. Несмотря на то, что iota_range – это отсортированный прямой интервал. Бинарные алгоритмы делят интервалы, а деление бесконечного интервала на выходе должно дать бесконечный интервал. Ждать этого придётся долго.
Быстродействие
Читателей прошлого поста, возможно, покоробила реализация iota_range::iterator::equal. Поскольку iota_range никогда не должен остановиться в своих итерациях, условие прекращения должно быть константой. Вместо этого мы делаем следующее:
bool equal(iterator that) const
{
return sentinel_ == that.sentinel_
&& i_ == that.i_;
}
Две проверки там, где их должно быть ноль! В прошлый раз я показал, что это приводит к нежелательным эффектам в сгенерированном коде.
Возможные бесконечные интервалы
Кроме проблемы с бесконечными циклами есть ещё одна, которая, к сожалению, существует в STL. Возьмём моего любимого мальчика для битья std::istream_iterator. Это итератор ввода, поэтому с ним необходимо связать difference_type. В книге «Elements of Programming» Александр Степанов (отец STL и Generic Programming) говорит про это так:
DistanceType возвращает целый тип, достаточно большой, чтобы измерить любую последовательность приложений допустимого саксессора.
Для istream_iterator difference_type будет std::ptrdiff_t. Рассмотрим такой код:
std::istream& sin = ...;
std::istream_iterator<char> it{sin}, end;
std::ptrdiff_t dis = std::distance(it, end);
Код допустимый и логичный. Он выцепляет символы из istream, подсчитывает их, и избавляется от них. Представьте, что sin получает символы из сети, и этот код работает несколько дней, получая миллиарды символов. Что случится, если ptrdiff_t окажется недостаточно большим для результата? Ответ: неопределённое поведение. На практике – мусор, но в принципе – всё, что угодно.
Меня это маленько сбивает с толку. У итератора difference_type должен быть достаточно большим, чтобы содержать промежуток между двумя любыми итераторами. Поскольку потоки ввода в принципе границ не имеют, то не существует знакового целого, достаточно большого для них. Приходится признать, что допустимость операции увеличения istream_iterator ограничена размером difference_type, или что difference_type задан неверно.
Предварительное заключение
Бесконечные интервалы – вещь полезная, но у них есть проблема с тем, как они сейчас определены в STL. Можно было бы запретить бесконечные интервалы, но проблема даже больше этого. И некоторые из проблем существуют и сегодня. Тяжело исправить проблему с переполнением difference_type в STL (кроме как просить людей соблюдать осторожность), но можно подумать, не поможет ли нам новый интерфейс для интервалов.
Вот пока все проблемы, которые я встретил с интервалах с парой итераторов по принципу STL:
- интервалы с ограничителями и бесконечные интервалы генерят плохой код,
- им приходится моделировать более слабые концепции, чем они могли бы,
- их трудно использовать,
- очень просто передать бесконечный интервал в алгоритм, который его не переварит,
- интервалы, которые могут быть бесконечными или очень большими, могут вызвать переполнение в difference_type.
В следующем посте я опишу основы концепции моей новой библиотеки интервалов, которая бьёт в корень всех этих проблем. Не переключайтесь.
Вновь небольшой презент для добравшихся до конца. Ещё пять билетов со скидкой 30% по промокоду Infinite Ranges
UPD: По справедливому замечанию VoidEx исправили пассаж про zip. Спасибо!
Другие статьи цикла
Интервалы в С++, часть 1: Интервалы с ограничителями
Интервалы в С++, часть 3: представляем инкременторы (Iterable)
Интервалы в С++, часть 4: к бесконечности и далее
Комментарии (19)
nickolaym
11.08.2015 13:35auto dist = std::distance(iota.begin(), iota.end());
Этот и тому подобный код перестанет быть криминальным, если
— сделать iota::iterator моделью random access iterator (что?! вы это ещё не сделали?! зря...)
— установить в качестве значения «недостижимой бесконечности» какое-нибудь очень большое число, например, iota::infinity = std::limits<ptrdiff_t>::max
— реализовать арифметику по модулю infinity (либо молиться, что мы не добежим до целочисленного переполнения — ни по нашему модулю, ни по машинному)
— и, если очень хочется, подправить операцию вычитания так, что distance(N,infinity) = infinity; впрочем, это уже необязательно
Если итераторы — честные forward, то можно сделать хак, чтобы distance по-быстрому проверяло, не является правый аргумент «бесконечностью».
FreeMind2000
11.08.2015 14:04+1Господа!
Приведите хотя бы один пример из реальности, где в реальных вычислениях требуются бесконечные интервалы… И вообще, в чем их глубокий вычислительный смысл-то ???
fshp
11.08.2015 15:28C++ особого смысла в них нет, т. к. нет вменяемых инструментов для работы с ними.
В том же Haskell бесконечные списки используются во всю — для индексации элементов другой последовательности, для построения конечных последовательностей с заданными свойствами (но для этого генераторы удобнее).nickolaym
11.08.2015 17:57+1В хаскелле бесконечные списки — это генераторы, сделанные из удобного материала.
Будь то мап над йотой — т.е. [f x | x < — [1..]],
или итеративный процесс — iterate f x0 = [x0, f$x0, f$f$x0, ...],
или рекурсивные структуры — fibs = 0: 1: zipWith (+) fibs (tail fibs)
В С++ нет ленивых списков, соответственно, и выразительные средства другие.
Но те же итераторы (особенно из бустовского конструктора собери-сам) — вполне годная вещь, чтобы всякие групповые операции выражать через них.fshp
11.08.2015 19:04Семантически да. Но человек работает с синтаксисом. В первом примере в генераторе вы всё равно использовали синтаксис списков. А как оно устроено внутри уже не важно (если опустить вопрос производительности), главное использовать удобно.
Хвостовая рекурсия, например, обычный цикл «из удобного материала». Но мы их различаем.FreeMind2000
12.08.2015 18:10Кхм, кхм… это все понятно, я про другое, я спрашивал о бесконечности.
По вашим рассуждениям можно любой динамический контейнер назвать — бесконечным, хоть вектор, хоть список, хоть мап… в них нет ограничения на добавление.
Вот автор пишет:
— Необходимость бесконечных интервалов обосновать чуть сложнее.
А как по мне, то в C++ в них вообще смысла нет.
для контейнеров — vector, list и т.п…
для файлов, сокетов, портов… — потоки
Еще автор пишет:
— Представьте, что sin получает символы из сети, и этот код работает несколько дней, получая миллиарды символов.
Такое может себе представить только ненормальный программист, все нормальные знают — что если ты откуда-то получаешь постоянно данные, то они пишутся в буфер (разумного размера) и потом скидываются куда-там еще… хоть в файлы, хоть на дисплей… иначе — это утечка памяти.
Поэтому бесконечность в реальном мире — полная чушь. Я не понимаю, для чего нужны контейнеры, которые вместо своей длинны или итератора конца возвращают false.
Просто используйте while(true){std::cout << i++ << 'n';} — вот вам и вся бесконечность.
Зачем городить кучу мусорного кода для iota_range ??? В чем реальная польза этого класса? Очень хочется чтоб кто-нибудь привел пример его полезности в реалной жизни.fshp
12.08.2015 21:08Я вам выше написал, что в C++ они не нужны.
А в Haskell нет прямого аналога while(true).FreeMind2000
13.08.2015 17:07И я с Вами совершенно согласен, абсолютно непонятны мотивы и попытки автора реализации этой идеи на cpp.
fshp
13.08.2015 17:15«С++ тоже может». Статья чисто научно-развлекательного характера. Практической ценности она не предоставляет.
DrReiz
13.08.2015 18:28Кейс: получить первых N-штук, соответствующих условию F, из бесконечного генерируемого списка.
FreeMind2000
14.08.2015 17:01Ок :)
И как же должен выглядеть такой кейс с использованием беск.интервалов на сях? Я не совсем понимаю смысл фразы «из бесконечного генерируемого списка». В чем его плюс по сравнению с простым циклом и выходом по условию? Просто пример приведите…DrReiz
14.08.2015 17:34Бесконечно генерируемый список используется в переборных алгоритмах: bruteforce пароля, выбор лучшего хода в игре, поиск лекарства от рака и т.д. При генерации используется расширяющийся список комбинаций. На первом этапе — все комбинации из одного элемента, на втором — комбинации из двух элементов и т.д.
Концепция «бесконечные интервалов» удобна для отделения генераторов от самого алгоритма перебора (цикла). Концепция «бесконечных интервалов» удобна при комбинировании генераторов.FreeMind2000
14.08.2015 23:58С моей точки зрения их использование для этих целей не дает особого выигрыша ни в удобстве ни в производительности. Для комбинации генераторов достаточно в цикл передавать настраиваемый объект создающий комбинации для вызыва ф-ций генераторов по указателям.
Но спор наверно тут не имеет смысла, cpp позволяет решать одну задачу множеством вариантов, поэтому пусть каждый выбирает свой. Спасибо за более мене реальный пример применения.
nickolaym
11.08.2015 17:16+11) Забег по файлу, особенно, по stdin
2) Поэлементные операции — std::transform, например, в двуместном случае считают, что второй диапазон если не бесконечен, то уж заведомо не короче первого.
3) Операции линейного поиска — если заведомо известно, что искомое значение встретится. Старая добрая strlen — это пример реального вычисления с бесконечным интервалом «от этой буквы и до упора».
fshp
11.08.2015 15:24Ещё учесть случай distance(infinity,N)
nickolaym
11.08.2015 17:07Там много чего можно учесть.
Но вообще, distance над перевёрнутым диапазоном forward-итераторов — это просто неопределённое поведение.
Проще всего это просечь и пресечь так: запретить инкремент (и декремент) infinity. Банальным ассертом.
Даже нет нужды делать арифметику с насыщением, infinity+k == infinity-k == infinity. Лишние проверки в релизном коде.
Нет уж! Бесконечность так бесконечность. Просто для её реализации мы похитим одно целое число из 4 миллиардов или 16 квадрильонов. Как когда-то авторы Си похитили адрес 0 для нулевого указателя (своеобразной минус-бесконечности).
DrReiz
> Поскольку потоки ввода в принципе границ не имеют, то не существует знакового целого, достаточно большого для них
Достаточно int64. При считывание символа на такт — его хватит на время больше существования вселенной.
krasko
Если считывать по миллиарду символов в секунду, хватит на примерно 8 млрд секунд (если int64 знаковый) — примерно 250 лет. Не так и много.
PHmaster
После чего выводится ответ 42