Почему обработка отсортированного массива выполняется быстрее, чем обработка несортированного массива? ⇐ C++

[Anonymous]

В этом коде C++ сортировка данных (до временной области) ускоряет основной цикл примерно в 6 раз:

Код: Выделить всё

#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)
{
for (unsigned c = 0; c < arraySize; ++c)
{   // Primary loop.
if (data[c] >= 128)
sum += data[c];
}
}

double elapsedTime = static_cast(clock()-start) / CLOCKS_PER_SEC;

std::cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array[/url]