The difference between __getattribute__ and __getattr__

The other day I was teaching Python meta-programming to a workmate. I think it’s a good way to learn about high order functions since meta-programming makes extensive use of closures, function builders, decorators… I was trying to make a concept probe about a very, very generic REST connector. Here is my first (and wrong) attempt:

class RESTConn(object):

  def __init__(self, entry_point):
    self.entry_point = entry_point

  def method_builder(self, method_name):
    verb, _, collection = method_name.split('_', 2)
    def do_verb(payload=None, **kwargs):
      uri = self.make_uri(collection)
      querystring = self.make_querystring(kwargs)
      print verb.upper(), self.combine(uri, querystring)
      if payload:
        print payload

    return do_verb

  def make_uri(self, collection):
    return '/'.join([self.entry_point, collection])

  def make_querystring(self, kwargs):
    return '&'.join(['='.join(pair) for pair in kwargs.iteritems()])

  def combine(self, uri, querystring):
    if querystring:
      return '&'.join([uri, querystring])

    return uri

  def __getattribute__(self, name):
    if not hasattr(self, name):
      method = self.method_builder(name)
      setattr(self, name, method)

    return super(RESTConn, self).__getattribute__(name)

Try this example by instantiating a new connector and trying to call something like:

c = RESTConn('unoyunodiez.com')
c.get_from_articles()

The program falls into an infinite recursion and do nothing before crashing. Why?

There are three problems here. First and most important is using __getattribute__(), second is using hasattr() and third is accessing self.method_builder().

The object’s method __getattribute__() is used to retrieve an attribute from an instance. It captures every attempt to access an instance attribute by using dot notation or getattr() built-in function. Unless it was overridden, the former expression is translated into object.__getattribute__(self, ‘get_from_article’). The default implementations looks into the instance’s namespace, then looks into the class namespace, then into each base’s namespace and so on. Finally, if not found, the default implementation calls the fallback __getattr__() method of the instance and it raises an AttributeError exception as default implementation.

This is not a problem by itself but if you pay attention enough you’ll notice we are trying to create the new method only if the object does not have the method yet. It is semantically the same as overriding __getattr__() because it is called only when the attribute was not found. So, even if we cannot explain the infinite recursion error yet, we can fix the class by replacing:

  def __getattribute__(self, name):
    if not hasattr(self, name):
      method = self.method_builder(name)
      setattr(self, name, method)

    return super(RESTConn, self).__getattribute__(name)

with:

  def __getattr__(self, name):
    method = self.method_builder(name)
    setattr(self, name, method)
    return getattr(self, name)

So, the difference between __getattribute__() and __getattr__() is that the first one is called unconditionally when an attribute is being retrieved from an instance while the second is called only when the attribute was not found.

But, what about the infinite recursion? Why the first example was failing?

Seguir leyendo «The difference between __getattribute__ and __getattr__»

Django 1.5 in a nutshell I

In 2011, I wrote a quick tutorial about Django 1.3. I was going to demonstrate how to write a blog in just one hour in a live code session. This time I’m in a mentoring program teaching Python and Django to a colleague so I decided to update that tutorial. Django is now in version 1.5 and you can find what is new in the release notes of the framework. Let’s code!

Seguir leyendo «Django 1.5 in a nutshell I»

Metaprogramación en Python

Hace unos días os contaba en la entrada sobre la Codemotion que una de las charlas más interesantes fue la propuesta por Sergio Gil sobre metaprogramación en Ruby en la que se nos introducía esta técnica de programación de forma amena y coloquial. Como os prometí, aquí tenéis la adaptación a Python y en breve tendréis también su versión enfocada en JavaScript.

La charla de Sergio en la Codemotion estaba etiquetada con nivel intermedio no por requerir conocimientos avanzados de Ruby (yo soy un absoluto novato en este lenguaje) sino por precisar de comprender conceptos avanzados de los lenguajes dinámicos. Quizá, lo más importante sea el modelo de datos.

