{ Category Archives }

Lenguajes de Programación

Comparando utilidades de compresión

Hoy ha tocado colocar un poco el disco duro, y en estas que me da por mirar cuánto ocupa el directorio

.thunderbird/

donde guardo todo el correo que recibo (desde hace años, incluído spam). 1.8G suman todos los correos. Casi nada, teniendo en cuenta que es texto plano.

Buceando en ese directorio llego al fichero

Inbox

de una de mis cuentas de correo. Todo lo que almacena está en formato mbox, que es lo que habitualmente usan los lectores de correo (o MUAs, Mail User Agent). Los MTAs (Mail Transport Agent) suelen usar el formato Maildir ya que evita el cuello de botella que impone mbox ante la concurrencia.

El caso es que me da por mirar a ver qué tal comprimen los diferentes algoritmos de compresión que tengo en Linux, que son básicamente cuatro: bzip2, LZMA (7zip y versiones nuevas del tar), el tradicional Zip (herramientas zip y gzip) y RAR.

Me he centrado sólo en el ratio de compresión de cada programa, no me he preocupado por cuánto tardan en comprimir, ni cuánto se tarda en listar el contenido de un fichero, o en descomprimir un sólo fichero. De hecho es que no he diferenciado entre formatos que comprimen y archivan a la vez, y los que sólo comprimen (p.ej.

bzip2

). He comprimido un sólo fichero, y era un fichero de texto (en formato

mbox

).

Los resultados para un solo fichero

mbox

de 118M:

Programa Algoritmo Tamaño ¿Libre?
gzip -9 LZ77 modificado 65M Sí
zip -v9 LZ77 modificado 65M Sí
bzip2 Burrous-Wheeler/Huffman 63M Sí
rar LZSS 56M No
7-zip LZMA 54M Sí
tar –lzma LZMA 54M Sí

Con ¿Libre? me refiero a si yo conozco implementaciones libres del algoritmo tanto para comprimir como para descomprimir.

El LZ77 modificado también se conoce como DEFLATE.

Se concluye lo que más o menos ya habíamos observado a base bajarnos discos:

LZMA

es el que más comprime (y es libre),

RAR

no se queda muy lejos (pero no es libre, aunque es bastante multiplataforma),

bzip2

mejora un poco lo del tradicional

Zip

, pero éstos dos ya van teniendo que jubilarse.

Las únicas ventajas que tienen

zip/gzip/bzip2

son a) que aparentemente tardan menos en comprimir (lógico) y b) que están mucho más difundidos: es difícil encontrar un sistema que no tenga alguno de los tres.

LZMA

en cambio, es más difícil de encontrar.

Update (2009-02-17): Hoy en barrapunto.com han publicado Comparación entre diferentes algoritmos de compresión en Linux . Una noticia que enlaza a tres sitios donde han hecho comparativas similares, pero mucho más extensas:

2008 11 09

Algoritmia
Estructuras de datos
Linux
Shell scripting

Comments (0)

Permalink

Charles Simonyi

Hace un par de semanas leía un artículo traducido al español de Joel Spolsky. Trataba sobre la notación Húngara, un estilo de codificación muy útil si es bien entendida y bien utilizada, cosa que no suele ocurrir (por eso a nivel popular se le tiene tanto rechazo).

Para saber más acerca de la notación húngara recomiendo leer el artículo de Spolsky: Haciendo que el código defectuoso se vea defectuoso.

En ese mismo artículo se menciona que Simonyi era un programador húngaro que inicialmente trabajaba en Xerox Parc en un procesador de textos llamado Bravo, y se acabó pasando a Microsoft para trabajar en el equipo del Word, que es donde inventó la notación húngara con la finalidad de saber de qué clase es cada variable (no del tipo).

Ahora estaba leyendo que el notas va a viajar por segunda vez a la Estación Espacial Internacional en primavera, así que pareceser que con el Word, pese a Clippo, no le fue nada mal.

2008 10 12

Lenguajes de Programación
Personajes

Comments (4)

Permalink

Recorrer un árbol de directorios en Python

Ya me picaba el gusanillo tras tanto examen y tanta gaita, así que esta vez ha tocado hacer una función que recorra los ficheros del directorio actual y de todos sus subdirectorios. Se basa en una función que mediante las funciones

os.stat()

para saber el tipo de fichero,

os.listdir()

para sacar el contenido de un directorio y una cola para guardar los ficheros que quedan por analizar.

