Может я чего-то не понимаю.... - C/C++

Здравствуйте, bnk, Вы писали:

R>

for(int x : numbers_in) if (!(x % 2)) numbers_out.push_back(x / 2);

bnk>Особенно сравнивая с нормальными языками

bnk>

numbers_in.filter(x => x % 2 == 0).map(x => x / 2)

Ну ты же жульничаешь — ты не положил числа в выходной массив. Ты предоставть законченное решение, тогда и сравним.

И запись, с которой сравниваешь, удалил зачем-то. Наверное, для того, чтобы сделать сравнение максимально наглядным

А во-вторых, в С++ тоже можно решить эту задачу в функциональном стиле и с lazy evaluation. Необходимая поддержка для этого давно уже есть в boost и сравнительно недавно появилась в стандартной библиотеке, в std::ranges:

http://coliru.stacked-crooked.com/a/dda09192df73cb9d

numbers_in | filtered([](int x) { return !(x % 2); }) | transformed([](int x) { return x / 2; })

Ну да, в C++ лябмды выглядят не столь компактными как в "нормальных" языках, но мы же не состязаемся в синтаксическом кариесе, правда?

Здравствуйте, rg45, Вы писали:

R>Ну и в-третьих, а чем, в данном случае, хуже "лобовое" решение с использованием обычного цикла?

R>

R>  for(int x : numbers_in) if (!(x % 2)) numbers_out.push_back(x / 2);
R>

Для плюсов — идеальный вариант, т.к. другие или корявые или сложные

Здравствуйте, Sm0ke, Вы писали:

S>Добавил свой алгоритм, сделанный на основании ranges::copy_if
S>( modified_copy_if: В предикат передаётся исходное значение, а в результат пишется проекция )
S>( В стандартном copy_if: проекция передаётся в предикат, но в результат пишет исходное )

S>Добавил custom div

S>Исходник: https://godbolt.org/z/K5hKP5fnv

Похоже, теперь я чего-то не понимаю. Я с самого начала думал, что здесь проходят соревнования, у кого короче.

Здравствуйте, B0FEE664, Вы писали:

BFE>Тут s_count=8'000'000;
BFE>https://godbolt.org/z/1vhEzfE4c
BFE>Добавил "многопоточность", а она ни на что не влияет

. Что я делаю не так?:

А почему ты ожидал ускорения от использования "многопоточки"? В частности для par (copy_if/transform+par_unseq), код копирования/фильтрации однопоточный, что фильтрация ,что трансформация примитивны, и если их убрать (копировать всё, возвращать оригинальное значение) на скорость это почти не влияет, но в твоём случае (для par) пробег по памяти в 1.5 раза больше. Хз что тут меряем, да ещё и на godbold

(к слову доступно всего 2 потока, в FAQ написано про 3).

==
А твой код был однопоточным, поэтому быстрым

По умолчанию алгоритмы execution используют дефолтный, последовательный backend (по asm листингу видно), надо добавить т.н. parallel backend, пока только один доступный — Intel TBB (-ltbb, но на godbold надо выбрать из предустановленных).

Убрал ranges, т.к. завёлся только gcc 11.2 с c++17 (как в примере для TBB на godbold), trunk правда тоже работает. Свежие версии gcc требуют отладочные либы TBB, которых нет в наличии.

https://godbolt.org/z/a15v7zWo3

mcq: 8050
mcq: 7462
for: 10950
for: 10982
for div: 21935
for div: 18560
par: 7672
check 1: 6953
par with mutex: 203897
check 2: 8464

Здравствуйте, B0FEE664, Вы писали:

BFE>Допустим, есть вектор с целыми числами, и требуется поделить все его числа на два. Те, которые не делятся, нужно просто выкинуть.

Если "в одну строчку", то удобно использовать ренжи.
Заодно позволит не создавать лишние буфера в процессе многостадийной обработки:

#include <iostream>
#include <ranges>
#include <boost/phoenix.hpp>

int main() {
    using namespace std;
    using views::filter;
    using views::transform;
    using boost::phoenix::placeholders::_1;

    //===========================================================

    auto const v1 = { 1, 2, 3, 4, 5, 3 };

    auto rng = v1 | filter(_1 % 2 == 0) | transform(_1 / 2);
    auto const vec = rng | ranges::to<vector>();

    //===========================================================

    ostream_iterator<int> const out { cout, " " };

    ranges::copy(v1, out), cout << std::endl;
    ranges::copy(rng, out), cout << std::endl;
    ranges::copy(vec, out), cout << std::endl;

    return 0;
}

Здравствуйте, B0FEE664, Вы писали:

BFE>Почему так сложно? Ведь задача решается в одну строчку:
BFE>

BFE>std::remove_if(numbers_in.begin(), numbers_in.end(), [](int& x){ const int s = x; x /= 2; return (s%2)==1; } );
BFE>

BFE>Или так нельзя?

Можно, но придется дописать, т.к. remove_if не удаляет элементы, несмотря на свое название.

Здравствуйте, B0FEE664, Вы писали:

BFE>Немного удивившись такому решению, быстрым поиском нашёл похожее у MS здесь
BFE>Почему так сложно? Ведь задача решается в одну строчку:
BFE>

BFE>std::remove_if(numbers_in.begin(), numbers_in.end(), [](int& x){ const int s = x; x /= 2; return (s%2)==1; } );
BFE>

