Сложность алгоритма std :: includes в C++
Алгоритм std::includes берет два отсортированных диапазона и проверяет, находится ли set2 в set1 (т.е. каждый ли элемент set2 включен в set1)?
Интересно, почему eel.is/c++draft говорит, что сложность этого алгоритма не больше сравнения 2·(N1+N2-1)?
То же указано по адресу:
1. cppreference
2. cplusplus
Мне кажется, что это должно быть только в большинстве сравнений с 2·N1, в худшем случае - с max(set2) >= max(set1).
Возможно, что в стандарте это указано, чтобы дать некоторую свободу реализации. Может существовать неочевидный алгоритм, который потенциально может быть быстрее, но может потребовать дополнительных сравнений.
@Justin, хорошее предположение, было бы круто, если бы кто-нибудь нашел эту реализацию, тем более реализованную в каком-нибудь компиляторе.
Ответы 3
Для наборов с чередованием, например 1,3,5,7 ..., 2,4,6,8, ..., нужно сравнить первый элемент каждого набора на равенство, и когда это не удается, нужно использовать элемент меньшего размера из отсортированной очереди. Другой способ - сравнить сначала a<b, затем b<a, предполагая, что доступен только оператор «меньше». В любом случае это приводит к 2 (N1 + N2 + c) сложности.
Этот анализ сложности может измениться с введением трехстороннего сравнения <=> с (N1 + N2-1).
Обновлено: да, вы правы. Алгоритм продвигает первый указатель на каждой итерации и останавливается, когда первый указатель / итератор достигает конца. Таким образом, будет максимум N итераций. Это не зависит от шагов, необходимых для продвижения итератора2. Ошибка в алгоритме примера, который не обрабатывает случаи set1 = {1,2,3}, set2 = {3,3,3, X} с повторениями.
алгоритм должен остановиться, когда он сравнит 3 и 2, потому что цикл for, предложенный в cppreference, имеет инвариант цикла first1 <= first2, не так ли?
он обрабатывает этот случай, потому что multiset1 не содержит multiset2, потому что первый имеет только одну 3, а второй - три 3. И эта операция считается стандартно как операция на наборах.
Я согласен с твоим выводом. Пример inteleaved sets из Ответ Аки Суйконена неверен, потому что алгоритм завершится раньше, чем 2 < 3.
В примере реализации cppreference есть цикл, который увеличивает first1 на каждой итерации, возвращается, когда first1 == last1, выполняет не более двух сравнений за итерацию и не содержит вложенных циклов. Я не понимаю, как это может сделать больше, чем сравнение 2xN1.
«Я не понимаю, как это могло сделать больше, чем 2xN1 сравнений». скажем, N1 == 1 и N2 == 5, а наборы - это {5} и {1,2,3,4,5}, как это можно сделать в двух сравнениях?
Поскольку на первой итерации алгоритм сравнивает 1<5, определяет, что 1 не входит в {5}, и возвращает false. В этом случае в примере реализации выполняется только одно сравнение.
А как насчет S1 = {5} и S2 = {5,5,5,5,5}? Я не понимаю, как это можно сделать в двух сравнениях
Ах, я предположил, что сначала проверяет, а потом второе, а не наоборот. Виноват
@Justin, в этом случае алгоритм остановится после первого сравнения, потому что на второй итерации указатель S1 будет увеличен, и алгоритм вернет false из-за first1 == last1. Фактически в каждом случае, когда N1 < N2 вернет false после итераций N1.
@Justin, нет, насколько я понимаю, в этом случае примерный алгоритм просто вернет false. Первый диапазон должен содержать то же количество копий, что и второй диапазон, чтобы std::includes вернул истину.
@MattHellige Тогда функция неправильно указана в стандарт. В нем говорится, что мы оцениваем ∀a∈S2, a∈S1, что, безусловно, может быть правдой, даже если |S2| > |S1|, поскольку S1 и S2 не являются наборами, а являются диапазонами с потенциально повторяющимися элементами.
@Justin, я думаю, что он правильно указал, потому что он работает для наборов и мультимножеств. Таким образом, наборы не могут содержать дубликатов. А мультимножество S1 = {1} не включает S2 = {1,1,1}, поэтому работает корректно. Стандарт говорит, что std :: includes - это операция над наборами.
@Justin Я склонен согласиться, но я также проверил поведение в gcc, и std::includes возвращает false для {5} и {5, 5, 5, 5, 5}. Таким образом, либо фактическая реализация также неверна, либо, вероятно, следует обновить спецификацию функции. Такое поведение меня тоже удивило!
Я создал проблема на github стандартного черновика C++. Об этом немного поговорили с Ричардом Смитом из Комитета по стандартам ISO C++.
С самого начала он отказался от вопроса, запутавшись в намерении std::includes. Но в конце концов согласились, что сложность функции должна быть пересмотрена после уточнения ее спецификации:
The complexity requirements are consistent with the current description, and should be fixed if/when the description is fixed to actually describe what the algorithm is "supposed' to do. Seems like LWG is already on the case. I'll reply to that lib thread to request that the complexity be revisited when the spec is fixed.
На этой странице есть образец реализации, сколько сравнений он выполняет?