Importamos las funciones necesarias de sus respectivos módulos:

from os import stat,listdir
from os.path import join
from stat import S_ISDIR,S_ISCHR,S_ISBLK,S_ISREG,S_ISFIFO,S_ISLNK,S_ISSOCK

Todas las

stat.S_ISxx()

se pueden sacar también de

os.stat.isXX()

, según la documentación del módulo stat –donde se puede encontrar una función similar a la implementada, pero con recursividad en vez de usar una cola.

Ahora la función (siento que la identación esté hecha con ___, pero es que el editor de WordPress no está hecho para meter código):

def walktree(origen):
____ficheros=[(None,origen),]

cargar la ruta inicial. El primer elemento de la tupla no sería necesario, no habría por qué usar una tupla. La estoy usando para un uso posterior que le quiero dar a esta función de recorrido de directorios.

____while ficheros:

mientras queden ficheros

____ ____ (parent,file)=ficheros.pop()

sacamos el siguiente fichero de la lista (ignorad

parent

)

____ ____print “Fichero: %s”%(file)
____ ____tipo=stat(file).st_mode

obtenemos mediante

os.stat()

el modo del fichero (lo que incluye los permisos, pero también el tipo). Según de qué tipo sea imprimiremos una cosa u otra en pantalla:

____ ____ if S_ISDIR(tipo):

Es un directorio: además de decir que es un directorio…

____ ____ ____ print “Directory”
____ ____ ____ for nuevo_fichero in listdir(file):

…debemos leer sus contenidos con

os.listdir()

e incluirlos en la lista ficheros. Nótese que

listdir()

no devuelve ni el directorio

‘.’

, ni

‘..’

, lo que nos evita ciclos que harían que el algoritmo no acabara nunca hasta agotar la memoria

____ ____ ____ ____ ficheros.insert(0,
____ ____ ____ ____ ____ (None,join(file,nuevo_fichero)))
____ ____ elif S_ISCHR(tipo):

y vamos comprobando otros tipos

____ ____ ____ print “Char. device”
____ ____ elif S_ISBLK(tipo):
____ ____ ____ print “Block device”
____ ____ elif S_ISREG(tipo):
____ ____ ____ print “Regular file”
____ ____ elif S_ISFIFO(tipo):
____ ____ ____ print “Named pipe”
____ ____ elif S_ISLNK(tipo):
____ ____ ____ print “Soft link”
____ ____ elif S_ISSOCK(tipo):
____ ____ ____ print “Socket”
if __name__==’__main__’:
____ walktree(‘.’)

2008 09 19

Python
Sistemas de ficheros

Comments (0)

Permalink

Pilas y colas en Python

Las listas son un tipo de objeto mutable de Python. Por mutable, en Python se entiende que el objeto es modificable una vez definido, por ejemplo:

>>> a=[1,2]

(definimos la lista a con dos elementos)

>>> a.append(3)

(añadimos otro elemento)

>>> a
[1, 2, 3]

A diferencia de las tuplas, que no son modificables:

>>> b=(1,2)

(definimos la tupla b, que se quedará así por los siglos de los siglos…)

>>> b=None

(…o hasta que pase el recolector de basura)

Las listas por ser mutables tienen definidas unas operaciones sobre ellas de las que las tuplas carecen, por ejemplo el método append(<elemento>) que se ha visto antes, o por ejemplo los siguientes métodos:

>>> c=["a","b","c"]
>>> c
['a', 'b', 'c']
>>> c.insert(0,”d”)
>>> c
['d', 'a', 'b', 'c']
>>> c.insert(2,”e”)
>>> c
['d', 'a', 'e', 'b', 'c']
>>> c.pop()
‘c’
>>> c
['d', 'a', 'e', 'b']
>>>

Como se puede apreciar pop() toma el último elemento (, o c[len(c)-1], como se prefiera), lo saca de la lista (la lista se queda sin ese valor) y nos lo devuelve. Junto con append() es lo justo para crear una pila:

>>> pila=[]

(creamos la pila, vacía)

>>> pila.pop()

(sacamos datos de una pila vacía, y nos dan una excepción)

Traceback (most recent call last):
File “<stdin>”, line 1, in ?
IndexError: pop from empty list
>>> pila.append(1)

(añadimos datos a la pila)

