¿Por qué es más rápido procesar una array ordenada que una array no ordenada?

Aquí hay un código C++ que ilustra que ordenar los datos milagrosamente hace que el código sea más rápido que la versión sin ordenar. Probemos un programa C++ de muestra para entender mejor la declaración del problema. 

Implementación:

// CPP program to demonstrate processing
// time of sorted and unsorted array
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
 
const int N = 100001;
 
int main()
{
    int arr[N];
 
    // Assign random values to array
    for (int i=0; i<N; i++)
        arr[i] = rand()%N;
 
    // for loop for unsorted array
    int count = 0;
    double start = clock();
    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;
 
    double end = clock();
    cout << "Time for unsorted array :: "
        << ((end - start)/CLOCKS_PER_SEC)
        << endl;
    sort(arr, arr+N);
 
    // for loop for sorted array
    count = 0;
    start = clock();
 
    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;
 
    end = clock();
    cout << "Time for sorted array :: "
        << ((end - start)/CLOCKS_PER_SEC)
        << endl;
 
    return 0;
}

Time for unsorted array::0.000844
Time for sorted array::0.00023

Observe que el tiempo necesario para procesar una array ordenada es menor en comparación con una array no ordenada. El motivo de esta optimización para la array ordenada es la predicción de ramas. 

¿Qué es la predicción de rama?
En la arquitectura de computadoras, la predicción de bifurcaciones significa determinar si es probable que se tome o no una bifurcación condicional (salto) en el flujo de instrucciones de un programa. Todos los procesadores segmentados realizan predicción de bifurcaciones de alguna forma, porque deben adivinar la dirección de la siguiente instrucción a buscar antes de que se haya ejecutado la instrucción actual. 

¿Cómo se aplica la predicción de rama en el caso anterior?  
La condición if verifica que arr[i] < 5000 , pero si observa en el caso de una array ordenada, después de pasar el número 5000, la condición siempre es falsa, y antes de eso siempre es verdadera, el compilador optimiza el código aquí y omite el if condición que se conoce como predicción de rama. 

Caso 1: array ordenada

    T = if condition true
    F = if condition false
    arr[] = {0,1,2,3,4,5,6, .... , 4999,5000,5001, ... , 100000}
            {T,T,T,T,T,T,T, .... , T,    F,   F,   ... ,    F  }    

Podemos observar que es muy fácil predecir la rama en un arreglo ordenado, ya que la secuencia es TTTTTTTTTTTT………FFFFFFFFFFFFFF 

Caso 2: array no ordenada

    T = if condition true
    F = if condition false
    arr[] = {5,0,5000,10000,17,13, ... , 3,21000,10}
            {T,T,F,     F,   T, T, ... , T, F,    T}

Es muy difícil predecir si la declaración será falsa o verdadera, por lo tanto, la predicción de ramificación no juega un papel importante aquí. 

La predicción de bifurcación funciona con el patrón que sigue el algoritmo o, básicamente, con el historial, cómo se ejecutó en los pasos anteriores. Si la conjetura es correcta, entonces la CPU continúa ejecutándose y si sale mal, entonces la CPU debe vaciar la canalización y retroceder a la rama y reiniciar desde el principio. 

En caso de que el compilador no pueda utilizar la predicción de saltos como herramienta para mejorar el rendimiento, el programador puede implementar sus propios trucos para mejorar el rendimiento. 

Este artículo es una contribución de Mandeep Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.