Aunque en realidad la memoria es una secuencia de celdas direccionables que guardan datos o referencias a otras celdas (lenguages como C lo hacen patente), Ruby, JavaScript o Python no se ejecutan directamente sobre nuestra máquina sino sobre un intérprete o máquina virtual que recubre la máquina real. El intérprete ofrece una visión de la memoria «en alto nivel» al programador llena de variables, métodos, objetos, clases, módulos y otras entidades que, junto con la forma en la que tales entidades se relacionan entre sí, forman lo que se llama el modelo de datos del lenguaje. Lo interesante de los lenguajes dinámicos y por lo que se llaman así es porque en tiempo de ejecución, no se limitan a ofrecer una descripción estática del modelo sino que permiten manipularlo. Por ejemplo:

>>> class Simple(object):
...   '''Simply a class'''
...
>>> o = Simple()
>>> dir(o)
['__class__', '__delattr__', '__dict__', '__doc__', '__format__', '__getattribute__', '__hash__', '__init__', '__module__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__']
>>> o.__class__
<class '__main__.Simple'>
>>> o.__doc__
'Simply a class'
>>> o.__init__
<method-wrapper '__init__' of Simple object at 0x7f8a016fabd0>
>>> def f(): print 'Hello!'
...
>>> f
<function f at 0x7f8a016fc668>
>>> o.say_hello = f
>>> o.say_hello()
Hello!
>>> p = Simple()
>>> p.say_hello()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'Simple' object has no attribute 'say_hello'

Fijaos en la interacción anterior, la consola de Python proporciona un entorno de ejecución. En él creamos una clase nueva, Simple, e instanciamos un objeto o, mostramos sus atributos con dir, comprobamos el tipo de algunos de ellos y a continuación creamos una nueva función que asignamos sólo al objeto o. El objeto p no tiene esta función por lo que el intérprete falla al intentar encontrarla.

Ahora que tenemos la idea intuitiva de por qué Python es un lenguaje dinámico, indaguemos en la metaprogramación al fin. Metaprogramación es una palabra que se asocia comunmente a la idea de «programas que escriben programas»; yo prefiero concebir la metaprogramación como una técnica para automatizar la descripción de modelos. ¿Suena muy técnico? Veámoslo con un ejemplo:

Supongamos que queremos una clase que nos permita obtener información de una hipotética compañía mycompany.com Tal sitio web expone información de sus proyectos, empleados, compradores, etc a traves de las páginas /projects, /employees, /customers… Una posible implementación es la siguiente:

class MyCompany(object):
    url = 'mycompany.com'

    def projects(self):
        return self._get('/projects')

    def employees(self):
        return self._get('/employees')

    def customers(self):
        return self._get('/customers')

    def _get(self, url):
        return 'GET ' + self.url + url

Evidentemente, en un entorno real, la función _get() debería hacer algo más que devolver una cadena pero, para nuestros propósitos, nos sirve tal y como está.

La clase MyCompany es bastante clara y expresiva. Si quisiera acceder ahora a /products partiría de uno de los métodos existentes y cambiaría su nombre y la ruta de la URL. Cuando la clase tenga 15 métodos, y a la compañía le de por mover sus páginas a /items/projects, /items/employees, /items/customers… pues tendremos que revisar los 15 métodos. Las desventajas son evidentes pero, ¿podemos hacerlo mejor? Por supuesto:

class MyCompany(object):
    url = 'mycompany.com'

def make_get(path):
    def actual_get(self):
        return 'GET ' + self.url + '/' + path

    return actual_get

for name in ['projects', 'employees', 'customers']:
    setattr(MyCompany, name, make_get(name))

Ahora, añadir un nuevo método es tan sencillo como añadirlo a la lista de métodos, y modificar la funcionalidad es tan fácil como cambiar el método actual_get().

Como yo no tengo una limitación de 45 minutos (como ocurría en la presentación), podemos entrar en detalle: lo único que estamos haciendo es usar setattr() para añadir atributos a un objeto (sí, en Python las clases son objetos; en Python TODO son objetos). El primer parámetro es el objeto al que queremos añadir el atributo, el segundo es el nombre del atributo y el tercero es el valor del atributo. El valor lo produce la función make_get() que devuelve otra función actual_get() con el comportamiento deseado.

Ahora podemos hacer:

>>> company = MyCompany()
>>> company.projects()
'GET mycompany.com/projects'
>>> company.employees()
'GET mycompany.com/employees'
>>> company.customers()
'GET mycompany.com/customers'