>>> pila.append(2)
>>> pila.append(3)
>>> pila
[1, 2, 3]
>>> while pila:
… print “Ultimo elemento de la pila: %d (pila: %s)” % (pila.pop(),pila)…
Ultimo elemento de la pila: 3 (pila: [1, 2])
Ultimo elemento de la pila: 2 (pila: [1])
Ultimo elemento de la pila: 1 (pila: [])
>>>

El otro método utilizado era insert(<posición>,<elemento>), que como creo que cabe esperar realiza este comportamiento:

>>> lista=[]

(creamos la lista)

>>> lista.insert(1,”a”)

(insertamos en la posición 1, pero como está vacía realmente queda en la posición lista[0])

>>> lista
['a']
>>> lista.insert(5,”a”)

(insertamos en la posición 5, pero como está vacía realmente queda en la posición lista[1])

>>> lista
['a', 'a']
>>> lista.insert(0,”b”)

(insertamos al principio)

>>> lista
['b', 'a', 'a']
>>> lista.insert(-1,”c”)

(insertamos justo antes de la última posición)

>>> lista
['b', 'a', 'c', 'a']
>>> lista.insert(-2,”d”)

(insertamos en la antepenúltima posición)

>>> lista
['b', 'a', 'd', 'c', 'a']
>>>

¿Y para insertar en la última posición? lista.append(‘u’), mismamente:

>>> lista.append(‘u’)
>>> lista
['b', 'a', 'd', 'c', 'a', 'u']
>>>

Ahora ya crear una cola es coser y cantar, a base de insert(0,<elemento>) y pop():

>>> cola=[]

(crear la cola)

>>> cola.pop()

(sacar de una cola vacía nos da una excepción

IndexError

, como en la pila)

Traceback (most recent call last):
File “<stdin>”, line 1, in ?
IndexError: pop from empty list
>>> cola.insert(0,”1″) (

introducimos datos)

>>> cola.insert(0,”2″)
>>> cola.insert(0,”3″)
>>> cola
['3', '2', '1']
>>> while cola:

(y vamos sacando…)

… print “Cabeza de la cola: %c (cola: %s)” % (cola.pop(),cola)
…
Cabeza de la cola: 1 (cola: ['3', '2'])
Cabeza de la cola: 2 (cola: ['3'])
Cabeza de la cola: 3 (cola: [])
>>>

¿Cuánto tiempo nos podemos ahorrar por programarlo en Python en vez de en C?

Aunque también es mucho más ineficiente ejecutarlo en Python que en C, pero normalmente es preferible ahorrar tiempo de programación que tiempo de ejecución: mi tiempo es importante, el del microprocesador no tanto.

2008 08 15

Estructuras de datos
Python

Comments (0)

Permalink

Parsear Makefiles (en Python)

Necesitaba parsear ficheros Makefile desde Python, y buscando… me cuesta encontrar cosas.

  • Makefile::Parser, en Perl, parsea Makefiles, pero no soporta toda la gramática, y está en pre-alpha. Además es en Perl y no en Python, y para prototipar no hay problema, pero para sacar algo más sólido me deja un poco “descubierto”.
  • Makefile::Parser::GmakeDB ejecuta make, y toma la base de datos que genera este comando (primera noticia de que hace esto, aunque si le quitamos los comentarios la base de datos es como un Makefile, pero ampliado). Parece estar más maduro que el anterior, aunque eso de requerir de un comando externo me sigue pareciendo un poco cojo.
  • Makefile::AST parte también del análisis de tal base de datos para generar ASTs (Abstract Syntax Trees).
  • Y Makefile::DOM genera árboles DOM a partir del fichero entero (cabía esperarse ésto, ¿no?).

¿Y qué tal si nos hacemos con la gramática y luego generamos un parser vía bison (o similares)? La gramática de los Makefiles no la encuentro, y eso que he visto varios mensajes en diferentes listas de correo solicitando el BNF de la gramática, así que tocará ir abriendo boca con un subconjunto de la gramática, y luego ya se irá ampliando si es preciso (gracias al manual de GNU Make).

Generadores de parsers en Python ando buscando, así que ya escribiré qué es lo que he encontrado.

Y por último mencionar SCons, que sigue la misma idea de make, pero está hecho sobre Python y usa la sintaxis de Python (ejemplos). En mi opinión, es poco práctico usar esa sintaxis para un Makefile (¿exceso de costumbre con los makes? ¿falta de bregaje con makes complicados?), pero desde luego le da la potencia de Python al script de compilación.

2008 08 12

Python

Comments (1)

Permalink

« Older posts
Newer posts »