BFE>Или так нельзя?

Ну, во-первых, правильно выше подсказывают, здесь не хватает вызова erase. И если его добавить, то твоя строчка становится чуть длиннее:

   numbers_in.erase(std::remove_if(numbers_in.begin(), numbers_in.end(), [](int& x){ const int s = x; x /= 2; return (s%2)==1; } ), numbers_in.end());

Во-вторых, по условию задачи результат нужно было сложить в другой массив, а ты удаляешь прямо в исходном. Или ты собираешься сперва скопировать все содержимое, а потом уже удалять? Это вообще не спортивно.

Ну и в-третьих, а чем, в данном случае, хуже "лобовое" решение с использованием обычного цикла?

  for(int x : numbers_in) if (!(x % 2)) numbers_out.push_back(x / 2);

А, ну и по сути вопроса — "почему так сложно?" — а ХЗ, почему. Мозги у людей как-то странно сложены.

Здравствуйте, rg45, Вы писали:

R>

numbers_in.erase(std::remove_if(numbers_in.begin(), numbers_in.end(), [](int& x){ const int s = x; x /= 2; return (s%2)==1; } ), numbers_in.end());

R>А, ну и по сути вопроса — "почему так сложно?" — а ХЗ, почему. Мозги у людей как-то странно сложены.

Особенно сравнивая с нормальными языками

numbers_in.filter(x => x % 2 == 0).map(x => x / 2)

Здравствуйте, rg45, Вы писали:

R>Во-вторых, по условию задачи результат нужно было сложить в другой массив, а ты удаляешь прямо в исходном. Или ты собираешься сперва скопировать все содержимое, а потом уже удалять? Это вообще не спортивно.
Нет, это в примере решена не та задача, которая поставлена.

R>Ну и в-третьих, а чем, в данном случае, хуже "лобовое" решение с использованием обычного цикла?
R>

R>  for(int x : numbers_in) if (!(x % 2)) numbers_out.push_back(x / 2);
R>

Ну, если добавить const:

for(const int x : numbers_in) if (!(x % 2)) numbers_out.push_back(x / 2);

то нормально, если нам действительно нужно копирование.

R>А, ну и по сути вопроса — "почему так сложно?" — а ХЗ, почему. Мозги у людей как-то странно сложены.
Мне кажется, что подобную задачу в качестве примера я не первый раз встречаю. Все её решают почему-то через промежуточный буфер... Отсюда и вопрос.

Здравствуйте, sergii.p, Вы писали:

SP>в условии ничего нет про то, что надо сложить результат в контейнер

Учу читать, пока бесплатно:

// задача: поделить на 2 все чётные числа из numbers_in
// и записать результаты в numbers_out
std:vector<int> intermediate;

здесь

Здравствуйте, McQwerty, Вы писали:

MQ>Здравствуйте, Sm0ke, Вы писали:

S>>Замерил на годболте через chrono: https://godbolt.org/z/dK4jsoxG3
S>>На массиве с 90к элементов

MQ>Дополнил тест следующим вариантом (с предварительным resize и последующим erase для v_dest):
MQ>

MQ>    {
MQ>        v_dest.clear();
MQ>        v_dest. resize (v_src. size ()); // 1
MQ>        const some_time v_start = std::chrono::system_clock::now(); // 2
MQ>        my_container::iterator d = v_dest. begin ();
MQ>        for (auto x : v_src)
MQ>        {
MQ>            * d = x >> 1;
MQ>            d += x & 1 ^ 1;
MQ>        }
MQ>        v_dest. erase (d, v_dest. end ());
MQ>        const some_time v_stop = std::chrono::system_clock::now();
MQ>        std::cout
MQ>            << "mcq: "
MQ>            << std::chrono::duration_cast<std::chrono::microseconds>(v_stop - v_start)
MQ>            << '\n'
MQ>        ;
MQ>    }
MQ>

А если всё же поменять местами строчки 1 и 2 ?
Ведь остальные способы работают изначально с пустым dst

Пофиксил, и почистил от остатков неполного рефактора: https://godbolt.org/z/5E8sco1Pv

mcq: 266us
mcq: 113us
for: 108us
for: 107us
algo: 118us
algo: 152us
for div: 382us
for div: 318us
algo div: 481us
algo div: 474us

Здравствуйте, Sm0ke, Вы писали:

S>Мне интересно почему for + div() медленнее, чем for?
S>Ведь казалось бы мы делаем две операции (деление и остаток) за одну инструкцию. Но видимо в std накосячили и что-то пошло не так. Или вообще что случилось?

сделал маленький рефакторинг https://godbolt.org/z/1aW4zzvoY
Получил

mcq: 52ms
for_loop: 45ms
algo: 45ms
for_loop_div: 252ms
algo_div: 345ms

с std::div реально какая-то шляпа. Меняю на my_div — все значения в пределах погрешности.

в итоге, если отбросить аномалию с std::div, то можно сказать, что результаты примерно одинаковые

Здравствуйте, Sm0ke, Вы писали:

S>Мне интересно почему for + div() медленнее, чем for?
S>Ведь казалось бы мы делаем две операции (деление и остаток) за одну инструкцию. Но видимо в std накосячили и что-то пошло не так. Или вообще что случилось?

