Сбой стабильности std :: remove и std :: remove_if?
Недавно (из одного комментария) я узнал, что std::remove а также std:remove_if стабильны Я ошибаюсь, считая, что это ужасный выбор дизайна, поскольку он предотвращает определенные оптимизации?
Представьте себе удаление первого и пятого элементов 1М std::vector, Из-за стабильности мы не можем реализовать remove со свопом. Вместо этого мы должны сдвинуть каждый оставшийся элемент. 🙁
Если бы мы не были ограничены стабильностью, мы могли бы (для RA и BD iter) фактически иметь 2 итера, один спереди, второй сзади, а затем использовать своп, чтобы довести до конца подлежащие удалению элементы. Я уверен, что умные люди могли бы быть даже лучше. Мой вопрос в целом, а не о конкретной оптимизации, о которой я говорю.
РЕДАКТИРОВАТЬ: обратите внимание, что C ++ рекламирует принцип нулевых накладных расходов, а также есть std::sort а также std::stable_sort алгоритмы сортировки.
EDIT2:
Оптимизация будет выглядеть примерно так:
За remove_if:
- bad_iter с самого начала ищет те элементы, для которых предикат возвращает true.
- good_iter просматривает с конца те элементы, для которых предикат возвращает false.
когда оба нашли то, что ожидали, они обменяли свои элементы. Прекращение в good_iter <= bad_iter,
Если это помогает, подумайте об этом как об одном и том же в алгоритме быстрой сортировки, но мы не сравниваем их со специальным элементом, а вместо этого используем вышеупомянутый предикат.
EDIT3: Я играл и пытался найти худший случай (худший случай для remove_if — обратите внимание, как редко предикат будет правдой) и я получил это:
#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <memory>
using namespace std;
int main()
{
vector<string> vsp;
int n;
cin >> n;
for (int i =0; i < n; ++i)
{ string s = "123456";
s.push_back('a' + (rand() %26));
vsp.push_back(s);
}
auto vsp2 = vsp;
auto remove_start = std::chrono::high_resolution_clock::now();
auto it=remove_if(begin(vsp),end(vsp), [](const string& s){ return s < "123456b";});
vsp.erase(it,vsp.end());
cout << vsp.size() << endl;
auto remove_end = std::chrono::high_resolution_clock::now();
cout << "erase-remove: " << chrono::duration_cast<std::chrono::milliseconds>(remove_end-remove_start).count() << " milliseconds\n";
auto partition_start = std::chrono::high_resolution_clock::now();
auto it2=partition(begin(vsp2),end(vsp2), [](const string& s){ return s >= "123456b";});
vsp2.erase(it2,vsp2.end());
cout << vsp2.size() << endl;
auto partition_end = std::chrono::high_resolution_clock::now();
cout << "partition-remove: " << chrono::duration_cast<std::chrono::milliseconds>(partition_end-partition_start).count() << " milliseconds\n";
}C:\STL\MinGW>g++ test_int.cpp -O2 && a.exe
12345678
11870995
erase-remove: 1426 milliseconds
11870995
partition-remove: 658 milliseconds
Для других случаев, раздел немного быстрее, такой же или медленнее. Цвет меня озадачил. : D
Решение
Я полагаю, вы спрашиваете о гипотетическом определении stable_remove быть чем remove в настоящее время и remove чтобы быть реализованным, однако, разработчик считает, что лучше всего давать правильные значения в любом порядке. Ожидая, что разработчики смогут улучшить то же самое, что и stable_remove,
На практике библиотека не может без труда сделать эту оптимизацию. Это зависит от данных, но вы не хотите тратить слишком много времени, чтобы решить, сколько элементов будет удалено, прежде чем принимать решение о том, как удалить каждый из них. Например, вы можете сделать дополнительный проход для их подсчета, но во многих случаях этот дополнительный проход неэффективен. Тот факт, что нестабильное удаление в некоторых случаях происходит быстрее, чем стабильное, не обязательно означает, что адаптивный алгоритм выбора между ними является хорошей ставкой.
Я думаю разница между remove а также sort это сортировка известен быть сложной проблемой с множеством различных решений и компромиссов. Все «простые» алгоритмы сортировки работают медленно в среднем. Большинство стандартных алгоритмов довольно просты, и remove один из них, но sort не является. Я не думаю, что это имеет много смысла, поэтому определить stable_remove а также remove как отдельные стандартные функции.
Редактировать: ваше редактирование с моей настройкой (аналогично std::partition но не нужно держать значения справа) мне кажется довольно разумным. Это требует двунаправленного итератора, но в стандарте есть прецедент для алгоритмов, которые ведут себя по-разному в разных категориях итераторов, таких как std::distance, Таким образом, было бы возможно для стандарта определить unstable_remove только это требует прямой итератор, но делает свое дело, если получит двунаправленный итератор. Стандарт, вероятно, не выложит алгоритм, но он может иметь фразу вроде «если итератор двунаправленный, то самое большее min(k, n-k) движется куда k это количество удаленных элементов «, что фактически заставит его. Но обратите внимание, что стандарт в настоящее время не говорит, сколько ходов remove_if делает, поэтому я считаю, что закрепление этого просто не было приоритетом.
Конечно, ничто не мешает вам реализовать свои собственные unstable_remove,
Если мы признаем, что стандарту не нужно было указывать нестабильное удаление, тогда возникает вопрос, должна ли была быть вызвана определенная им функция stable_removeпредвидя будущее remove это ведет себя по-разному для двунаправленных итераторов и может вести себя по-разному для прямых итераторов, если какая-то хитрая эвристика для выполнения нестабильного удаления когда-либо станет достаточно известной, чтобы стоить стандартной функции. Я бы сказал, что нет: это не катастрофа, если названия стандартных функций не совсем регулярны. Это могло быть довольно разрушительным, чтобы убрать гарантию стабильности из STL remove_if, Тогда возникает вопрос: «Почему STL не назвал это stable_remove_if«На что я могу только ответить, что в дополнение ко всем пунктам, указанным во всех ответах, процесс проектирования STL был намного быстрее, чем процесс стандартизации.
stable_remove также откроет банку червей относительно других стандартных функций, которые могут теоретически есть нестабильные версии. Для особенно глупого примера следует copy называться stable_copyНа всякий случай существует какая-то реализация, на которой ее явно быстрее изменить порядок элементов при копировании? Должен copy называться copy_forward, так что реализация может выбрать, какой из copy_backward а также copy_forward называется copy по которому быстрее? Часть работы комитета — провести черту где-нибудь.
Я думаю, что реально существующий стандарт является разумным, и было бы разумно отдельно определить stable_remove и remove_with_some_other_constraints, но remove_in_some_unspecified_way просто не дает такую же возможность для оптимизации, что sort_in_some_unspecified_way делает. Интросорт был изобретен в 1997 году, так же, как стандартизировался C ++, но я не представляю себе, какие исследования были предприняты remove вполне то, что было и вокруг sort, Я могу ошибаться, оптимизируя remove может быть следующая большая вещь, и если так, то комитет упустил хитрость.
Другие решения
std::remove указано для работы с прямыми итераторами.
Подход с работой с парой итераторов, с начала и с конца, либо увеличит требования к итераторам и, таким образом, уменьшит полезность функции, либо нарушит / ухудшит гарантии асимптотической сложности.
Чтобы ответить на мой собственный вопрос> 3 года спустя 🙂
Да, это был «провал».
Есть предложение D0041R0 это добавило бы unstable_remove.
Можно утверждать, что только потому, что есть предложение добавить std :: unstable_remove, это не означает, что std :: remove было ошибкой, но я не согласен. 🙂
detector