Publi

Extraer 10 elementos ordenados de grandes colecciones de datos

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....

There are 7 comments left Ir a comentario

  1. Pingback: BlogESfera.com /

  2. Carlos Henríquez /
    Usando Google Chrome Google Chrome 12.0.742.112 en Linux Linux

    Habría que probarlo con tu manera de medir el tiempo pero la mejor forma para elegir los k menores (o mayores) elementos de una lista de N (N >> k) es utilizando un heap.

    Dado el arreglo original, construir un heap es O(n) y luego extraer los k menores sería O(k log N). Tu propuesta es O(kN) con un peor caso horrible si los elementos que quieres están al final del arreglo. Con un heap no hay peor caso.

    Si estás falto de tiempo, puedes probar a ver qué pasa y nos cuentas. Capaz y me animo yo durante la semana. No prometo nada.

  3. Carlos Henríquez /
    Usando Google Chrome Google Chrome 12.0.742.112 en Linux Linux

    @Carlos Henríquez

    Pues tengo noticias interesantes. Tú opción es totalmente válida siempre que TAM_LISTA sea mucho más pequeño en comparación con TAM_ARRAY (exageradamente más pequeño). He probado lo que te comenté en mi máquina y los resultados son los siguientes (medidos con tu función):

    TAM_ARRAY=1000000 TAM_LISTA=10
    Solución quicksort (tu implementación): 307.00ms
    Solución sort (de C++, no tu quicksort): 251ms
    Solución priority_queue: 131.94ms
    Solución heap (mi implementación): 36.35ms
    Solución diezmenores: 5.10ms

    Pasemos ahora a la teoría, porque los resultados en principio no parece cuadrar con los órdenes de los algoritmos. Manteniendo igual TAM_ARRAY pero variando TAM_LISTA tenemos los siguientes resultados:

    TAM_LISTA diezmenores heap
    100 4.45ms 36.75ms (0,01%)
    500 12.32ms 36.72 (0,05%)
    1000 31.65ms 36.56ms (0,1%)
    5000 521.39ms 43.56ms (0,5%)
    10000 1855.08ms 45.19ms (1%)

    Los porcentajes indican la relación TAM_LISTA/TAM_ARRAY.

    Ahora sí se aprecia la diferencia logarítmica entre ambas opciones. Por lo tanto, la opción de diezmenores (o k-menores pues es parametrizable) es válida pero dentro de una situación muy específica (hasta 0,05% apróximadamente).

    Esto es interesante pues nos recuerda que la notación big-O mide complejidad de los algoritmos para cantidades de datos grandes, pues es cuando se estabilizan los comportamientos. Cuando se trabaja con tamaños pequeños, casi todo se vale 😉

    ¿Qué te parece?

  4. Gaspar Fernández / Post Author
    Usando Mozilla Firefox Mozilla Firefox 5.0 en Linux Linux

    @Carlos Henríquez
    Carlos! ¡Cómo te lo curras! Yo he hecho una implementación con la priority_queue de C++ que ya viene hecha, y no tiene mala pinta, se mantiene entre (70 y 100ms, en mi ordenador, vamos), pero seguro que puedo optimizar un poco más.

    La solución, necesité hacerla en la práctica para 50 elementos dentro de una colección de 3*10^6 y por eso la publiqué, me pareció que rendía muy bien, pero claro, seguimos hablando de 0.005%.

    ¡Gracias por introducir un poquito de ciencia por aquí !

  5. Pingback: Bitacoras.com /

Leave a Reply