De nuevo parafraseando a Sergio en su charla de la Codemotion, al final todo se reduce a:

DRY
D
on’t Repeat Yourself

El segundo listado resulta muy compacto pero adolece de algunos problemas de diseño: demasiado acoplamiento. Si ahora quiero crear otra compañía, pongamos yourcompany.com, ¿qué hago? ¿Otro módulo con casi el mismo código? ¡No! De nuevo ¡DRY!

Vamos a mejorar el diseño:

class HTTP(object):
    @classmethod
    def get(cls, *names):
        def make_get(path):
            def actual_get(self):
                return 'GET ' + self.url + '/' + path

            return actual_get

        for name in names:
            setattr(cls, name, make_get(name))

class MyCompany(HTTP):
    url = 'mycompany.com'
MyCompany.get('projects', 'employees', 'customers')

class YourCompany(HTTP):
    url = 'yourcompany.com'
YourCompany.get('projects', 'employees')

Ahora podemos coger la clase HTTP y meterla en un módulo aparte (por ejemplo http.py). Nuestras compañías pueden estar en otro módulo (tal vez companies.py) e importar y heredar de HTTP para a continuación llamar al método de clase get() que creará los métodos indicados.

El método de clase get() tiene algo de chicha: está decorado con el decorador classmethod que hace que, al ser llamado, reciba como primer parámetro la clase donde ha sido definido. Luego recibe una lista con los argumentos pasados a la función, en este caso, los nombres de los métodos. Por cada uno de ellos, crea una nueva función de la forma que vimos anteriormente.

El siguiente listado prueba las clases MyCompany y YourCompany:

>>> mine = MyCompany()
>>> mine.projects()
'GET mycompany.com/projects'
>>> mine.customers()
'GET mycompany.com/customers'
>>> yours = YourCompany()
>>> yours.projects()
'GET yourcompany.com/projects'
>>> yours.customers()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'YourCompany' object has no attribute 'customers'

Comprender el modelo de datos de Python resulta de vital importancia para explotar la metaprogramación, baste por el momento comprender cómo Python recupera un attributo de un objeto. Cuando en Python escribimos objeto.atributo, internamente se llama a la función __getattribute__ con el objeto y el nombre del atributo como parámetros. La implementación por defecto mira (no preguntéis cómo, que no acabamos nunca) en el objeto por un atributo con ese nombre y si no lo encuentra trata de encontrarlo en la clase del objeto. Si ahí tampoco está, mira en las superclases y de ahí hacia arriba por la jerarquía de clases. En caso de no encontrarlo se llama al método __getattr__ de la instancia el cual, por defecto, lanza una excepción del tipo AttributeError.

¿Y qué queremos decir con esto? Pues que podemos explotar más la metaprogramación hasta el punto de ni siquiera tener que crear los métodos de la clase explícitamente. La generación en sí puede ser dinámica, creados conforme se necesitan. Veamos cómo:

class HTTP(object):
    @classmethod
    def get(cls, *names):
        def make_get(path):
            def actual_get(self):
                return 'GET ' + self.url + '/' + path

            return actual_get

        for name in names:
            setattr(cls, name, make_get(name))

    def __getattr__(self, name):
        HTTP.get(name)
        return getattr(self, name)

class MyCompany(HTTP):
    url = 'mycompany.com'
MyCompany.get('projects', 'employees', 'customers')

class YourCompany(HTTP):
    url = 'yourcompany.com'
YourCompany.get('projects', 'employees')

Hemos reescrito __getattr__() para que en caso de que el método no exista, le pidamos a la clase que lo genere por nosotros. Luego lo recuperamos y devolvemos.

La misma interacción que antes fallaba con la excepción AttributeError ahora no fracasará:

>>> mine = MyCompany()
>>> mine.projects()
'GET mycompany.com/projects'
>>> mine.customers()
'GET mycompany.com/customers'
>>> yours = YourCompany()
>>> yours.projects()
'GET yourcompany.com/projects'
>>> yours.customers()
'GET yourcompany.com/customers'

