c++

¿Por que un array ordenado se ejecuta más rápido?. Por Branch Prediction

Aquí está un pedazo de código de C++ que parece muy peculiar. Por alguna extraña razón, ordenar los datos milagrosamente hace que el código casi seis veces más rápido. #include #include #include int main() { // Generate data const unsigned arraySize = 32768; int data[arraySize]; for (unsigned c = 0; c < arraySize; ++c) data[c] = std::rand() % 256; // !!! With this, the next loop runs faster std::sort(data, data + arraySize); // Test clock_t start = clock(); long long sum = 0; for (unsigned i = 0; i < 100000; ++i) { // Primary loop for (unsigned c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC; std::cout << elapsedTime << std::endl; std::cout << "