Poesía Binaria

Extraer 10 elementos ordenados de grandes colecciones de datos

Gaspar Fernández

En ocasiones podemos tener una colección grande de información (de varios millones de elementos), y debemos obtener los diez primeros (por ejemplo) menores.
Por poner un ejemplo rápido, vamos a utilizar números, tenemos una colección de 15 números y necesitamos extraer los 5 menores:

1832312113126153146549234852154030209834

En este caso, queremos obtener: 20, 21, 30, 34, 98

El problema es la optimización, necesitamos hacerlo en el menor tiempo posible, utilizando la menor cantidad de operaciones, tal vez haya un método mejor que el que voy a proponer, aunque este no es malo del todo.

Imaginemos que nuestra colección de elementos es un array (por facilitar un poco las cosas) y tiene un millón de elementos (a los que asignaremos valores de manera aleatoria); queremos obtener los 10 elementos menores.

Para ello, he utilizado dos métodos:

  1. Ordenamos el array de elementos por completo y extraemos los 10 primeros.
  2. Generamos un array de menos elementos y vamos introduciendo los elementos más pequeños.

Para cronometrar el código he utilizado una función de un post anterior, además el algoritmo quicksort está sacado de Wikipedia.
Para medir el tiempo he hecho varias ejecuciones del algoritmo con la velocidad de mi procesador al mínimo (800MHz).
El primero de ellos es, digamos, el más intuitivo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <time.h>
#include <stdio.h>

#define TAM_ARRAY 1000000
#define TAM_LISTA 10

int colocar(int *v, int b, int t);
void quicksort(int* v, int b, int t);
unsigned long long crononsec(int startstop);

int main()
{
  int array[TAM_ARRAY];
  int i;

  crononsec(1);
  srand(time(NULL));
  for (i=0; i<TAM_ARRAY; i++)
    {
      array[i]=rand()%TAM_ARRAY;
    }
  printf("%.2fms generando array\n", (float)crononsec(0)/1000000);

   crononsec(1);
  quicksort(array, 0, TAM_ARRAY-1);
  printf("%.2fms ordenando array con quicksort\n", (float)crononsec(0)/1000000);

  for (i=0; i<TAM_LISTA; i++)
    printf("Elemento %d: %d\n", i, array[i]);
}

int colocar(int *v, int b, int t)
{
    int i;
    int pivote, valor_pivote;
    int temp;
 
    pivote = b;
    valor_pivote = v[pivote];
    for (i=b+1; i<=t; i++){
        if (v[i] < valor_pivote){
                 pivote++;    
                temp=v[i];
                v[i]=v[pivote];
                v[pivote]=temp;
 
        }
    }
    temp=v[b];
    v[b]=v[pivote];
    v[pivote]=temp;
    return pivote;
}
 
void quicksort(int* v, int b, int t)
{
     int pivote;
     if(b < t){
        pivote=colocar(v, b, t);
        quicksort(v, b, pivote-1);
        quicksort(v, pivote+1, t);
     }  
}

unsigned long long crononsec(int startstop)
{
  static unsigned long pre_time;
  static unsigned long pre_secs;
  struct timespec ts;

  if (startstop)
    {
      clock_gettime(CLOCK_MONOTONIC, &ts);
      pre_time=ts.tv_nsec;
      pre_secs=ts.tv_sec;
    }
  else
    {      
      clock_gettime(CLOCK_MONOTONIC, &ts);
      return (ts.tv_sec-pre_secs)*1000000000+ts.tv_nsec - pre_time;
    }

    return 0;
}

Este código ha tardado una media de 1045.66ms con 5 ejecuciones. Aunque sólo es un segundo, son un millón de elementos, no es mucho, y estamos hablando de una ejecución, en el caso de, por ejemplo una aplicación de servidor, con este mismo algoritmo ejecutándose de forma concurrente todo se retrasa mucho más.

El algoritmo que propongo es el siguiente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <time.h>
#include <stdio.h>

#define TAM_ARRAY 1000000
#define TAM_LISTA 10

void diezmenores(int *v, int *lista, int total_lista, int total);
unsigned long long crononsec(int startstop);

int main()
{
  int array[TAM_ARRAY];
  int lista[TAM_LISTA];
  int i;

  crononsec(1);
  srand(time(NULL));
  for (i=0; i<TAM_ARRAY; i++)
    {
      array[i]=rand()%TAM_ARRAY;
    }
  printf("%.2fms generando array\n", (float)crononsec(0)/1000000);

  crononsec(1);
  diezmenores(array, lista, TAM_LISTA, TAM_ARRAY);
  printf("%.2fms ordenando array con diezmenores\n", (float)crononsec(0)/1000000);

  for (i=0; i<TAM_LISTA; i++)
    printf("Elemento %d: %d\n", i, lista[i]);
}

void diezmenores(int *v, int *lista, int total_lista, int total)
{
  int i;
  int j;
  int mayor=v[0];
  int pmayor=0;
  for (i=0; i<total_lista; i++)
    {
      lista[i]=v[i];
      if (lista[i]>mayor)
    {
      pmayor=i;
      mayor=lista[i];
    }
    }
  for (i=total_lista; i<total; i++)
    {
      if (v[i]<mayor)
    {
      lista[pmayor]=v[i];
      pmayor=0;
      mayor=lista[0];
      for (j=1; j<total_lista; j++)
        {
          if (lista[j]>mayor)
        {
          mayor=lista[j];
          pmayor=j;
        }
        }    
    }
    }
}

unsigned long long crononsec(int startstop)
{
  static unsigned long pre_time;
  static unsigned long pre_secs;
  struct timespec ts;

  if (startstop)
    {
      clock_gettime(CLOCK_MONOTONIC, &ts);
      pre_time=ts.tv_nsec;
      pre_secs=ts.tv_sec;
    }
  else
    {      
      clock_gettime(CLOCK_MONOTONIC, &ts);
      return (ts.tv_sec-pre_secs)*1000000000+ts.tv_nsec - pre_time;
    }

    return 0;
}

Con este algoritmo el tiempo es de: 21.236ms por ejecución, es decir, 49.240 veces menos.
Vale, los resultados no se obtienen ordenados, pero sería muy rápido aplicar quicksort (o cualquier método de ordenación) a la lista de 10 elementos.
Por otra parte, dado que el objetivo del algoritmo no es ordenar el array ni nada de eso, si hacemos que el tamaño de la lista sea muy grande, el tiempo de ejecución crecerá muy rápidamente (la lista debe ser relativamente pequeña).

Lo podemos utilizar para dar una muestra de datos de forma rápida, por ejemplo, ante la existencia de varios millones de elementos, podemos elegir unos 200 aplicando un cierto criterio (orden alfabético, o numérico entre ellos).

También podría interesarte....