Похоже что из-за отсутствия инлайна std::div (выполняется call)

Добавил mydiv и mydiv_noinline (эмуляция вызова std::div):

std::div_t mydiv(int x, int y)
{
    return { x / y, x % y };
}

std::div_t __attribute__ ((noinline)) mydiv_noinline(int x, int y)
{
    return { x / y, x % y };
}

Судя по asm смартовый оптимизатор выполняет idiv — та самая одна инструкция (частное в rax, остаток в rdx), а при инлайне mydiv заменяет её код на test (AND) и сдвиг (как в варианте mcq, да и в for такой же код генерится)

mydiv_noinline(int, int):
        mov     eax, edi
        cdq
        idiv    esi
        sal     rdx, 32
        or      rax, rdx
        ret

https://godbolt.org/z/a98Wv3bTM

for mydiv_noinline: 670us
for mydiv_noinline: 493us
for mydiv: 130us
for mydiv: 129us
mcq: 140us
mcq: 148us
for: 159us
for: 133us
algo: 264us
algo: 265us
for div: 529us
for div: 645us
algo div: 1039us
algo div: 765us

Здравствуйте, ArtDenis, Вы писали:

AD>Для плюсов — идеальный вариант, т.к. другие или корявые или сложные

Слишком простой код, нет клёвой функциональщины. Код сразу выдаёт старпёра, с которыми и смузи выпить не о чем, и на одном электросамокате не покататься.

Здравствуйте, rg45, Вы писали:

S>>Исходник: https://godbolt.org/z/K5hKP5fnv

R>Похоже, теперь я чего-то не понимаю. Я с самого начала думал, что здесь проходят соревнования, у кого короче.

Все соревнования всегда сводятся к тому, у кого длиннее

Знакомясь с возможностями C++20 наткнулся на статью здесь
Предлагается решить задачу:

Допустим, есть вектор с целыми числами, и требуется поделить все его числа на два. Те, которые не делятся, нужно просто выкинуть. Это несложно написать циклом, но для выразительности воспользуемся алгоритмами:

std:vector<int> numbers_in;
std:vector<int> numbers_out;

// задача: поделить на 2 все чётные числа из numbers_in
// и записать результаты numbers_out
std:vector<int> intermediate;

// скопируем в intermediate только чётные числа
std::copy_if(numbers_in.begin(), numbers_in.end(),  
             std::back_inserter(intermediate), 
             [](int x) {
                        return x % 2 == 0;
             }
);

// поделим их на 2
std::transform(intermediate.begin(), intermediate.end(),
               std::back_inserter(numbers_out),
               [](int x) {
                          return x / 2;
               }
)

Немного удивившись такому решению, быстрым поиском нашёл похожее у MS здесь
Почему так сложно? Ведь задача решается в одну строчку:

~~std::remove_if(numbers_in.begin(), numbers_in.end(), [](int& x){ const int s = x; x /= 2; return (s%2)==1; } );~~

Исправление (забыл отрезать хвост):

numbers_in.erase(std::remove_if(numbers_in.begin(), numbers_in.end(), [](int& x){ const int s = x; x /= 2; return (s%2)==1; } ), numbers_in.end());

Или так нельзя?

Здравствуйте, rg45, Вы писали:

bnk>>

numbers_in.filter(x => x % 2 == 0).map(x => x / 2)

R>Ну ты же жульничаешь — ты не положил числа в выходной массив. Ты предоставть законченное решение, тогда и сравним.

R>И запись, с которой сравниваешь, удалил зачем-то. Наверное, для того, чтобы сделать сравнение максимально наглядным

Ну совсем немного и сжульничал

R>А во-вторых, в С++ тоже можно решить эту задачу в функциональном стиле и с lazy evaluation. Необходимая поддержка для этого давно уже есть в boost и сравнительно недавно появилась в стандартной библиотеке, в std::ranges:

R>

R>numbers_in | filtered([](int x) { return !(x % 2); }) | transformed([](int x) { return x / 2; })
R>

R>Ну да, в C++ лябмды выглядят не столь компактными как в "нормальных" языках, но мы же не состязаемся в синтаксическом кариесе, правда?

Ну, да, выглядит получше. Хотя "=>" вместо того ужаса, что есть была бы как-то понятнее IMHO.

Здравствуйте, bnk, Вы писали:

bnk>Ну, да, выглядит получше. Хотя "=>" вместо того ужаса, что есть была бы как-то понятнее IMHO.

Ну, прямо "ужас" — лямбды не на птичьем языке записываются. По-моему, данная тема и данный форум — не лучшее место для обсуждения таких вопросов.

Здравствуйте, rg45, Вы писали:

bnk>>

numbers_in.filter(x => x % 2 == 0).map(x => x / 2)

R>Ну ты же жульничаешь — ты не положил числа в выходной массив. Ты предоставть законченное решение, тогда и сравним.

Это, кстати, от языка зависит. В некоторых языках map именно что создает новый контейнер:

r = [3, 4, 5, 6, 7, 8].filter {|x| x % 2 == 0}.map {|x| x/2}
p r # => [2, 3, 4]

Другое дело, что в таких языках никого не парит что за контейнер будет создан, как он будет расти и т.д., и т.п.

Здравствуйте, so5team, Вы писали:

