Comments 33
А что не так с io streams?
Первые реализации streams были значительно медленнее аналогов из C stdlib,
поэтому сложилось предубеждение, что io stream это плохо:
https://stackoverflow.com/questions/18688763/why-is-istream-ostream-slow
Например что файл перестал читаться на середине или в файле внезапно встретилось не число а строка в нужном месте.
Несколько замечаний.
- Если используете потоки и не используете stdio обязательно отключайте синхронизацию с stdio sync_with_stdio, потоки ускорятся в несколько раз:
int main() { std::ios::sync_with_stdio(false); // ... } - Вектор при добавлении элементов может выполнять реаллокацию, что крайне неэффективно. Поэтому если вы знаете, сколько примерно элементов будете обрабатывать, то сделайте v.reserve() с небольшим запасом. Если нет, то можно хотя бы выделить страницу памяти (4096 байт), так как меньше страницы в любом случае не выделится:
v.reserve(4096); - Используйте cbegin() и cend() вместо begin() и end() там, где это возможно
- Сортировать массив сложных структур не особо эффективное занятие, либо определите swap для своей структуры, либо сортируйте указатели. Так как у нас контейнер владеет данными, то вполне подойдет std::unique_ptr:
std::vector<std::unique_ptr<man>> v; // ... std::sort(v.begin(), v.end(), [](const auto& m1, const auto& m2){return m1->age < m2->age;}); - Вот это также неэффективно:
std::copy_if(v.begin(), v.end(), std::ostream_iterator<man>(std::cout, "\n"), predicate(20, 25));
Вектор уже отсортирован, нет необходимости просматривать его целиком. Можно найти начало требуемого диапазона (age > 20) бинарным поиском std::lower_bound и выводить элементы, пока мы не выйдем из диапазона (age < 25). Так можно просмотреть лишь небольшую часть массива.
С++ это язык написания прежде всего эффективного кода (если эффективность для вас не важна, лучше взять другой, более удобный язык), не нужно гнаться за красотой. Если "красивый" алгоритм из STL делает что-то хуже (применительно к вашей задаче), чем можно сделать "некрасиво" руками, то использовать его не нужно.
Если нет, то можно хотя бы выделить страницу памяти (4096 байт), так как меньше страницы в любом случае не выделится:
v.reserve(4096);
Для reserve указывается число элементов, не байт. Кроме того, при добавлении в вектор и исчерпании capacity оно увеличивается в 1.5 раз (по крайней мере, там, где я видел реализацию, но по крайней мере всегда во сколько-то раз, а не на сколько-то). А это приводит к тому, что до 4096/sizeof(T) вектор дорастёт очень быстро, и смысла в этом reserve нет. Но, разумеется, если число элементов заранее известно, то reserve не помешает в любом случае, даже для нескольких элементов.
Для reserve указывается число элементов, не байт.
Да, конечно, там должно быть что-то вроде v.reserve(4096 / sizeof(decltype(v.front())))
Кроме того, при добавлении в вектор и исчерпании capacity оно увеличивается в 1.5 раз
Странно, где вы видели увеличение в 1.5 раза. Сейчас посмотрел у себя в libstdc++ 8.1 (g++ 8.1) размер увеличивается в 2 раза:
size_type
_M_check_len(size_type __n, const char* __s) const
{
if (max_size() - size() < __n)
__throw_length_error(__N(__s));
const size_type __len = size() + std::max(size(), __n); // <---------------
return (__len < size() || __len > max_size()) ? max_size() : __len;
}В VC++, насколько я помню, также в 2 раза, но это нужно отдельно смотреть
Да, в VC++ (VS 2017, 15.4.1) как раз таки в 1.5 раза
size_type _Calculate_growth(const size_type _Newsize) const
{ // given _Oldcapacity and _Newsize, calculate geometric growth
const size_type _Oldcapacity = capacity();
if (_Oldcapacity > max_size() - _Oldcapacity / 2)
{
return (_Newsize); // geometric growth would overflow
}
const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
if (_Geometric < _Newsize)
{
return (_Newsize); // geometric growth would be insufficient
}
return (_Geometric); // geometric growth is sufficient
}
Зависит от реализации, Саттер (?) говорил, что надо на золотое сечение увеличивать
Вы уж меня простите, но не вижу смысла в указанных замечаниях к учебному примеру. Особенно в 5 пункте. Оцените эффективность предложенного вами решения и увидите, что в худшем случае сложность O(sqrt(N) +N), в среднем делим О пополам. Так зачем в учебном примере со сложностью О(N) заниматься подобной оптимизацией? Вероятно, плохо я определил идею примеров, если появляются такие комментарии.
Хорошо, оцениваем.
Ну, во-первых, там не O(sqrt(N) + N), а O(ln(N) + N). А логарифм — очень и очень медленно растущая функция. Например, двоичный логарифм 1 000 000 всего около 20, а 1 000 000 000 — около 30. Так что можно сказать, что O(ln(N) + N) = O(N), что кстати верно также по определению асимптотической сложности.
Во-вторых, у нас не абстрактные циферки, а реальный возраст реальных людей. То есть, данные подчиняются некому статистическому распределению. Поскольку в статье ничего не сказано о выборке, будем считать ее среднестатистической. Возьмем распределение по возрастам жителей России за 2017 год http://www.statdata.ru/nasel_pol_vozr. Нам нужен диапазон 21-24, но для простоты возьмем 20-24 (на деле выигрыш будет еще больше). Людей в возрасте 20-24: 7 828 тыс., всего людей 146 804 тыс. Проигрыш copy_if будет составлять 18,8 раз (!), что, извините, слишком много, даже для учебной статьи.
В целом, у вас неплохая статья, но вот пример с copy_if выбран не совсем удачно. Можно, например, сформулировать условие так, что даны два неупорядоченных списка людей, нужно первый отсортировать по возрасту, а из второго выбрать людей с возрастом 21-24 года. Тогда никаких вопросов к использованию copy_if не было бы.
А при чем здесь статистика? Входной файл может быть списком учащихся в стране с болонской системой обучения. Тогда, статистика покажет другой результат.
Тогда спрашивается, зачем в учебном примере всё это?
Входной файл может быть списком учащихся в стране с болонской системой обучения.
В условии этого не сказано, поэтому рассматриваем выборку как среднестатистическую
Тогда спрашивается, зачем в учебном примере всё это?
Зачем в учебном примере учить применять алгоритм, который здесь явно применять не следует?
Выводим: lower_bound по нижней границе возраста по всему диапазону данных и lower_bound по верхней границе возраста и в диапазоне от результата первого поиска и до конца исходного диапазона.
Преимуществом того, что данные отсортированы, стоит воспользоваться)
Более того, у вас уже есть comparator (хотя для lower_bound понадобится иной)
Вектор уже отсортирован, нет необходимости просматривать его целиком.
С одной стороны — да. Но с другой стороны, асимптотику операции это никак не улучшит, как было Θ(N), так и осталось. Кроме того, на фоне сортировки за Θ(N log N) лишний проход по вектору и вовсе теряется.
Вектор при добавлении элементов может выполнять реаллокацию, что крайне неэффективно.
Тоже самое возражение: на фоне сортировки лишние аллокации в векторе теряются.
Кстати, диапазон возрастов людей сильно ограничен (к сожалению). Поэтому тут можно отсортировать массив подсчетом за O(N), использование std::sort также вызывает вопросы.
В общем, к сожалению, автор выбрал не самые удачные примеры
На кой черт в структуре man поле age объявлено как size_t?
Для хранения возраста простого int более чем достаточно. Для игр в переносимость кода можно использовать uint_fast8_t.
Усложняя стандартный пример