Facundo Batista: Satélites argentinos

   Publicado:


Estos días fue lanzado exitosamente el tercer nanosatélite argentino, "Tita" (llamado así en honor a Tita Merello).

Se llaman "nanosatélites" porque, justamente, son mucho más chicos (y baratos) que los satélites "tradicionales". En particular, Tita pesa unos 25 kilos, está equipado con tres antenas y lleva una cámara para tomar fotos y videos en alta definición.

El satélite Tita, siendo instalado en el lanzador

Lo desarrolló la empresa argentina Satellogic, pero no lo lanzamos nosotros al espacio (todavía no tenemos esa capacidad), sino que fue lanzado desde la ciudad rusa de Yasny. Su objetivo es tomar imágenes durante tres años, en colaboración con otros nanosatélites, los ya lanzados Capitán Beto (llamado así obviamente en referencia a la canción de Spinetta) y Manolito (por el personaje de Mafalda), y a otros 15 satélites que Satellogic planea lanzar durante el próximo año.

Pero Tita es diferente a los dos anteriores, que pesaban alrededor de dos kilos. También es un prototipo, y usa las mismas estrategias de diseño y fabricación con componentes de uso comercial (resortes de ferretería, electrónica de teléfonos celulares y computadoras personales), pero este permite tomar imágenes y videos de dos metros de resolución. Esencialmente, la gente de Satellogic está haciendo lo mismo que hace un satélite convencional, pero a un precio entre cien y mil veces menor.

En este video bastante interesante podemos ver a Lino Barañao (Ministro de Ciencia y Tecnología) y Emiliano Kargieman (CEO de Satellogic), contándonos un poco todo esto (y de paso se ven pasos de la construcción, y las oficinas, ¡donde se ve bastante gente de PyAr trabajando!).



Como detalle final, les dejo este audio de Adrián Paenza hablando sobre los satélites (en general) en el programa La Mañana de Victor Hugo Morales.