bnk>>>

numbers_in.filter(x => x % 2 == 0).map(x => x / 2)

R>>Ну ты же жульничаешь — ты не положил числа в выходной массив. Ты предоставть законченное решение, тогда и сравним.

S>Это, кстати, от языка зависит. В некоторых языках map именно что создает новый контейнер:

Ну, как минимум, нужно сделать присваивание (инициализацию) — в любом языке. А если это C# (пардон, если не угадал), то еще и добавить преобразование к нужному типу. И если это сделать, то совсем не понятно, ради чего нужно было заводить очередной холивар:

numbers_out = numbers_in.filter(x => x % 2 == 0).map(x => x / 2).ToArray<int>();

for(int x : numbers_in) if (!(x % 2)) numbers_out.push_back(x / 2);

Здравствуйте, rg45, Вы писали:

R>Ну ты же жульничаешь — ты не положил числа в выходной массив.

это как акцент поставить. До С++20 нельзя сделать std::transform без создания выходного массива. В оригинальной статье явно этот момент и отмечался.
Там же есть уточнение:

Но если всё же вам необходимо вычислить всё сразу, вы можете по старинке сложить все элементы диапазона в какой-нибудь контейнер:
numbers_vector = std::vector(number_out.begin(), numbers_out.end());

Здравствуйте, sergii.p, Вы писали:

SP>это как акцент поставить. До С++20 нельзя сделать std::transform без создания выходного массива. В оригинальной статье явно этот момент и отмечался.

Так я проставил акцент: http://rsdn.org/forum/cpp/8568552.1

Ну и в-третьих, а чем, в данном случае, хуже "лобовое" решение с использованием обычного цикла?

В данном случае выходной массив создается по условию задачи.

Здравствуйте, rg45, Вы писали:

R>

R>Ну и в-третьих, а чем, в данном случае, хуже "лобовое" решение с использованием обычного цикла?

R>В данном случае выходной массив создается по условию задачи.

в условии ничего нет про то, что надо сложить результат в контейнер

Допустим, есть вектор с целыми числами, и требуется поделить все его числа на два. Те, которые не делятся, нужно просто выкинуть.

и там же дано объяснение почему "лобовое" решение "хуже"

Это несложно написать циклом, но для выразительности воспользуемся алгоритмами

"выразительность" — понятие условное конечно. Лично мне эти "фломастеры" нравятся.

Здравствуйте, B0FEE664, Вы писали:

BFE>Нет, это в примере решена не та задача, которая поставлена.

Ну, так а я тут при чем? Я вижу в ТВОЕМ сообщении формулировку: "задача: поделить на 2 все чётные числа из numbers_in и записать результаты в numbers_out". Я же с тобой общаюсь, поэтому то, что написано тобой я рассматриваю с более высоким приоритетом чем то, что находится по ссылкам. А если в твоем сообщении присутствуют противоречащие друг другу формулировки, то это твоя забота рассказать, что читать, а что игнорировать. В чем я не прав?

BFE>Ну, если добавить const:
BFE>

BFE>for(const int x : numbers_in) if (!(x % 2)) numbers_out.push_back(x / 2);
BFE>

BFE>то нормально, если нам действительно нужно копирование.

И почему здесь так важен этот const, не объяснишь? Помимо правил хорошего стиля.

Здравствуйте, B0FEE664, Вы писали:

BFE>Знакомясь с возможностями C++20 наткнулся на статью здесь
BFE>Предлагается решить задачу:
BFE>[q]
BFE>Допустим, есть вектор с целыми числами, и требуется поделить все его числа на два. Те, которые не делятся, нужно просто выкинуть.

Вариант с алгоритмами: https://godbolt.org/z/T4Ya6q58T

auto v_pred = [](my_item p) { return p % 2 == 0; };
auto v_mod = [](my_item p) { return p / 2; };
std::ranges::copy(
  std::ranges::filter_view(v_src, v_pred) | std::views::transform(v_mod),
  std::back_inserter(v_dest)
);

Деление и остаток в некоторых платформах делается за одну инструкцию, так воспользуемся std::div()

auto v_mod_1 = [](my_item p) { return std::div(p, 2); };
auto v_pred = [](const std::div_t & p) { return p.rem == 0; };
auto v_mod_2 = [](const std::div_t & p) { return p.quot; };
std::ranges::copy(
  std::ranges::transform_view(v_src, v_mod_1) | std::views::filter(v_pred) | std::views::transform(v_mod_2),
  std::back_inserter(v_dest)
);

Теперь Обычным Циклом:

for( auto it : v_src ) if( std::div_t res = std::div(it, 2); res.rem == 0 ) { v_dest.push_back(res.quot); }

Циклом, но без div():

for( auto it : v_src ) if( it % 2 == 0 ) { v_dest.push_back(it / 2); }

Но это же надо мерить по производительности

Замерил на годболте через chrono: https://godbolt.org/z/dK4jsoxG3
На массиве с 90к элементов

for: 201us
for: 138us
algo: 198us
algo: 130us
for div: 349us
for div: 363us
algo div: 587us
algo div: 508us

Не знаю на сколько можно доверять этим цифрам, ведь они менялись при перестановке способов в одной программе.

Здравствуйте, sergii.p, Вы писали:

SP> До С++20 нельзя сделать std::transform без создания выходного массива.
Почему так нельзя?:

