Pourquoi le traitement d'un tableau trié est-il plus rapide que celui d'un tableau non trié ?

Bonjour à tous ! Je suis un développeur C++ débutant et j'ai rencontré un problème très étrange lors de l'optimisation de code. J'ai une simple boucle qui additionne les éléments d'un tableau, mais seulement ceux qui sont supérieurs à un certain seuil. J'ai remarqué que si le tableau est trié, le code s'exécute plusieurs fois plus rapidement que s'il n'est pas trié. Voici un exemple de code : ```cpp #include #include #include #include int main() { const int SIZE = 100000; std::vector data(SIZE); // Remplir le tableau avec des nombres aléatoires for (int i = 0; i < SIZE; ++i) { data[i] = rand() % 256; } // Trier le tableau pour le premier test std::vector sorted_data = data; std::sort(sorted_data.begin(), sorted_data.end()); long long sum_sorted = 0; long long sum_unsorted = 0; // Mesurer le temps pour le tableau trié auto start = std::chrono::high_resolution_clock::now(); for (int i = 0; i < SIZE; ++i) { if (sorted_data[i] > 128) { sum_sorted += sorted_data[i]; } } auto end = std::chrono::high_resolution_clock::now(); auto duration_sorted = std::chrono::duration_cast(end - start).count(); // Mesurer le temps pour le tableau non trié start = std::chrono::high_resolution_clock::now(); for (int i = 0; i < SIZE; ++i) { if (data[i] > 128) { sum_unsorted += data[i]; } } end = std::chrono::high_resolution_clock::now(); auto duration_unsorted = std::chrono::duration_cast(end - start).count(); std::cout << "Temps trié : " << duration_sorted << " microsecondes\n"; std::cout << "Temps non trié : " << duration_unsorted << " microsecondes\n"; std::cout << "Somme triée : " << sum_sorted << "\n"; std::cout << "Somme non triée : " << sum_unsorted << "\n"; return 0; } ``` Quand j'exécute ce code, le résultat est surprenant. Le tableau trié est systématiquement plus rapide, parfois de 2 à 3 fois. Je sais que cela a probablement à voir avec la prédiction de branche, mais je ne comprends pas exactement comment cela fonctionne. Quelqu'un pourrait-il m'expliquer pourquoi cela se produit et comment cela affecte les performances ? Merci d'avance !