1votos

Busqueda de un elemento mejorada en C

por josejuan hace 6 años

Realmente, el problema GENERAL no tiene solución, no es posible mejorar una búsqueda secuencial en una lista desordenada (no ser que usemos paralelización, ordenador cuántico, etc...). O BIEN, el problema esté concretado y alguna propiedad pueda ser explotada (eg. la suma de varios elementos). Mi solución únicamente se aprovecha del coste de hacer un JMP a nivel de máquina para mejorar el rendimiento (desenrollando el bucle). Pero el ALGORITMO sigue siendo de búsqueda exhaustiva.

Dado un vector enorme de enteros, implementar una algoritmo que encuentre un elemento en un tiempo menor a una busqueda secuencial

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
// Algoritmo trivial 
#include <malloc.h> 
 
#define N 50000000 
 
void main(void) { 
        int *v = (int*) malloc(sizeof(int) * N); 
        int *i, n; 
        for(n = 0, i = v; n < N; n++) *i++ = 100; 
        v[N-10] = 101; // "casi" el peor caso (para hacer down en subbúsqueda) 
        for(i = v; *i != 101; i++); 
        printf("Encontrado %i!\n", *i); 
 
// salida algoritmo trivial 
$ time ./searchBo 
Encontrado 101! 
 
real    0m0.472s 
user    0m0.317s 
sys     0m0.153s 
 
// Desenrollando el bucle 
#include <malloc.h> 
 
#define N 50000000 
 
void main(void) { 
        int *v = (int*) malloc(sizeof(int) * N); 
        int *i, n; 
        for(n = 0, i = v; n < N; n++) *i++ = 100; 
        v[N-10] = 101; // "casi" el peor caso (para hacer down en subbúsqueda) 
        int T = N/20; 
        for(n = 0, i = v; n < T; n++) { 
#define O && *i++ != 101 
                if(!(*i++ O O O O O O O O O O O O O O O O O O O)) { 
                        while(*--i != 101); 
                        printf("Encontrado %i!\n", *i); 
                        return; 
 
// salida desenrrollado 
$ time ./search 
Encontrado 101! 
 
real    0m0.368s 
user    0m0.213s 
sys     0m0.157s 
3 comentarios
0votos

Escrito por santanor hace 6 años

Nadie ha dicho que la paralelizacion no sea posible ;) de todas formas me gusta tu solucion de implementarlo a bajo nivel
0votos

Escrito por olga meneses orozco hace 3 años

sabes yo opino que el algoritmo secuencial d busqueda no es exsausta es mas bien falta de interpretacion saber manejarmiuy bien un algoritmo y solucionar el problema dado para poder hallar el ordenamiento de un algoritmo

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.