{"id":33383,"date":"2023-02-07T13:31:08","date_gmt":"2023-02-07T08:01:08","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-fast-comparing-array-to-the-number\/"},"modified":"2023-02-07T13:31:08","modified_gmt":"2023-02-07T08:01:08","slug":"solved-fast-comparing-array-to-the-number","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-fast-comparing-array-to-the-number\/","title":{"rendered":"[Solved] Fast comparing array to the number"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

TL;DR<\/strong>: do it the obvious way, and make sure your compiler optimizes it.<\/p>\n

\n

It’s hard to reason about performance without a full, reproducible program example. So let’s start with a straightforward implementation:<\/p>\n

#include <array>\n#include <algorithm>\n\nstd::array<int, 362856427> a = {};\n\nint main()\n{\n    a[500] = 1;\n    a[5000] = 1;\n    a[50000] = 1;\n    a[500000] = 1;\n\n    auto counter = 0u;\n    for (auto i = 0u; i < a.size(); ++i) {\n    if (a[i] != 1)\n        ++counter;\n    }\n\n    return counter != 362856423;\n}\n<\/code><\/pre>\n
Timing this, I got 1.79 seconds of user time.  Then I realised my mistake, and added -O3<\/code> to my compilation command.  That’s better:<\/p>\n
g++ -std=c++17 -g -Wall -Wextra -O3  16385733.cpp -o 16385733\ntime .\/16385733 \n0.07user 0.08system 0:00.16elapsed 98%CPU (0avgtext+0avgdata 2212maxresident)k\n<\/code><\/pre>\n
We can attempt to simplify the loop, but this makes no measurable difference (the optimizer already beat us to this one):<\/p>\n
for (auto i = 0u;  i < a.size();  ++i)\n    counter += a[i] != 1;\n<\/code><\/pre>\n
Another option is to make the code clearer, by using a standard algorithm:<\/p>\n
auto counter = a.size() - std::count(a.begin(), a.end(), 1);\n<\/code><\/pre>\n
This consistently takes 50% longer than the obvious loop.<\/p>\n
If your input array was substantially larger, you might be able to gain by parallelizing the computation like this:<\/p>\n
     auto counter = 0ul;\n#pragma omp parallel for reduction(+:counter)\n    for (auto i = 0ul;  i < a.size();  ++i)\n        counter += a[i] != 1;\n<\/code><\/pre>\n
My benchmarking showed this as being as slow as the standard algorithm when the array size is 362856427, and no faster when it’s increased to 3628564270.<\/p>\n
There are a few ways to re-write in equivalent form:<\/p>\n
    for (auto i: a)\n        counter += i != 1;\n<\/code><\/pre>\n
    for (auto p = a.data();  p < end;  ++p)\n        counter += *p != 1;\n<\/code><\/pre>\n
All these exhibit similar performance, and aren’t improved with OpenMP.<\/p>\n
So the short answer is<\/p>\n