¿Bastante impresionante, no? Ahora bien, ¿cuándo debemos usar metaprogramación? La respuesta no es sencilla pero yo tiraría por «siempre que sea expresivo y la alternativa sea peor» o quizá «siempre que se ajuste a la naturaleza del problema» La metaprogramación tiene mucho que ver con el diseño de interfaces, la interfaz de una utilidad tiene que ser agradable para sus usuarios pero mantenerla no puede resultar en una pesadilla para el programador: debemos llegar a un acuerdo entre usabilidad y mantenimiento.

La metaprogramación no es más que programación así que no pierdas las buenas costumbres. Documenta tus métodos y explícate qué estás haciendo en todo momento. Así, cuando recuperes tu proyecto 3 meses más tarde no invertiras horas y horas tratando de ver qué escribiste.

Vale la pena terminar con una comparación con Ruby. ¿Es cómodo metaprogramar en Python? En mi opinión: no tanto como en Ruby. Ruby está más orientado a manipular fragmentos de código, el hecho de que lo que existe entre un bloque do – end sea un dato simplifica considerablemente las cosas. En Python, el modelo de datos es poco regular y difícil con muchos casos y excepciones. Además, los decoradores, el anidamientos de funciones, los nombres especiales de función y el modelo de acceso a los atributos contribuyen a disminuir la claridad y limpieza de la implementación.

En la próxima entrada, exploraremos exactamente el mismo ejemplo pero en JavaScript. Será una entrada mucho más corta dado que no será necesaria la introducción ni las explicaciones previas, pero os aseguro que volverá a ser útil e interesante.

Tenéis todo el código de los ejemplos en:
https://github.com/lodr/metaprogramming

Pretty-Print: Imprimiento de forma «bonita» datos complejos en python

Hoy en el trabajo, tenía que cargar a mano un diccionario de Python que, en su forma canónica, ocupaba un churro de 7000 caracteres, que se dice pronto.

Buscando cosas que no tenían nada que ver, descubro el módulo pprint que seguro que, a la hora de depurar, os resuelve la vida a más de uno. Se trata de un módulo que aúna funcionalidad para representar tipos de datos arbitrariamente complejos de manera «bonita» (el módulo se llama pretty-print).

La funcionalidad más básica la proporciona la función pprint() del módulo. La función toma los siguientes parámetros:

  • object, el objeto que quieres imprimir.
  • stream, opcional, dónde lo quieres imprimir. Por defecto en la salida estándar.
  • indent, opcional, cuántas sangrías (indentaciones) por nivel. Por defecto 1.
  • depth, opcional, nivel máximo a partir del cual los objetos más profundos se reemplazan por ‘…’. Por defecto, desactivado.
  • width, opcional, anchura máxima antes de romper una línea. Por defecto 80.

Os dejo una comparación para que veais a qué me refiero:

import pprint

a = {'nombre completo':{'nombre':'Salvador', 'apellidos':'de la Puente'}, 'edad':25, 'puestos':[('programador .NET',2006),('administrador de sistemas', 2008),('investigador', 2010)]}
print a
pprint.pprint(a)

Y su salida:

>>> print a
{'edad': 25, 'nombre completo': {'apellidos': 'de la Puente', 'nombre': 'Salvador'}, 'puestos': [('programador .NET', 2006), ('administrador de sistemas', 2008), ('investigador', 2010)]}
>>> pprint.pprint(a)
{'edad': 25,
 'nombre completo': {'apellidos': 'de la Puente', 'nombre': 'Salvador'},
 'puestos': [('programador .NET', 2006),
             ('administrador de sistemas', 2008),
             ('investigador', 2010)]}

¿Veis qué útil?

Mi primera entrevista con Google

Bueno, el pasado Jueves pasé mi primera entrevista con Google y el Viernes me dijeron que la había hecho satisfactoriamente y que a la semana siguiente me pasarían otra. ¡Algo es algo!

Fueron unos 45-50min de entrevista en Inglés con uno de los ingenieros de Google. Para mi el tiempo se me hizo eterno y entre los nervios, el calor, el teléfono y mi dicción inglesa, me dio la impresión de que lo había hecho fatal aunque reconocía que era fácil. De hecho la sensación era «avergonzado de lo mal que lo había hecho para lo fácil que era». Afortunadamente no fue así.

La entrevista se dividión en tres partes: una parte de teoría y dos problemas. Aunque me habían pedido Java o C++, me pude defender perfectamente en Python y a continuación os cuento un poco la entrevista, cómo respondí y cómo me hubiera gustado responder…

