domingo, 15 de marzo de 2015

SUMA CREW

SUMA CREW (Concurrent Read Exclusive Read) 
Sumas Prefijas

Algoritmo:

for i=1 to log2 n do
    forall Pj where 2i-1+1≤ j ≥ n doinparallel
        a[j]←a[j]+a[j-2i-1]
    end forall
endfor


En python:

import threading
import math

#Definicion del hilo
def hilo(i,j):
    a[j]=a[j]+a[j-pow(2,i-1)]

#Programa Principal
a=[0,5,2,10,1,8,12,7,3]

n=len(a)
lg=int(math.log(n,2))

for i in range(1,lg-1):
    for j in range((pow(2,i-1)+1),n):
        h = threading.Thread(target=hilo,args=(i,j))
        h.start()
        h.join()

print a

SUMA EREW

SUMA EREW (Exclusive Read Exclusive Write)
Reducción Paralela


Algoritmo:

for i=1 to log2  n do 
    forall Pj where 1≤ j ≥n/2 doinparallel
        if (2j modulo 2i)=0 then
a[2j]←a[2j]+a[2j-2i-1]
        endif
    end forall
end for


En python:

import threading
import math

#Definicion del hilo
def hilo(i,j):
    if(((2*j)%int(pow(2,i)))==0):
       a[2*j]=a[2*j]+a[int((2*j)-pow(2,i-1))]

#Programa Principal
a=[0,5,2,10,1,8,12,7,3]

n=len(a)
lg=int(math.log(n,2))

for i in range(1,lg+1):
    for j in range(1,(n/2)+1):
        h = threading.Thread(target=hilo,args=(i,j))
        h.start()
        h.join()

print a

domingo, 1 de marzo de 2015

Bùsqueda Binaria



Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.

Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.

A continuación se muestra el código para este tipo de bùsqueda en Python:

#BUSQUEDA BINARIA

def BubbleSort(A,n):
    i=0
    while(i<=(n-2)):
        j=0
        while(j<=(n-2-i)):
            if (A[j+1]<A[j]):
                a=A[j]
                A[j]=A[j+1]
                A[j+1]=a
            j=j+1
        i=i+1       
    return A

def BusquedaBinaria(C,B,j):
    if(B==int(C[j])):
        return 1,j       
    else:
        if(len(C)==1 or j<1):
            return 0,j
        if(B<C[j]):
            return BusquedaBinaria(C[:j],B,j/2)
       
           
        else:
            return BusquedaBinaria(C[j+1:],B,j/2)
           

a=[]
prueba = [1,50,34,2,7,788]
valorABuscar=7

C=BubbleSort(prueba,len(prueba))

i=0
while (i<len(prueba)):
    a.append(int(C[i]))
    i=i+1
if((len(a)%2)==0):
    j=((len(a)/2)-1)
else:
    j=(len(a)/2)

x,y=BusquedaBinaria(a,valorABuscar,j)

if(x==1):
    print ("Numero encontrado")
else:
    print ("Numero no encontrado")