std::transform(numbers_in.begin(), numbers_in.end(), numbers_in.begin(), [](int x){ return x/2;});

Здравствуйте, Sm0ke, Вы писали:

S>Замерил на годболте через chrono: https://godbolt.org/z/dK4jsoxG3
S>На массиве с 90к элементов

Дополнил тест следующим вариантом (с предварительным resize и последующим erase для v_dest):

    {
        v_dest.clear();
        v_dest. resize (v_src. size ());
        const some_time v_start = std::chrono::system_clock::now();
        my_container::iterator d = v_dest. begin ();
        for (auto x : v_src)
        {
            * d = x >> 1;
            d += x & 1 ^ 1;
        }
        v_dest. erase (d, v_dest. end ());
        const some_time v_stop = std::chrono::system_clock::now();
        std::cout
            << "mcq: "
            << std::chrono::duration_cast<std::chrono::microseconds>(v_stop - v_start)
            << '\n'
        ;
    }

Выхлоп для тех-же 90'000 элементов:

Program returned: 0
for: 337us
mcq: 132us
for: 195us
algo: 181us
algo: 192us
for div: 415us
for div: 457us
algo div: 526us
algo div: 600us

Здравствуйте, so5team, Вы писали:

bnk>>>

numbers_in.filter(x => x % 2 == 0).map(x => x / 2)

R>>Ну ты же жульничаешь — ты не положил числа в выходной массив. Ты предоставь законченное решение, тогда и сравним.

S>Это, кстати, от языка зависит. В некоторых языках map именно что создает новый контейнер:
S>

r = [3, 4, 5, 6, 7, 8].filter {|x| x % 2 == 0}.map {|x| x/2}

S>Другое дело, что в таких языках никого не парит что за контейнер будет создан, как он будет расти и т.д., и т.п.

Ну я и имел в виду, что новый контейнер создается. В смысле, должно быть

numbers_out = numbers_in.filter(x => x % 2 == 0).map(x => x / 2)

Т.е. я нарочно опустил присваивание "numbers_out" для того чтобы результат казался чуть короче.
Про что rg45 и пишет что "сжульничал". У тебя его кстати тоже нет.
В "функциональном стиле" (т.е. с использованием std::ranges) синтаксический оверхед (тм) примерно такой же
Кстати почему-то у меня код с "transformed" и "filtered" не компилируется в таком виде как дан (говорит что нет такой буквы в C++ 20)
Я думаю если компилируемый код сделать там еще процентов 50 запросто прибавится на всяких приседаниях.

Здравствуйте, bnk, Вы писали:

S>>Это, кстати, от языка зависит. В некоторых языках map именно что создает новый контейнер:
S>>

r = [3, 4, 5, 6, 7, 8].filter {|x| x % 2 == 0}.map {|x| x/2}

S>>Другое дело, что в таких языках никого не парит что за контейнер будет создан, как он будет расти и т.д., и т.п.

bnk>Ну я и имел в виду, что новый контейнер создается. В смысле, должно быть
bnk>

numbers_out = numbers_in.filter(x => x % 2 == 0).map(x => x / 2)

bnk>Т.е. я нарочно опустил присваивание "numbers_out" для того чтобы результат казался чуть короче.
bnk>Про что rg45 и пишет что "сжульничал". У тебя его кстати тоже нет.

Вообще-то есть, r называется.

Но чтобы быть совсем уж близко к первоисточнику, то следовало бы написать:

numbers_out = numbers_in.filter {|x| x % 2 == 0}.map {|x| x/2}

Здравствуйте, bnk, Вы писали:

bnk>Кстати почему-то у меня код с "transformed" и "filtered" не компилируется в таком виде как дан (говорит что нет такой буквы в C++ 20)

Ты имеешь в виду вот этот код? Так это же boost, а не std. Причем древняя как мир библиотека. Ну и по ссылке видно, что копмилируется и работает.

Здравствуйте, B0FEE664, Вы писали:

BFE>Мне кажется, что подобную задачу в качестве примера я не первый раз встречаю. Все её решают почему-то через промежуточный буфер... Отсюда и вопрос.

Ну так кто-то один написал, а остальные копипастят. Та же самая история, почему во всех примерах с циклом используется постинкремент переменной цикла.

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, bnk, Вы писали:

bnk>>Кстати почему-то у меня код с "transformed" и "filtered" не компилируется в таком виде как дан (говорит что нет такой буквы в C++ 20)

R>Ты имеешь в виду вот этот код? Так это же boost, а не std. Причем древняя как мир библиотека. Ну и по ссылке видно, что копмилируется и работает.

А, понял

Здравствуйте, rg45, Вы писали:

R>И почему здесь так важен этот const, не объяснишь? Помимо правил хорошего стиля.
Потому, что ближе к функциональному программированию, меньше ошибок.
Вообще говоря я в последние время редко использую неконстантные локальные переменные. Неконстантные локальные переменные — это обычно переменные для ввода-вывода. Так получается, что все изменения состояний лежат в объектах, которые живут всё время от запуска до завершения программы. Либо, как уже написал, в вводе/выводе.

Здравствуйте, Pzz, Вы писали:

