Самый быстрый способ использовать двоичное выражение в массиве логических значений

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 раза быстрее, но я считаю, что есть еще лучший способ сделать это. Я прав?

Btw. требуется и посещаются динамически распределяемые массивы

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

1

arrays boolean-operations c++optimization

Решение

Другие решения

В строке @AlanStokes используйте упакованные двоичные данные и объедините их с инструкцией AVX _mm512_and_epi64512 бит за раз. Будьте готовы к тому, что ваши волосы запутались.

0

Источник

Accepted Answer

В случае, когда вы используете список простых объектов, вам, скорее всего, лучше всего подходит функциональность, предоставляемая стандартной библиотекой C ++. Структуры, такие как valarray и векторы, очень эффективно распознаются и оптимизируются всеми современными компиляторами.

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

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

Создайте valarray (высоко оптимизированный в c ++ 11 и более поздних версиях):

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

В качестве альтернативы, вы можете сделать это одной строкой, используя transform:

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

2