Seguir leyendo «Mi primera entrevista con Google»

Preguntas de entrevista de Google (con respuestas) II

Seguimos con otras diez preguntas de entrevista de Google tras la primera entrega de esta serie. Insisto en que si conoceis mejores respuestas o soluciones las pongais en los comentarios.

#11 ¿Cómo se pasan las cookies en el protocolo HTTP?

Bueno, esta me parece bastante fácil. Las cookies, que no son más que pares clave=valor se pasan como texto plano en las cabeceras de cualquier petición o respuesta HTTP. Cuando el explorador realiza una petición, pasa las cookies tal cual se las mandó el servidor simulando así una suerte de «estado persistente».

Puede encontrarse información sobre el protocolo HTTP y las cookies en particular en Wikipedia.

#12 Escribe una expresión regular que acepte direcciones de correo

Divide y vencerás: la estructura de un correo electrónico es [usuario]@[host] así que ya podemos hacer una versión inicial de la expresión regular:

()@()

Tenemos que rellenar esos corchetes. Vamos con el host que tiene una forma como [subdominio].[dominio]. Ese punto final es optativo (se supone que todos los FQDN lo llevan en su normalización) así que la expresión regular para el host será algo como:

([a-zA-Z0-9][a-zA-Z0-9-]*\.)+[a-zA-Z]+(\.)?

Es más o menos correcto. El primer grupo entre corchetes obliga a que el nombre del dominio empiece por un carácter alfanumérico. El segundo acepta el resto de caracteres (alfanuméricos y el guión) y hace terminar la cadena en punto. Todo esto podemos repetirlo indefinidamente (en realidad un nombre de dominio sólo puede tener hasta 253 caracteres). Debemos terminar con una extensión que representa un dominio de primer nivel formado por caracteres alfabéticos (al menos, uno) y el punto optativo final. Los puntos están precedidos de la barra para que no sean considerados caracteres especiales.

Ahora, el nombre de usuario depende. Pongamos algunas reglas. Supongamos que solo permitimos caracteres alfanuméricos, guiones bajos, puntos y símbolos de sumar y restar y que debe comenzar por un carácter alfanumérico o guión bajo . Su longitud mínima será de 1 caracter. Tenemos pues:

[_a-zA-Z0-9][_a-zA-Z0-9-+.]*

Ahora, combinando las tres, tenemos:

([_a-zA-Z0-9][_a-zA-Z0-9-+.]*)@(([a-zA-Z0-9][a-zA-Z0-9-]*\.)+[a-zA-Z]+(\.)?)

Y listo, ese churro valida direcciones email.

Os invito a probarlo en RegexPal.

#13 Escribe una función f(a, b) que toma dos cadenas de caracteres y devuelve otra sólo con los caracteres comunes en el orden en el que aparecen en a. Escribe una versión que ejecute en orden N cuadrado y otra en orden N.

Vamos a suponer caracteres alfabeticos y en minúscula:

La primera solución que se nos puede ocurrir es algo como esto (en Python).

def f(a,b):
  r = ''
  for c in a:
    if c in b and c not in r:
    r += c

  return r

Esta solución es N cuadrado pues el hecho de comprobar si el caracter c está o no en b supone un recorrido por los caracteres de b. Así que tenemos un bucle de longitud(b) dentro de otro de longitud(a) luego longitud(a)*longitud(b) pertenece a O(N^2). Esto es notación O que supongo que a cualquier ingeniero le sonará de algo.

La solución N es también muy fácil. Para ello necesitamos una función auxiliar que haga a=0, b=1, c=2…

def alpha_to_index(c):
  return ord(c)-ord('a')

def f(a,b):
  l = [0]*26
  for c in b:
    i = alpha_to_index(c)
    if not l[i]:
      l[i] = 1 # Indica aparición en b

  r = ""
  for c in a:
    i = alpha_to_index(c)
    if l[i] == 1:
      r += c
      l[i] = 2 # Indica ya añadida al resultado

  return r

Este algoritmo se ejecuta en longitud(a)+longitud(b) que pertenece a O(n) Para quitar las restricciones de minúscula y caracteres alfabéticos, en vez de un array se usa un hashmap (un diccionario en Python) para albergar el estado de los caracteres.