Pzz>В одну строчку — это для любителей. А профессионал напишет полэкрана текста, как в приведенном тобой примере. Потому, что он профессионал.
У профессионала вообще не возникает таких ситуаций, когда в массиве лежат данные, которые следует выкинут.

Здравствуйте, B0FEE664, Вы писали:

R>>И почему здесь так важен этот const, не объяснишь? Помимо правил хорошего стиля.
BFE>Потому, что ближе к функциональному программированию, меньше ошибок.
BFE>Вообще говоря я в последние время редко использую неконстантные локальные переменные. Неконстантные локальные переменные — это обычно переменные для ввода-вывода. Так получается, что все изменения состояний лежат в объектах, которые живут всё время от запуска до завершения программы. Либо, как уже написал, в вводе/выводе.

Тут я с тобой полностью согласен. Но мы тут затеяли длиной меряться, а в данном конкретном случае наличие или отсутствие const на результат никак не влияет и я пошел на сделку со своей совестью и выбросил его. Целых пять букв, шутка ли. А с пробелом все шесть!

Здравствуйте, Sm0ke, Вы писали:

S>Пофиксил, и почистил от остатков неполного рефактора: https://godbolt.org/z/5E8sco1Pv

Мерить скорость на годболте — так себе идея

Здравствуйте, ArtDenis, Вы писали:

AD>Мерить скорость на годболте — так себе идея

Откомпилировал на ноутбуке, vs community 2022

mcq: 497us
mcq: 177us
for: 148us
for: 292us
algo: 239us
algo: 281us
for div: 1073us
for div: 1070us
algo div: 1788us
algo div: 1796us

mcq: 579us
mcq: 194us
for: 220us
for: 256us
algo: 219us
algo: 269us
for div: 1063us
for div: 1063us
algo div: 2196us
algo div: 2281us

Судя по разбросу мерить скорость на винде тоже не айс :Р
Так на чём мерить?

Здравствуйте, Sm0ke, Вы писали:

S>Судя по разбросу мерить скорость на винде тоже не айс :Р
S>Так на чём мерить?

А если вначале сделать "разогрев"?
Вставить перед замерами что-то типа:

    {
        for (auto it : v_src) {
            v_dest.push_back(it);
        }
    }

Похоже что после 1-й пробежки по памяти векторов данные остаются в кэше процессора и последующие обращения к памяти идут существенно шустрее.

Тут s_count=80'000.
https://godbolt.org/z/fK6boY8qn

mcq: 139us
mcq: 145us
for: 107us
for: 107us
algo: 127us
algo: 132us
for div: 359us
for div: 324us
algo div: 478us
algo div: 495us

Здравствуйте, Sm0ke, Вы писали:

S>Судя по разбросу мерить скорость на винде тоже не айс :Р
S>Так на чём мерить?

Как тут уже сказали, перед замером надо "прогревать" процессор. ОС выставит для него максимальную частоту и переключит твой поток на мощное ядро. Затем, один и тот же тест надо прогонять много раз, каждый раз считать время, а затем брать например, медианное значение. Но я бы не заморачивался и использовал какую-нибудь готовую либу для бенчмаркинга. В неё это всё будет уже встроено

Здравствуйте, pilgrim_, Вы писали:

_>Тут s_count=80'000.
_>https://godbolt.org/z/fK6boY8qn

_>

_>mcq: 139us
_>mcq: 145us
_>for: 107us
_>for: 107us
_>algo: 127us
_>algo: 132us
_>for div: 359us
_>for div: 324us
_>algo div: 478us
_>algo div: 495us

Мне интересно почему for + div() медленнее, чем for?
Ведь казалось бы мы делаем две операции (деление и остаток) за одну инструкцию. Но видимо в std накосячили и что-то пошло не так. Или вообще что случилось?

Здравствуйте, rg45, Вы писали:

BFE>>Мне кажется, что подобную задачу в качестве примера я не первый раз встречаю. Все её решают почему-то через промежуточный буфер... Отсюда и вопрос.

R>Ну так кто-то один написал, а остальные копипастят. Та же самая история, почему во всех примерах с циклом используется постинкремент переменной цикла.

Я всегда префиксный инкремент использую, для любых типов. Привычка. Впрочем, я сознательно себя к этому приучал в своё время

Здравствуйте, T4r4sB, Вы писали:

TB>Слишком простой код, нет клёвой функциональщины. Код сразу выдаёт старпёра, с которыми и смузи выпить не о чем, и на одном электросамокате не покататься.

Если бы плюсы позволяли удобную и понятную функциональщину, я бы предпочёл её

Здравствуйте, pilgrim_, Вы писали:

_>Тут s_count=80'000.
Тут s_count=8'000'000;
https://godbolt.org/z/1vhEzfE4c
Добавил "многопоточность", а она ни на что не влияет

. Что я делаю не так?:

