viernes, 18 de octubre de 2013

Punteros en Python (Pointers in Python)

En realidad en Python todo son punteros he aquí una prueba sencilla:
In Python all are pointers here's a simple example:
a=1
id(a) # posicion 11111
b=2
id(b) # posicion 22222
Los dos apuntan a posiciones distintas, pero....
They point to different positions, but ....
id(a) # posicion 11111
b=a
id(b) # posicion 11111
TACHAN!!! B apunta a la misma posición que A. De todas formas si ahora modificamos el valor de B el valor de A no varía. Para lograr simular un puntero de verdad. Tenemos que hacer el siguiente apaño.
TACHAN! B has the same position as A. But if we change B, A does not change. To simulate this we have to do ...
class ref:
    def __init__(self, obj): self.obj = obj
    def get(self):    return self.obj
    def set(self, obj):      self.obj = obj

a = ref(1)
b = a
print a.get()  # 1
print b.get()  # 1

b.set(2)
print a.get()  # => 2
print b.get()  # => 2
happy coding ;)

lunes, 14 de octubre de 2013

Busquedas binarias en Python (Binary search in Python)

Hoy os presento 3 sencillos casos de búsqueda binaria. Antes de usar este sencillo algoritmo necesitamos una lista ordenada. Mi primer ejemplo con un árbol.
Today i present three cases of simple binary search. Before using this simple algorithm we need an ordered list. My first example with a tree.
class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def binary_insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child == None:
                root.l_child = node
            else:
                binary_insert(root.l_child, node)
        else:
            if root.r_child == None:
                root.r_child = node
            else:
                binary_insert(root.r_child, node)

def searchNode(root,search):
    if not root:
        return        
    searchNode(root.r_child,search)
    if root == search:
        print(root.data)
    searchNode(root.l_child,search)

def resultUp(r,node):
    if not r:
        return
    print(r.data)
    if r == node:
        return
    resultUp(r.r_child,node) 

def resultPointToPoint(ini,fin):
    if not ini:
        return 
    if ini == fin:
        print(ini.data)
        return
    print(ini.data)
    resultPointToPoint(ini.r_child,fin)
    resultPointToPoint(ini.l_child,fin)

Example:
r = Node(0)
n1= Node(1)
n2= Node(2)
n3= Node(3)
n4= Node(4)
n5= Node(5)
n6= Node(6)
n7= Node(7)
n8= Node(8)

binary_insert(r,n1)
binary_insert(r,n2)
binary_insert(r,n3)
binary_insert(r,n4)
binary_insert(r,n5)
binary_insert(r,n6)
binary_insert(r,n7)
binary_insert(r,n8)


print("Search n1")
searchNode(r,n1)

print("n2 to n5")
searchPointToPoint(r,n2,n5)

print("n5 route to r")
resultUp(r,n5)

Este ejemplo es el método más complejo para implementarlo. Ahora os muestro otro caso de busqueda binaria más simplificada:
This example is the most complex to implement. Now I show another case of more simplified binary search:
import random

def binary_search(the_array, the_key, imin, imax):
    while imax >= imin:
        imid = int(imin + ((imax - imin) / 2))
        if the_array[imid] < the_key:
            imin = imid + 1
        elif the_array[imid] > the_key:
            imax = imid - 1
        else:
            return imid
    return None

Example:
print (binary_search(range(0,1000),21,0,1000))

Por último el mismo caso que el anterior pero usando la recursividad:
Finally the same case as above but using recursion:
import random

def binary_search_recur(the_array, the_key, imin, imax):
    if (imax < imin):
        return None
    else:
        imid = int(imin + ((imax - imin) / 2))
        if the_array[imid] > the_key:
            return binary_search_recur(the_array, the_key, imin, imid-1)
        elif the_array[imid] < the_key:
            return binary_search_recur(the_array, the_key, imid+1, imax)
        else:
            return imid

Example:
print (binary_search_recur(range(0,1000),21,0,1000))

Y con estos sencillos ejemplos me despido hasta la siguiente entrada.
And with these simple examples I say goodbye until the next entry.