En breve dedicaré un post a la notación O y a cómo calcular el coste de un algoritmo.

#14 Te dan un código fuente que se rompe en cada ejecución. Tras ejecutarlo 10 veces en un depurador te das cuenta de que nunca se rompe dos veces por el mismo sitio. El código fuente sólo usa un hilo y la biblioteca estándar de C. ¿Qué errores de programación podrían estar causando los problemas? ¿Cómo podrías probar cada uno?

A mi se me ocurre que las causas pueden ser principalmente dos:

  1. Desbordamientos (y son un caso particular del segundo)
  2. Comportamientos indefinidos

Para probarlos cogería un lista de comportamientos indefinidos y probaría que no se están ralizando asunciones erroneas. Para los desbordamientos comprobaría los casos típicos (desbordamiento de array, de paso de parámetro, copia de arrays…).

#15 Explica cómo funciona el control de congestión en el protocolo TCP

La verdad es que este no es mi fuerte así que si alguien se sabe otra forma más sencilla de explicarlo, estaré encantdo de rectificar la respuesta. Entre lo que recuerdo de redes y lo que he sacado de la Wikipedia, la explicación se parece a esto:

El típico (porque hay varios) consiste en variar el tamaño de la llamada ventana de congestión mediante un algoritmo llamado Slow-Start. La necesidad del protocolo surge porque los extremos de una conexión TCP no tienen manera de saber a priori la calidad la red. En principio, no pueden saber el tamaño máximo del datgrama (los datos enviados en TCP)  que causaría la mayor tasa de transferencia sin desbordar la capacidad de la ruta seleccionada.

Encontrar este óptimo es tarea del algoritmo de control de congestión. Para ello, el emisor cuenta con una ventana de congestion que especifica cuántos datagramas enviará de golpe. La ventana comienza al tamaño máximo de un datagrama y cada vez que se acusa un recibo se dobla. Eventualmente se superará un umbral llamado sstresh que hará que la ventana aumente linealmente. En el momento en que la cantidad de datagramas satura la red se comienzan a perder paquetes y se produce una de las siguientes situaciones:

  • Si se detecta un timeout, la ventana se reestablece al tamaño máximo de un datagrama.
  • Si en vez de un timeout, se detectan tres acuses iguales, la ventana se reduce a la mitad del mínimo entre la ventana de congestión y la ventana de recepción (el tamaño máximo del datagrama que el nodo está dispuesto a aceptar por vez).

#16 En Java, ¿cuál es la diferencia entre final, finally y finalize?

Yo me sabía dos (final y finally):

  • final es un modificador de tipo. En variables indica que, una vez inicializada en el constructos, no puede volver a ser modificada. En clases indica que no se puede heredar de ella.
  • finally es una clusula del bloque try / catch que indica qué se debe hacer finalmente, antes de continuar la ejecución
  • finalize es el método al que invoca el recolector de basura al ir a destruir un objeto

Fuente: http://www.janeg.ca/scjp/gc/finalize.html

#17 ¿Qué es la programación multihilo? ¿Qué es un deadlock?

La programación multihilo hace referencia a distintas líneas de ejecución dentro de un programa. Cada línea de ejecución es un subprograma que mantiene su propio estado y es independiente de los demás. La comunicación se realiza mediante el traspaso de mensajes o a través de recursos compartidos. El acceso a estos recursos compartidos promueve toda una nueva serie de problemas relaccionados con el acceso simultáneo a los mísmos.

Un deadlock o interbloqueo es un problema de sincronización que se da cuando el hilo A se encuentra esperando un recurso del hilo B y viceversa. He encontrado un ejemplo muy claro de interbloqueo en el blog de JASoft.org

En él se nos invita a pensar en un proceso que transfiere dinero entre dos cuentas. Obviamente el proceso trata de obtener un acceso exclusivo a cada cuenta al comienzo de su ejecución por si ya hay otro proceso manipulando dicha cuenta. Si una cuenta está en uso, el hilo que la requiere esperará (haciendo nada) hasta que sea liberada.

Ahora supongamos que se producen dos transferencias en sentidos contrarios. Ambos procedimientos comenzarán por bloquear sus cuentas origen pero al tratar de bloquear las cuentas destino se encontraran con que tal cuenta ya se encuentra bloqueada. Y lo que es peor, de esta situación no saldrán nunca.

