performance - java - python vs c++ español - ¿Por qué el procesamiento de una matriz ordenada es más rápido que el de una matriz sin ordenar?

diferencia entre python y c++ / java / c++ / optimization / branch-prediction

He aquí un trozo de código C++que muestra un comportamiento muy peculiar.Por alguna extraña razón,ordenar los datos hace que el código sea milagrosamente casi seis veces más rápido:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generar datos
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! Con esto, el siguiente ciclo corre más rápido.
    std::sort(data, data + arraySize);

    // Prueba
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Bucle primario
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

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

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Al principio,pensé que podría tratarse de una anomalía del lenguaje o del compilador,así que probé con Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generar datos
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
        data[c] = rnd.nextInt() % 256;

        // !!! Con esto, el siguiente ciclo corre más rápido.
        Arrays.sort(data);

        // Prueba
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Bucle primario
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Aplet123



Answer #1

Utilizando el valor 0/1 del bit de decisión como índice en un array,podemos hacer un código que será igual de rápido tanto si los datos están ordenados como si no lo están.Nuestro código siempre añadirá un valor,pero cuando el bit de decisión sea 0,añadiremos el valor en algún lugar que no nos interese.Este es el código:

// Prueba
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Bucle primario
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];
// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}
if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

esta biblioteca haría algo así como

i = (x < node->value);
node = node->link[i];