Скрытый текст

    // par
    {
        v_dest.clear();
        const some_time v_start = std::chrono::system_clock::now();
        std::copy_if(v_src.begin(), v_src.end(),
                     std::back_inserter(v_dest),
                     [](int x) { return !(x & 0b1); });
        std::transform(std::execution::par_unseq, v_dest.begin(), v_dest.end(), v_dest.begin(), [](int n){ return n/2;});

        const some_time v_stop = std::chrono::system_clock::now();
        std::cout << "par: "
        << std::chrono::duration_cast<std::chrono::microseconds>(v_stop - v_start)
        << '\n';
        //std::cout << v_dest << '\n';
    }

    // with mutex
    {
        v_dest.clear();
        const some_time v_start = std::chrono::system_clock::now();

        std::mutex mtx;
        std::for_each(std::execution::par_unseq, v_src.begin(), v_src.end(),
                      [&mtx, &v_dest](int n)
                      {
                        if ( !(n & 0b1) )
                        {
                          n /= 2;
                          std::lock_guard<std::mutex> lock(mtx);
                          v_dest.push_back(n);
                        }  
                      }
                     );

        const some_time v_stop = std::chrono::system_clock::now();
        std::cout << "par with mutex: "
        << std::chrono::duration_cast<std::chrono::microseconds>(v_stop - v_start)
        << '\n';
        //std::cout << v_dest << '\n';
    }

mcq: 6942us
mcq: 7745us
for: 8207us
for: 8221us
algo: 8282us
algo: 9553us
for div: 24985us
for div: 24839us
algo div: 34929us
algo div: 36110us
par: 6198us
check 1: 5840us
par with mutex: 5927us
check 2: 4767us

Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, pilgrim_, Вы писали:

BFE>Добавил "многопоточность", а она ни на что не влияет

. Что я делаю не так?:

#define PARALLEL
#include <execution>

видимо, для MSVC и clang тоже надо что-то магическое дефайнить.

R>  for(int x : numbers_in) if (!(x % 2)) numbers_out.push_back(x / 2);
R>

R>А, ну и по сути вопроса — "почему так сложно?" — а ХЗ, почему. Мозги у людей как-то странно сложены.

Следует добавить, что третье решение — правильное, потому что решает задачу при максимальной простоте и читаемости, а не демонстрирует возможности с++ биб-ки. Это решение понятно и смузеру, и старпёру с базовыми знаниями по программированию. Остальные решение это оверинжениринг.

Здравствуйте, sergii.p, Вы писали:

SP>

SP>#define PARALLEL
SP>#include <execution>
SP>

Не, для gcc надо либу явно линковать (-ltbb, какой-то хак gcc — по используемой либе определяет соотв. макрос, анализируемый уже в коде на предмет доступности TBB), на godbold выбирается из предустановленных в GUI. В транке gcc видно начало поддержки OpenMP как ещё одного бэкенда, но не доделано, видать в бранче каком развивается.

Произвёл модификацию кода

Добавил свой алгоритм, сделанный на основании ranges::copy_if
( modified_copy_if: В предикат передаётся исходное значение, а в результат пишется проекция )
( В стандартном copy_if: проекция передаётся в предикат, но в результат пишет исходное )

Добавил custom div

Исходник: https://godbolt.org/z/K5hKP5fnv

Замеры на ноуте: (ms vc community 2022)

mcq: 2557us
mcq: 2257us
for loop: 2252us
for loop: 2627us
algo: 2456us (filter_view + transform)
algo: 2471us (filter_view + transform)
algo div: 21614us (transform div() + filter rem zero + transform quot)
algo div: 18330us (transform div() + filter rem zero + transform quot)
algo div custom: 13423us (transform my_div() + filter rem zero + transform quot)
algo div custom: 12781us (transform my_div() + filter rem zero + transform quot)
for div: 10058us
for div: 9904us
for div custom: 9812us
for div custom: 10002us
algo modified_copy_if: 1455us (custom algo)
algo modified_copy_if: 1453us (custom algo)

Замеры в готболте: (gcc)

mcq: 3334us
mcq: 2005us
for loop: 2518us
for loop: 2351us
algo: 1681us (filter_view + transform)
algo: 1671us (filter_view + transform)
algo div: 12756us (transform div() + filter rem zero + transform quot)
algo div: 13324us (transform div() + filter rem zero + transform quot)
algo div custom: 1831us (transform my_div() + filter rem zero + transform quot)
algo div custom: 2302us (transform my_div() + filter rem zero + transform quot)
for div: 9182us
for div: 8855us
for div custom: 1635us
for div custom: 1606us
algo modified_copy_if: 1570us (custom algo)
algo modified_copy_if: 1517us (custom algo)

Здравствуйте, pilgrim_, Вы писали:

BFE>>Добавил "многопоточность", а она ни на что не влияет

. Что я делаю не так?:

_>А почему ты ожидал ускорения от использования "многопоточки"?
Я ничего не читал про возможности параллельного выполнения, кроме описания на cppreference.com из которого мало что следует. Чисто теоретически все операции над элементами в std::transform могут быть выполнены параллельно и за одно и тоже время. Т.е. вот этот вызов:

std::transform(std::execution::par_unseq, v_dest.begin(), v_dest.end(), v_dest.begin(), [](int n){ return n/2;});

в идеале может быть выполнен за за время равное одному вызову [](int n){ return n/2;}.
Думаю, что на практике такая операция будет выполнятся над кусками.
Понятно, что многое зависит от аппаратной части и архитектуры процессора, за которыми я не слежу. Просто хотелось увидеть, как оно сейчас на практике. Похоже, что никак.

Здравствуйте, vdimas, Вы писали:

V>

V>#include <iostream>
V>#include <ranges>
V>#include <boost/phoenix.hpp>