Fuente: http://geeks.ms/blogs/jalarcon/archive/2011/04/29/191-qu-233-es-un-deadlock-o-interbloqueo.aspx

#18 Escribe una función toExcel(v) que coja el valor de una columna excel (A, B, C, …, AA, AB, …, AAA) y devuelva su valor entero (A=1, B=2, C=3, …, AA=27…)

Este ejercicio es muy interesante pero aun lo es más el contrario. Para abordarlo, vamosa reducir al conjunto de letras a A, B y C. Ahora tenemos que A=1, B=2 y C=3 y la secuencia es A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC…

Si recordais el post con el que (casi) abrimos el blog, relacionado con las bases de numeración y con el hecho de que la suma de 1 y 1 sea 10 en binario, vereis que esto se acerca mucho a contar en base 3. El problema es que los dígitos en base 3 son 0, 1 y 2; y no 1, 2 y 3 (o A, B y C) como ocurre en este caso. Resulta que en este problema no contamos con ningún dígito que represente el 0 pero sí con uno que representa la base.

Bien, vayamos primero con el problema contrario. Transformemos, por ejmplo, 12 en CC.

El número 12, escrito en base tres tiene la siguiente pinta: 110 dado que puede expresarse como 1*3^2 + 1*3^1 + 0*3^0 Ahora bien, como no contamos con ningún símbolo para representar el 0 pero sí par representar el 3, vamos a ajustar 110 tratando de quitar los 0s. Podemos quitar una «decena» y añadir 3 unidades lo que resulta en 103 cuya descomposición sería 1*3^2 + 0*3^1 + 3*3^0 que sigue siendo 12. Ahora tenemos un 0 más así que quitamos 1 «centena» y ponermos 3 «decenas» quedando 033. Como los 0s a la izquierda no importan pues ya hemos terminado y su descomposición es 0*3^2 + 3*3^1 + 3*3^0 que sigue siendo 12. Ahora reemplazamos cada dígito por su letra quedando CC.

De aquí puede inferirse fácilmente el algoritmo de transformación que nos piden y puede resumirse en dos sencillos pasos:

  1. Reemplazar cada letra por el dígito correspondiente (A=1, B=2, C=3…)
  2. Interpretar en base 3 (o, generalmente, en base la longitud del conjunto de símbolos)
def char_to_index(c):
  return ord(c) - ord('A') + 1

def toExcel(v):
  l = len(v)
  r = 0
  for i in range(l):
    c = v[i]
    r += char_to_index(c) * (26**(l-i))

  return r

El caso contrario requiere el estudio de un caso más. Pongamos que queremos transformar 9 en BC. 9 en base tres es 100. Empezamos quitando 0 de más a la derecha: quitamos 1 «decena» y añadimos 3 unidades resultando en 1-13 cuya descomposición sería 1*3^2 – 1*3^1 + 3*3^0 que sigue siendo 9. Como tampoco tenemos símbolos para números negativos quitamos 1 «centena» y añadimos 3 «decenas» quedando 023 cuya descomposición es 0*3^2 + 2*3^1 + 3*3^0 que sigue siendo 9. Ahora reemplazamos cada dígito por su letra lo que nos lleva a BC.

El algoritmo supone modificar ligeramente el clásico de las divisiones y restos utilizado para transformar a una base dada (comprobado que funciona):

def char_to_index(c):
  return ord(c) - ord('A') + 1

def index_to_char(i):
  if not i:
    return ''

  return chr(ord('A') + i - 1)

def fromExcel(n):
  res = []
  d = n
  fixmode = False # Indica que estamos en modo ajuste (restar 1 al siguiente resto y añadir 26 al actual)
  while d >= 26:
    r = d%26

    # Si estamos ajustando los restos, asumimos que ya hemos añadido 3 al anterior y le quitamos uno a este
    if fixmode:
      r -= 1

    # Si es (o queda) negativo, le sumamos veintiseis y pasamos (o conservamos) el modo de ajuste
    if r<=0:
      r += 26
      fixmode = True

    # Si no lo es, dejamos el modo de ajuste
    else:
      fixmode = False

    res.insert(0, r)

    d = int(d/26)

  res.insert(0, d)
  return ''.join(map(index_to_char, res))

#19 Si tienes 1 millon de enteros. ¿Cómo los ordenarías eficientemente? Modifica un algoritmo conocido para hacerlo.

Dedicaremos en breve otro post a los algoritmos de ordenación. Baste decir que para tal cantidad de datos se prefieren estrategias «divide y vencerás». Primeramente el milllón de datos puede separarse en tramos (digamos de 10000 ó 100000) enteros y ordenarse separadamente mediante qsort. Luego pueden mezclarse con merge sort.

También se podría haber aplicado merge sort directamente.

Ojo, si nos dan límites de memoria entonces tendremos que ir poco a poco. Leer unos cuantos, aplicar una técnica anterior, escribir el resultados; leer otros pocos, volver a aplicar una técnica y volver a escribir el resultado… Al final, habrá que mezclar los archivos ordenados.

Fuente: teneis aquí una solución por Guido van Rossum con código en Python 3.0

#20 Tienes un flujo continuo e infinito de consultas (las consultas de Google que la gente introduce). Describe como podrías tomar una buena estimación de 1000 muestras de este conjunto inagotable de datos.

Esta pregunta no la entiendo y, sencillamente, preguntaría por más información. ¿Qué característica tienen que cumplir estas mil muestras? Supongo que se referirá a las 1000 consultas más solicitadas. Para ello se puede usar una estructura de datos (que acabo de descubrir) llamada splay-tree o árbol biselado que no es otra cosa que un árbol binario con la propiedad de que los elementos más recientemente accedidos pueden recuperarse más rápidamente.

Esta solución del árbol biselado requiere alguna normalización que convierta las consultas en números. Se podría utilizar alguna función hash.

Si esta no es la característica que deben cumplir las muestras, entonces la solución cambia. Por ejemplo si tiene que ser aleatoria se puede dividir el conjunto de consultas en 1000 segmentos y seleccionar un elemento al azar de cada uno.

EDIT: Según un comentario (con el que estoy de acuerdo) de Jisakiel en Facebook, la muestra debería cumplir normalidad. Ahora bien, estamos en las mismas, normalidad sí pero ¿respecto de qué? Si nos asaltan con esta pregunta, es nuestra obligación fusilar al entrevistador con aclaraciones hast que sepamos exactamente las propiedades de la muestra.

Django 1.3 en «cero coma» II

La primera entrega de este tutorial sirvió para introducir en 10 pasos algunos aspectos interesantes de Django 1.3. en esta segunda parte vamos a tratar de ser más caseros, programando un poco más pero utilizando correctamente el framework. Aquí tenéis un resumen:

  1. Añadiremos un propietario al modelo
  2. Mejoraremos la administración de posts
  3. Implementaremos un sistema de comentarios
  4. Retocaremos el administrador para gestionar los post y comentarios
  5. Implementaremos un formulario de búsqueda muy sencillo

Seguir leyendo «Django 1.3 en «cero coma» II»

Django 1.3 en «cero coma» I

Puedes encontrar una versión actualizada de este tutorial en ’Django 1.5 in a nutshell I‘ para Django 1.5

Esta semana son las I Jornadas del Software Libre de la Facultad de Informática de la UCM y me toca dar un par de charlas. Una sobre lenguajes y paradigmas de programación y otra sobre framworks de programación de aplicaciones web. En especial, la charla tratará sobre Ruby on Rails y Django. De la de Rails se encargará mi compañero del Grupo de Usuarios de Línux de la Complutense y Vicepresidente de KDE España, Rafael Fernández y de la de Django, un humilde servidor.

Resulta que Rails tiene un tutorial para desarrollar una aplicación rápida de blog que presenta las principales características del framework y aunque el tutorial de Django es excelente y presenta muchas características del software, yo necesito algo más rápido, que me de tiempo a codificar en una hora que es lo que dura mi exposición.

Así que este post es eso, un tutorial rápido de Django donde desarrollar un blog muy sencillo y parecido al del tutorial de Rails, presentando las características principales del lenguaje pudiendo desarrollarse en menos de una hora. Espero que lo disfruteis.

Seguir leyendo «Django 1.3 en «cero coma» I»