Hernán Grecco: PyVISA 1.5 is out

   Publicado: PyVISA is a Python wrapper for the VISA library that enables controlling all kinds of measurement equipment through GPIB, RS232, USB and Ethernet. It has served the instrumentation community very well since 2005 (that's Python 2.3!) and still does.

However, Python and the different supported platforms have changed a lot in the recent years. We thought that PyVISA could use an update. Within the Lantz Project we did a small proof of principle of such update in visalib. Now we are taking what worked well and use it into PyVISA 1.5 (without changing the API!). In other words, PyVISA 1.5 brings several important changes in the underlying architecture without forcing you to change the programs.

Some time ago I posted that we were going beta. Now PyVISA 1.5 is finally released.

The new architecture is summarized here and the comparison with the previous one is here. Briefly you get Python 3 support, Mac OS X support, a better way to find libraries in your platform, an isolated ctypes wrapper. But the most important change is that the VISA library is not opened on import anymore. You can still use the instrument and get_instruments_list helpers (although we encourage not to do it!), but under the hood they will only instantiate a VisaLibrary object when you need them. We think that this will lead to more explicit and clear code, easier to deploy and to upgrade. There other small goodies around. Take a look at the docs.

You can install PyVISA or upgrade your previous version using pip:
 
$ pip install -U pyvisa

This release is only possible thanks to the contribution of a lot of people that contributed bug reports, testing and code. Thanks to everybody!

We are moving forward to make PyVISA even better. Submit your bug reports, comments and suggestions in the Issue Tracker. We will address them promptly.

Read the docs: http://pyvisa.readthedocs.org/
or fork the code: https:/https://github.com/hgrecco/pyvisa/

Martín Gaitán: Deploy de Django con Circus, Chaussette y Nginx

   Publicado:

Aunque hay un pequeño mito al respecto, poner en producción una aplicación web hecha en Python no es tan complejo. Esa facilidad se debe a la estandarización de la pasarela WSGI, que define cómo se comunica (o se debería comunicar) una "app" (sea hecha con un framework o no) con un servidor web.

Si bien Nginx, el servidor web que está desplazando a Apache como el más popular tiene un módulo que implementa el estándar WSGI de manera nativa, la arquitectura más típica es utilizarlo como proxy reverso, conectado a un servidor WSGI especializado como Gunicorn que interactua con la aplicación web (posiblemente a través de multiples instancias o workers). Como queremos que nuestra app funcione permanentemente, el proceso WSGI y otros que sean necesarios (por ejemplo Redis) se demonizan de manera que sepan restaurarse automáticamente si mueren y sea posible monitorearlos: para eso suele usarse supervisor.

https://raw.githubusercontent.com/mozilla-services/circus/dff6cf3a348fecc0b58bd08cae91b1508aed14c2/docs/source/classical-stack.png

La arquitectura de deployment más común para una aplicación web Python

Si bien esta arquitectura está bastamente probada, hay una opción mejor.

https://circus.readthedocs.org/en/0.11.1/_images/circus-medium.png

El circo y el soquete

Circus y Chaussette son proyectos desarrollados por Tarek Ziadé y el equipo de Mozilla Sevices.

Tip

Tarek es un pythonista francés, core committer de Python y muchos proyectos relacionados. Recibió el reconocimiento de la PSF por sus aportes y es autor del gran libro Expert Python Programming

Una arquitectura de producción análoga a la descripta arriba, pero basada en Circus, se ve así:

https://raw.githubusercontent.com/mozilla-services/circus/dff6cf3a348fecc0b58bd08cae91b1508aed14c2/docs/source/circus-stack.png

Circus maneja procesos demonizados igual que Supervisor, pero además puede bindear sockets y manejarlos de la misma manera. Este desacople de la gestión de sockets del webserver WSGI permite muchas posibilidades, tanto en la gestión como en la escalabilidad de la arquitectura.

La capa WSGI en este esquema la aporta Chaussette, que tiene la particularidad que, en vez de abrir un socket nuevo, utiliza el que Circus abrió (y controla) para el worker. Además, aunque trae una implementación de WSGI built-in, puede usar muchos backends más eficientes o con características particulares como meinheld, gevent, gevent-socketio, entre muchos otros.

A diferencia de Supervisor que se basa en el protocolo XML-RPC para inspeccionar los procesos que controla, Circus utiliza un canal pub/sub basado en el mucho más moderno ZeroMQ (lo mismo que usa IPython Notebook) que permite un monitoreo realtime y una API de plugins mucho más simple. Otra diferencia, nada menor, es que Circus funciona con Python 2 o 3 (supervisor no es compatible con Python 3).

Y de yapa: Circus se puede usar como una biblioteca de muy alto nivel para la gestión no bloqueante de procesos. Se puede pensar con un wrapper de subprocess y/o multiprocess, que aporta información de monitoreo y estadísticas, control de flujo, una capa de señales (hooks) muy completa y más.

Desplegando Django

Para ejemplificar, voy utilizar un proyecto Django que estoy desarrollando (muy lentamente): nikolahub.

Circus se configura con un archivo con formato .ini. El mio, que bauticé circus.ini quedó así:

[circus]
check_delay = 5
endpoint = tcp://127.0.0.1:5555
pubsub_endpoint = tcp://127.0.0.1:5556
stats_endpoint = tcp://127.0.0.1:5557

[socket:nikolahub]
host = 127.0.0.1
port = 8080

[watcher:nikolahub]
cmd = /virtualenvs/nikolahub/bin/chaussette --fd $(circus.sockets.nikolahub) nikolahub.wsgi.application
use_sockets = True
numprocesses = 3

[env:nikolahub]
PYTHONPATH = /projects/nikolahub

La sección watcher indica lanza el comando a controlar, en este caso levantando 3 workers de la aplicación -django. Notar que como tengo instalado Chaussette dentro del virtualenv, uso el path absoluto al ejecutable. El fragmento --fd $(circus.sockets.nikolahub) se expande implícitamente asignando el pid que obtuvo el fork (el proceso hijo) de circus.

Si quisieramos usar otro servidor web, sólo hay que indicar cual con el parámetro --backend Por ejemplo:

cmd = /virtualenvs/nikolahub/bin/chaussette --backend gevent --fd $(circus.sockets.nikolahub) nikolahub.wsgi.application

Podemos probar si todo funciona:

(nikolahub)tin@morochita:$ circusd circus.ini
2014-06-12 04:36:16 circus[1141] [INFO] Starting master on pid 1141
2014-06-12 04:36:16 circus[1141] [INFO] sockets started
2014-06-12 04:36:16 circus[1141] [INFO] Arbiter now waiting for commands
2014-06-12 04:36:16 circus[1141] [INFO] nikolahub started
2014-06-12 04:36:16 circus[1141] [INFO] circusd-stats started
2014-06-12 04:36:17 circus[1150] [INFO] Starting the stats streamer
2014-06-12 04:36:17 [1149] [INFO] Application is <django.core.handlers.wsgi.WSGIHandler object at 0xa06f60c>
2014-06-12 04:36:17 [1149] [INFO] Serving on fd://5
2014-06-12 04:36:17 [1149] [INFO] Using <class chaussette.backend._wsgiref.ChaussetteServer at 0x9f2d6ec> as a backend
2014-06-12 04:36:17 [1148] [INFO] Application is <django.core.handlers.wsgi.WSGIHandler object at 0x939b60c>
2014-06-12 04:36:17 [1148] [INFO] Serving on fd://5
2014-06-12 04:36:17 [1148] [INFO] Using <class chaussette.backend._wsgiref.ChaussetteServer at 0x92596ec> as a backend

Tendremos la aplicación servida en el puerto 8080 de localhost. Demonizarlo es sólo un flag:

(nikolahub)tin@morochita:$ circud --daemon circus.ini

Para implementar nginx como proxy reverso armé un archivo nginx.conf:

server {
    listen 80;
    server_name nikolahub.nqnwebs.com;

    location /static/ {
            alias /projects/nikolahub/static/;
    }

    location /media/ {
        alias /projects/nikolahub/media/;
    }

    location / {
        proxy_pass http://localhost:8080/;
        proxy_pass_header Server;
        proxy_set_header Host $host;
        proxy_redirect off;
        proxy_set_header X-Real-IP $remote_addr;
        proxy_set_header X-Scheme $scheme;
        proxy_connect_timeout 600;
        proxy_send_timeout 600;
        proxy_read_timeout 600;
    }
}

Luego agregamos el sitio:

$ ln -s /etc/nginx/sites-available/nikolahub nginx.conf
$ ln -s /etc/nginx/sites-enable/nikolahub nginx.conf
$ sudo service nginx restart
http://upload.wikimedia.org/wikipedia/commons/thumb/6/67/Reverse_proxy_h2g2bob.svg/400px-Reverse_proxy_h2g2bob.svg.png

Esto pone a nginx como "frontend" de la aplicación, sirviendo los directorios con contenido estático y pasando el resto de las peticiones al puerto 8080 que administra Circus.

Ya tenemos nuestro sitio en producción.

El dueño del circo y los monitos

De ahora en más, podremos usar las herramientas que provee Circus.

circusctl es el dueño del circo. Puede parar, reiniciar, cambiar la cantidad de workers, abrir una consola ipython para interactuar o inspeccionar y mucho mas. Se puede usar como subcomandos (circusctl <subcmd> <watcher>) o usar la consola interactiva.

Por ejemplo, si quisiera ver cuantos procesos workers tengo y agregar uno más, podría hacer así:

(nikolahub)tin@morochita:$ circusctl numprocesses nikolahub
3
(nikolahub)tin@morochita:$ circusctl incr nikolahub
ok
(nikolahub)tin@morochita:$ circusctl numprocesses nikolahub
4

Lo mismo y más se puede hacer desde una consola IPython.

(nikolahub)tin@morochita:$ circusctl ipython
Python 2.7.4 (default, Apr 19 2013, 18:32:33)
Type "copyright", "credits" or "license" for more information.

IPython 2.1.0 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]: arbiter.numprocesses()
Out[1]: 4