V>int main() {
V>    using namespace std;
V>    using views::filter;
V>    using views::transform;
V>    using boost::phoenix::placeholders::_1;

V>    //===========================================================

V>    auto const v1 = { 1, 2, 3, 4, 5, 3 };

V>    auto rng = v1 | filter(_1 % 2 == 0) | transform(_1 / 2);
V>    auto const vec = rng | ranges::to<vector>();

V>    //===========================================================

V>    ostream_iterator<int> const out { cout, " " };

V>    ranges::copy(v1, out), cout << std::endl;
V>    ranges::copy(rng, out), cout << std::endl;
V>    ranges::copy(vec, out), cout << std::endl;

V>    return 0;
V>}
V>

чтож, неплохо!
Посмотрим детальнее

Вы забыли включить #include <vector> ( придираюсь к мелочам :Р )
Вроде рабочий вариант: https://godbolt.org/z/W17nbz8qx

ranges::to — из 23-го стандарта
Согласно cppref поддержка есть в:
* clang 17 (которого пока нет на готболт)
* msvc 19.34 (и он там есть)

Вы используете using-и, чтобы укоротить основную строчку, однако они сами добавляют отдельные строчки (хз честно это или нет).

V>Если "в одну строчку", то удобно использовать ренжи.
Там у вас две строки, а если в одну, то for всё равно короче)

vec = v1 | filter(_1 % 2 == 0) | transform(_1 / 2) | ranges::to<vector>();
for( auto it : v1 ) if( it % 2 == 0 ) { vec.push_back(it / 2); }

Однако для повторного использования забиндить цепочку изменений в переменную rng — конечно удобнее.

Здравствуйте, Sm0ke, Вы писали:

S>Вы используете using-и, чтобы укоротить основную строчку, однако они сами добавляют отдельные строчки (хз честно это или нет).

Однократно на некий файл, допустим, с несколькими функциями манипуляций данными.

V>>Если "в одну строчку", то удобно использовать ренжи.
S>Там у вас две строки

В одну, в одну ))
Копирование в вектор было необязательным, поэтому вынес в отдельную строку, но можно было приписать последней операцией в строке.
Т.е. суть в том, что на каждом этапе стоит оперировать концепцией ренжей и только ими, сохранять в переменную можно тоже просто ренж — специально это продемонстрировал, показав ranges::copy(rng, out) без сохранения в промежуточный контейнер.

А уже конечный ренж копировать или в хранилище, или передать в output_iterator, или еще куда-нить для последующей обработки.

S>а если в одну, то for всё равно короче)

На некоторых задачах да, но стремление к декларативности операций порой рулит, особенно если задача не диктует битовыжимание.

Опять же, ценность порой представляют не готовые трансформаторы данных, а вся инфрастуктура вокруг них, где ты относительно дешево можешь описывать свои прикладные повторно-используемые трансформаторы. Собсно, ради такого подхода к решению задач весь огород и нагородили.

S>ranges::to — из 23-го стандарта

Есть такое.
Можно юзать ренжи из буста (первоначальный вариант был бустовый), бо в стандарт еще не все плюшки переехали.
В смысле ренжей, атомик и потоков (пусть даже в версии 4) и прочих emplace, optional и т.д. Boost, конечно, оказал чудовищное влияние на язык и его стандарты.
Красавцы, чо! ))

S>Однако для повторного использования забиндить цепочку изменений в переменную rng — конечно удобнее.

Концепт ренжей прямо в стандарте описан как тип, который имеет операции begin(rng) и end(rng), при том что дефолтная реализация пытается взять rgn.begin() и rng.end(), т.е. подхватывает имеющиеся стандартные контейнеры и пользовательские типы, оформленные в STL-like манере, экономя на стороне прикладного кода избыточный однообразный код, где ты оперировал парой итераторов явно, замусоривая исходник. Казалось бы — на поверности... Но когда-то сделано не было в STL из-за отсутствия полноценной поддержки частичной специализации шаблонов... Но тут, как грится, лучше поздно, чем никогда. ))

Здравствуйте, ArtDenis, Вы писали:

AD>Как тут уже сказали, перед замером надо "прогревать" процессор. ОС выставит для него максимальную частоту и переключит твой поток на мощное ядро. Затем, один и тот же тест надо прогонять много раз, каждый раз считать время, а затем брать например, медианное значение.
Если измеряется быстродействие алгоритма в идеальных условиях, то надо брать лучшее значение, а не медианное.
(Идею не моя, а Александреску, он говорл о замерах алгоритмов в ФБ.)

От:	Pzz	https://github.com/alexpevzner
Дата:	25.07.23 23:19
Оценка:	+3

	От:	rg45
	Дата:	26.07.23 06:18
	Оценка:	+2

	От:	ArtDenis
	Дата:	26.07.23 09:31
	Оценка:	+3

	От:	rg45
	Дата:	02.08.23 14:40
	Оценка:

	От:	pilgrim_
	Дата:	01.08.23 23:16
	Оценка:	8 (1)

От:	bnk	http://unmanagedvisio.com/
Дата:	25.07.23 22:23
Оценка:	+1

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	02.08.23 14:42
Оценка:	-1

От:	so5team	https://stiffstream.com
Дата:	26.07.23 08:12
Оценка:

	От:	T4r4sB
	Дата:	30.07.23 08:10
	Оценка: