在布尔数组上使用二进制表达式的最快方法

Question

我需要以尽可能快的方式做这样的事情（O(1) 是完美的）：

for (int j = 0; j < V; ++j)
        {
            if(!visited[j]) required[j]=0;
        }

我想到了这个解决方案：

for (int j = 0; j < V; ++j)
        {
             required[j]=visited[j]&required[j];
        }

这使程序运行快了 3 倍，但我相信有更好的方法可以做到这一点。我说得对吗？

顺便说一句。 required 和 visited 是动态分配的数组

bool *required;
bool *visited;
required = new bool[V];
visited = new bool[V];

Answer 1

在您使用简单对象列表的情况下，您最适合使用 C++ 标准库提供的功能。所有现代编译器都能非常有效地识别和优化像 valarray 和向量这样的结构。

关于您可以在多大程度上依赖您的编译器存在很多争论，但一个保证是，您的编译器是与标准库一起构建的并且依赖它来实现基本功能（例如您的问题）通常是一个安全的选择.

永远不要害怕运行你自己的时间测试和你的编译器竞赛！这是一项有趣的练习，而且越来越难以实现。

构造一个valarray（在c++11及更高版本中高度优化）：

std::valarray<bool> valRequired(required, V);
std::valarray<bool> valVisited(visited, V);
valRequired &= valVisited;

或者，您可以使用转换在一行中完成：

std::transform(required[0], required[V-1], visited[0], required[0], [](bool r, bool v){ return r & v; })

编辑：虽然行数越少并不意味着速度越快，但您的编译器可能会将此操作向量化。

我也测试了他们的时间：

int main(int argc, const char * argv[]) {
    auto clock = std::chrono::high_resolution_clock{};
    {
        bool visited[5] = {1,0,1,0,0};
        bool required[5] = {1,1,1,0,1};

        auto start = clock.now();
        for (int i = 0; i < 5; ++i) {
            required[i] &= visited[i];
        }
        auto end = clock.now();
        std::cout << "1: " << (end - start).count() << std::endl;
    }

    {
        bool visited[5] = {1,0,1,0,0};
        bool required[5] = {1,1,1,0,1};

        auto start = clock.now();
        for (int i = 0; i < 5; ++i) {
            required[i] = visited[i] & required[i];
        }
        auto end = clock.now();
        std::cout << "2: " << (end - start).count() << std::endl;
    }

    {
        bool visited[5] = {1,0,1,0,0};
        bool required[5] = {1,1,1,0,1};

        auto start = clock.now();
        std::transform(required, required + 4, visited, required, [](bool r, bool v){ return r & v; });
        auto end = clock.now();
        std::cout << "3: " << (end - start).count() << std::endl;
    }

    {
        bool visited[5] = {1,0,1,0,0};
        bool required[5] = {1,1,1,0,1};
        std::valarray<bool> valVisited(visited, 5);
        std::valarray<bool> valrequired(required, 5);

        auto start = clock.now();
        valrequired &= valVisited;
        auto end = clock.now();
        std::cout << "4: " << (end - start).count() << std::endl;
    }
}

输出：

1: 102
2: 55
3: 47
4: 45
Program ended with exit code: 0

Answer 2

在@AlanStokes 的行中，使用打包的二进制数据并与AVX 指令结合_mm512_and_epi64，一次512 位。做好头发乱糟糟的准备。

在布尔数组上使用二进制表达式的最快方法

The fastest way to use a binary expression on array of booleans

c++

arrays

optimization

boolean-operations