circus-top es un monitor realtime, estilo top. Escucha las estadísticas que produce circusd-stats.

(nikolahub)tin@morochita:$ circus-top
/images/circus-top.png

circus-top en acción. Muestra los procesos watcher y los recursos que cosumen.

Todo esto puede verse y manejarse cómodamente a través de circus-web, un dashboard web que permite monitorear y administrar circus, con gráficos realtime y muy fácil de usar.

https://circus.readthedocs.org/en/0.11.1/_images/web-watchers.png

Desde las últimas versiones, circus-web se refactorizó para basarla en Tornado (originalmente usaba bottle) y hay que instalarlo aparte.

$ pip install circus-web

Conclusiones

Circus es una herramienta que simplifica el stack de deployment de una aplicación web WSGI. La API de alto nivel, una arquitectura mucho más moderna y simple y el aval de ser desarrollada (y usada exhaustivamente) por Mozilla, son avales poderosos para probarla.

Como escribió el Marcos Luc "la función ya debería empezar (...) Bueno nena, buena suerte, cada vez la red te teme más..."

Damián Avila: Zen themes updated

   Publicado:

OK, time to recap some things... As you know, Nikola 7.0.0 was released some weeks ago. It has a lot of improvements, bug fixes and new features. I recommend you to download and try it! As part of the release, we paid attention to update all the plugins and themes inside the Nikola Github organization (don't forget you can contribute with your own plugins and themes!). So, I updated my own themes, in particular, the Zen ones.

Read more… (2 min remaining to read)

Roberto Alsina: Nikola v7 finally out!

   Publicado:

I am th­ri­lled to an­noun­ce ver­sion 7 of Niko­la, a sta­tic si­te and blog ge­ne­ra­tor is ou­t, wi­th a ba­zi­llion fea­tu­res and bu­gfixes (see be­lo­w).

You can get it at all the usual pla­ce­s, and he­re's the re­lea­se an­noun­ce­ment

He­re's the new fea­tu­res, the bu­gfixes list would make the post too long :-)

  • Added UNS­LU­GI­FY_­TI­TLES op­tion for making ti­tles fe­tched via the ­fi­le­na­me re­gexp pre­ttier (Is­sue #1282)
  • New de­pen­den­cie­s: na­tsort (na­tu­ral sor­ting in ga­lle­rie­s) and da­teu­til (re­pla­ces py­tz)
  • Niko­la.­co­m­man­ds are now the use­r-­friend­ly wra­ppers from con­so­le (Is­sue #1177)
  • Add a gi­thu­b_­de­ploy co­m­mand to de­ploy to Gi­tHub pa­ges (Is­sue #1208)
  • Re­mo­ve tidy fil­ter (it was bro­ken due to tidy being an­cien­t) (Is­sue #1164)
  • Added GE­NE­RA­TE_R­SS se­tting to allow di­sa­bling RSS in Niko­la (Is­sue #1236)
  • Li­nk lis­tings raw sour­ces if CO­P­Y_­SOUR­CES is True (Is­sue #1214)
  • Mu­ch mo­re po­wer­ful niko­la plu­gin co­m­mand (Is­sue #1189)
  • Mo­re po­wer­ful con­so­le mo­de allo­ws ac­ce­ss to all niko­la co­m­man­ds (Is­sue #830)
  • New `RO­BO­TS_EX­CLU­SION­S` op­tion lis­ting re­sour­ces to ex­clu­de from site­ma­p and in­clu­de in new ge­ne­ra­ted /ro­bo­ts.­txt (Is­sue #804)
  • Ge­ne­ra­te site­ma­pin­dex con­tai­ning RSS and site­map fi­les (Is­sue #804)
  • Su­pport hooks in tem­pla­tes, for use by plu­gins (Is­sue #896)
  • Use read­li­ne if avai­la­ble (Is­sue #1238)
  • Re­pla­ced REA­D_­MO­RE_­LI­NK wi­th IN­DEX_­REA­D_­MO­RE_­LI­NK an­d RSS_­REA­D_­MO­RE_­LI­NK (Is­sue #1222)
  • Added rea­din­g_­ti­me, re­mai­nin­g_­rea­din­g_­ti­me, pa­ra­gra­ph_­coun­t, ­re­mai­nin­g_­pa­ra­gra­ph_­count tags for REA­D_­MO­RE_­LI­NK (Is­sue #1220)
  • Add ca­no­ni­cal li­nk in lis­tings.
  • Added su­pport for new me­ta fi­les that are the sa­me for­mat as 1-­fi­le me­ta­da­ta, a­llo­wing for grea­ter fle­xi­bi­li­ty (Is­sue #954)
  • Co­lor­box is now in­ter­na­tio­na­li­zed (Is­sue #1205)
  • Added LO­GO­_URL and SHO­W_­BLO­G_­TI­TLE=­True se­ttings to fa­ci­li­ta­te sho­wing off lo­gos (Is­sue #1122)
  • Crea­te au­to­ma­tic sto­ry in­dex pa­ges for su­bfol­der­s, too (Is­sue #793)
  • New Slo­vak trans­la­tion by To­máš Prékop
  • Created a Ma­rk­do­w­nEx­ten­sion plu­gin cla­ss (Is­sue #1175)
  • The ba­se the­me pro­du­ces pro­per­ly sec­tio­ned and se­man­tic HT­M­L5 (Is­sues #1123, #1137)
  • The ba­se the­me co­mes wi­th a new sty­lish look by de­fault (Is­sue #1137)
  • The ba­se the­me su­ppor­ts Ri­gh­t-­to­-­Le­ft by using ::­di­r(r­tl) CSS4 ru­les an­d <ht­ml di­r="r­tl"> tags whe­re va­lid (Is­sue #1146)
  • Boots­trap 2 up­dated to 2.3.2 (via Is­sue #1137)
  • Added FOR­CE_I­SO­8601 se­tting that cu­rren­tly makes new_­post use ISO 8601 da­tes (via Is­sue #1156)
  • Added su­pport for TZ spe­ci­fied in post da­te (Is­sue #1118)
  • Make niko­la init ask about the si­te’s se­ttings (Is­sue #1080)
  • Use na­tu­ral sor­ting for fi­les and fol­ders list in lis­tings and ga­lle­ries (Is­sue #1144)
  • Added in­va­rian­ce tes­ting (Is­sue #672)
  • Plu­gins can in­ject tem­pla­tes in the sys­tem (Is­sue #1139)
  • niko­la im­por­t_wor­dpress now has a --­­q­­tran­s­­la­­te op­tio­n, to par­se pos­ts in the qtrans­la­te wor­dpress plu­gin for­mat and turn them in­to mul­ti­lin­gua­l ­Niko­la pos­ts (Is­sue #1072)
  • niko­la con­so­le allo­ws for in­ter­pre­ter choi­ce via -b, -i, -p; mo­reo­ve­r, ­su­pport for bp­y­thon is not de­pre­ca­ted an­y­mo­re (Is­sue #1126)
  • re­ti­red tag for pos­ts has been re­pla­ced wi­th pri­va­te (via Is­sue #686)
  • Chan­ged the de­fault TRANS­LA­TION­S_­PA­TTERN to "{­pa­th}.{­lan­g}.{ex­t}". (Is­sues #990, #829)
  • Ba­ckwar­ds com­pa­ti­bi­li­ty wi­th v5 is bro­ken. Added ba­ckwar­d­s-in­com­pa­ti­ble ­chan­ges. (Is­sue #829)
  • Added a CON­TEN­T_­FOOTE­R_­FOR­MA­TS con­fig op­tio­n. It is us­ed to for­ma­t ­the CON­TEN­T_­FOOTER va­ria­ble pro­per­l­y, for com­pa­ti­bi­li­ty wi­th ­the Trans­la­ta­ble Se­ttings fea­tu­re. The va­ria­ble takes a dic­t, the ke­ys of whi­ch are lan­gua­ges, and va­lues are (args, kwargs). (Is­sue #1112)
  • Cer­tain se­ttings are now trans­la­ta­ble. As of no­w, the se­ttings are: ­BLO­G_AU­THO­R, BLO­G_­TI­TLE, BLO­G_­DES­CRIP­TIO­N, LI­CEN­SE, CON­TEN­T_­FOOTE­R, ­SO­CIA­L_­BU­TTON­S_­CO­DE, SEAR­CH_­FOR­M, BOD­Y_EN­D, EX­TRA_HEA­D_­DA­TA, ­NA­VI­GA­TIO­N_­LI­NKS, REA­D_­MO­RE_­LI­NK (the up-­to­-­da­te list is avai­la­ble in ­SI­TE.­TRANS­LA­TA­BLE_SE­TTINGS) (Is­sues #851, #1057, #1061, #1112)
  • New Pos­t.au­tho­r() re­turns me­ta 'au­tho­r' or BLO­G_AU­THOR (Is­sue #1117)
  • Ship ba­se-­jin­ja, boots­tra­p-­jin­ja, boots­tra­p3-­jin­ja wi­th Niko­la (Is­sue #1104)
  • In­vert HI­DE_­SOUR­CE­LI­NK and HI­DE_UN­TRANS­LATE­D_­POS­TS in­to SHO­W_­SOUR­CE­LI­NK and SHO­W_UN­TRANS­LATE­D_­POS­TS (Is­sue #1076)
  • Re­mo­ve old me­ss­ages le­ft over for ba­ckwar­ds com­pa­ti­bi­li­ty: (Is­sues #829, #1105)
    • "Mo­­­re po­s­­ts abou­­t", re­­pla­­ced by "Mo­­­re po­s­­ts about %s"
    • "Po­s­­te­­d", re­­pla­­ced by "Po­s­­te­­d:"
    • "A­l­­so avai­­la­­ble in", re­­pla­­ced by "A­l­­so avai­­la­­ble in:"
  • Re­mo­ve old "s­l_­SI", "tr_­TR" lo­ca­le alia­ses (u­se "s­l" and "tr") (Is­sue #829, #1105)
  • New op­tion RSS_­PLAIN to op­tio­na­lly strip HT­ML from RSS fee­ds (Is­sue #1107)
  • Su­pport con­tent key in com­pi­ler­s' crea­te_­post (Is­sue #1098)
  • Use se­tup­tool­s’ ex­tras fea­tu­re. Use pip ins­ta­ll niko­la[ex­tra­s] to­ ins­ta­ll Niko­la wi­th ex­tras (re­­qui­­re­­men­­ts-ex­­tra­s.­­txt, for­mer­l­y re­­qui­­re­­men­­ts-­­fu­­ll.­­txt -- no­te the na­me chan­ge!) (Is­sue #1089)

Hernán Grecco: Pint 0.5: now with uncertainties!

   Publicado:

Today I have released version 0.5 of Pint, a Python units library.

Pint is Python package to define, operate and manipulate physical quantities: the product of a numerical value and a unit of measurement. It allows arithmetic operations between them and conversions from and to different units.

It provides a comprehensive and extensive list of physical units, prefixes and constants defined in a standalone text file. The registry can parse prefixed and pluralized forms of units resulting in a much shorter and maintainable unit definition list.

It also provides great NumPy integration, with implicit unit conversion and an emphasis on correctness.

What's new

Pint 0.5 brings a long awaited feature: the integration with uncertainties, a great package by Eric Lebigot. Pint Measurement Class is now built using uncertainties ufloat class. The integration will be complete in 0.6 when we add support for all math operations.

By the way, the integration of uncertainties in Pint is a really nice example of collaboration between open source projects. From an issue that Eric posted on the tracker, we worked out together modifications to both projects that made the integration easier and more productive.

Pint 0.5 also brings performance improvements. Some operations are much faster due to internal caching of common unit conversions. Importing the package is faster too as the default registry is only loaded when needed.
 
There are no backwards incompatible changes in this version. But we have added the __call__ method to UnitRegistry. We suggest that you use it instead of __getitem__ which will be deprecated in future versions.

A few internal things have been improved. Better documentation of the code. Better logging, warnings and error messages. More configurations to testing configuration to our continous integration at travis. The test coverage, which was quit good since the begining of the project (~ 80%), is now even better (93%). And we are keeping an eye on this using coveralls.

There a lot of other improvements, you can look at the full list of changes.

Thanks to the people that contributed bug reports, suggestions and patches since 0.4. In particular to: Eduard Bopp, Felix Hummel, Jim Turner, Joel B. Mohler, Kenneth D. Mankof, Luke Campbell, Peter Grayson, Sundar Raman, Tom Ritchford and coutinho. (Please let me know if I am forgetting someone!)

Interested? Install it and give it a try!

Submit your bug reports, comments and suggestions in the Issue Tracker. There are already some ideas for version 0.6. Check them out, comment and add yours.

Read the docs: https://pint.readthedocs.org/
or fork the code: https://github.com/hgrecco/pint

Alejandro Santos: Substring matching in Python (run between naive, Boyer-Moore, and Suffix Array)

   Publicado:

A  few days ago I found this very interesting problem: given a list of strings L, write a function that returns the elements of L which contains some substring S.

For example, given L=["Casa", "Perro", "Gato", "Onomatopeya", "internacionalizacion", "Om nom nom"] and S="nom", we want the result of find(L, S) = ['Onomatopeya', 'Om nom nom'].

Naïve Version

On Python this sounds simple enough, and we can write:
def find1(L, S):
    return [x for x in (L) if S in x]
However, for a big enough L and S we can see the runtime of this function depends not only on the size of L but also on the size of S. That's it, the runtime complexity of find1 in BigOh notation is: O(n.m.s), where:
  • n=len(L)
  • m=max([len(x) for x in L])
  • s=len(S)
The plot of time for find1 for a fixed L and where we increase the size of S looks like this:


Boyer-Moore-Horspool

It turns out that since version 2.5, Python's "in" operator is implemented internally using a modified version of Boyer-Moore algorithm for substring searching. The details are here.

We can take advantage of this detail by creating a temporary structure for faster lookups. We pre-process L so we can make fast queries.

The idea is to construct a big string W with the concatenation of all the elements of L, using a special char as separator, a char that is not present on S nor any element of L. For example:
L = ["Casa", "Perro", "Gato", ...]
W = "Casa\nPerro\nGato\n..."
Then, finding if a substring S is present in any of the elements of L can be answered by just writing: 
S in W
This allows us to answer whether a substring is present or not. To actually construct the resulting list of elements of L which contain S we need another helper structure. We build T, a list of integers that, for every elements in L, equals the starting index of this element in W. Continuing with the example:
T = [0, 5, 11, 16, ... ]
This means the first element, "Casa", starts at index 0 in W; the second element "Perro" starts at index 5 in W, etc. And this structure allows us to quickly determine the index in W for every element in, and we lookup the index by doing a binary search on T.

The runtime complexity for constructing this intermediate index is O(n), with O(n) memory usage.

Our new find function should then:
  • find the first position of S in W as p
  • determine for which element of L this index relates to, by doing a binary search on T
  • from p+1 onwards, find again the next S in W.
Since an element of L can contain many times the same substring S we may jump to the next word on W.

On code, the find2 function looks like:
def find2(L, S):
    # Using the native Boyer-Moore implementation of the "in" operator
    R = []
    i = W.find(S)
    while i != -1:
        p = bisect.bisect_right(T, i) - 1
        e = L[p]
        #assert S in e
        R.append(e)
        i = W.find(S, T[p] + len(e))
    return R
The runtime complexity of this new find function is: O(n.m). We still need to take into account the length of each element of L since BMH algorithm is (mostly) linear on the W string. 

The plot of runtime for find1 vs. find2 looks like the following graphic. Again, we are leaving a fixed L and increasing the size of S:



Suffix Array

There is a third way to solve this problem, by means of constructing a suffix array

This amazing data structure offers a runtime complexity of O(log N) for suffix lookups, where N is the length of the string. Incidentally, it also allows to lookup for substrings, since we just lookup until a suffix on the SA has S as prefix.

Again, we need to construct an intermediate index, which is again very simple: sort all the possible suffixes on W. The trick is how to do it: we shall not keep every possible suffix as an string, but just a list of starting positions for every suffix, and sort this list by the actual string of the suffix.

In code, the construction of the SA table is really simple:
# Suffix Array Table
SL = list(range(len(W)))
SL.sort(key=lambda x: W[x:x+100])
The runtime complexity for constructing this intermediate index is O(n.log n), with O(n) memory usage.

To find a specific suffix we should binary search the SA table, using the element on SL to determine where in W the suffix starts.

Since a substring may appear many times on many elements of S, we may have many sufixes starting with S. The good news is, since the list of suffixes is sorted, all this suffixes will be one after another on the SL table. But since we are doing a binary search on the list of suffixes, we can't be sure on where the middle pointer will jump in this contiguous sequence of suffixes, all starting with S. 

Therefore, when we find the position of some suffix we should go back a little to make sure we are starting on the first suffix on the sequence of suffixes that start with S.

On code, our new find3 function looks like:
def find3(L, S):
    # Suffix array
    start = 0
    end = len(SL)
    while start < end:
        mid = start + (end - start) // 2
        pa = SL_key_fn(W, SL[mid], 100)
        pb = SL_key_fn(S, 0, len(S))
        if pa < pb:
            start = mid + 1
        elif pb < pa:
            end = mid
        else:
            # A word may contain the same S multiple times
            R = set()
            while mid > 0 and W.startswith(S, SL[mid]):
                mid = mid - 1
            if not W.startswith(S, SL[mid]):
                mid = mid + 1
            while mid < len(SL) and W.startswith(S, SL[mid]):
                p = bisect.bisect_right(T, SL[mid]) - 1
                e = L[p]
                assert S in e
                R.add(p)
                mid = mid + 1
            return [(L[i]) for i in R]
    return []
The SL_key_fn function was a failed experiment to enhance the performance of the lookups. This function today is:
def SL_key_fn(data, x, llen):
    return data[x:x+llen]
Which is the same as the key on the SA table sorter.

The runtime performance of the find3 function is: O(log (n.m)), and the plot of the three functions looks like this:



Drawbacks

This SA implementation in Python is using a lot of temporary memory for sorting the table. My implementation on my laptop is using 2.4GB of RAM to sort an L of 150k elements. There's been some discussion about this memory issue on this blog post and in this Stack Overflow question.

Special thanks

Python Argentina community is a great place to look for help for all your spanish Python programming needs. 

Facundo Batista: Recuperando terreno con el cine

   Publicado:


Entre los viajes y las vacaciones, estos meses terminé viendo un montonazo de películas. Encima, no aparecieron muchas peliculas copadas para anotar a futuro.

Por otro lado, no estuve viendo muchas series. Con Moni estamos viendo Battlestar Galactica, y yo tengo varias a punto de arrancar (Black Mirror, Almost Human, Through The Wormhole S03).

Pero, a nivel de películas, sí recuperé bastante terreno, :)

  • Chronicle: -0. Muy bien desarrollado el tema de cómo llevar adelante, explorar, y en algún punto sobrellevar, un superpoder adquirido. El resto de la película no vale.
  • Contagion: -0. Muestra de forma interesante (y ajustado a la realidad, me parece) el proceso social ante una epidemia, y las actuaciones están bien, pero le falta como película, como historia contada, como relato.
  • Dream house: +0. Predecible, predecible, predeci..WHAT? Un giro loco, la historia está buena, las actuaciones también; quiere ser un toque de terror pero blah.
  • El hombre de al lado: -0. Tiene partes interesantes, y Daniel Araoz está genial, pero la historia no llega a evitar el naufragio.
  • Elefante blanco: +0. Una realidad que uno (yo) no conoce; bien crudo como acostumbra Trapero. Darín está bien como siempre. Podría estar mejor la historia.
  • Ender's game: +1. Es una buena adaptación del libro, y la película está buenísima. Sí, el libro está mejor, tiene toda una parte que en la peli ni aparece, y es mucho más profundo... pero todo eso no hace que la peli en sí deje de estar buena.
  • Habitación en Roma: +1. Una película hermosa, cruda, y maravillosa, sobre el "enamoramiento".
  • Haywire: -0. Una película de acción que tiene algunos buenos actores un poco desaprovechados, tiene partes buenas, pero meh, es una más sin nada que la haga valer específicamente.
  • Killer Elite: -0. Al final no es más que una historia (que sí está buena) donde muchos machotes están todo el tiempo midiendo a ver quien tiene la pistola más larga.
  • Margin call: +1. Impecablemente contado la interna humana de un descarrilamiento financiero. Me gusta mucho el punto de vista del trabajador interno de la empresa, me pareció muy veraz. Muy buenas actuaciones.
  • Men in black III: +0. Divertida. Más de lo mismo pero con lo interesante de los saltos temporales y mostrar como era MIB en el pasado :)
  • Mission: Impossible - Ghost protocol: +0. No deja de ser la misma película fantasiosa de siempre, pero esta vez me divertí bastante al verla.
  • Monsters University: +1. Tan buena como la primera, aunque totalmente distinta.
  • No strings attached: -0. Natalie Portman no la llega a rescatar; el tema es trillado, no le dan un giro interesante, y Kutcher, como siempre, resta.
  • Paul: +0. Comedia liviana, nada espectacular, para reirse un rato y disfrutar todas las referencias extraterrestroides.
  • The Avengers: +0. Un poco demasiado violenta, pero en el límite (me hacía acordar a Transformers). Me divirtió. Me gustó los (escasos) planteos filosóficos que tiene, aunque al final siempre el mensaje de "menos mal que tenemos superheroes que nos van a salvar cuando todo esté mal", con el que estoy totalmente opuesto.
  • The King's speech: +1. Fantástica película, con actuaciones soberbias, y una historia muy interesante sobre superación personal.
  • The Ledge: +1. La historia interesante, las actuaciones bien. Muy buenos contrapuntos sobre "la religión". Emotiva. Patrick Wilson mejor de lo que esperaba, y Terrence Howard, como siempre, muy muy bien.
  • The divide: +1. Muy bien hecha. Muestra tan bien las miserias humanas que, aunque no soy impresionable y me banco (casi) cualquier cosa, no la voy a volver a ver.
  • The hobbit: The desolation of Smaug: +1. Segunda parte de la trilogía, sigue estando muy buena. Sorprendente la voz de Smaug (el dragón), ¡es Sherlock! http://www.imdb.com/name/nm1212722/
  • The thing: +1. Es vieja, pero los efectos no están tan mal. Y parece que tiene un montón de lugares comunes... hasta que uno entiende que en esa época no eran comunes! ;)


Las anotadas nuevas:


Finalmente, el conteo de pendientes por fecha:

(Sep-2008)    6
(Ene-2009)   18  12   1   1
(May-2009)   11  10   5
(Oct-2009)   16  15  14
(Mar-2010)   18  18  18  16   4
(Sep-2010)   18  18  18  18  18   9   2   1
(Dic-2010)   13  13  13  12  12  12   5   1
(Abr-2011)   23  23  23  23  23  23  22  17   4
(Ago-2011)       12  12  11  11  11  11  11  11   4
(Ene-2012)           21  21  18  17  17  17  17  11
(Jul-2012)               15  15  15  15  15  15  14
(Nov-2012)                   12  12  11  11  11  11
(Feb-2013)                       19  19  16  15  14
(Jun-2013)                           19  18  16  15
(Sep-2013)                               18  18  18
(Dic-2013)                                   14  14
(Abr-2014)                                        9
Total:      123 121 125 117 113 118 121 125 121 110

Damián Avila: 48 themes for your IPython notebook

   Publicado:

OK, a short post to give you some material to play with over the weekend ;-).

Today, I woke up early and whereas I was drinking a mate (a native drink here in Argentina) for breakfast, I remember a tweet from Nikhil Sonnad where I was mentioned:

Read more… (6 min remaining to read)

Damián Avila: Loader and Writer, IPython nbextensions to easily edit your text.

   Publicado:

Coming back to the nice practice of release my own IPython nbextensions, today I will release two extensions I use a lot in my daily workflow: loader and writer, useful extensions to load files into the IPython notebook and to write the content to the same (or another) file.

Read more… (3 min remaining to read)

Share