Martín Gaitán: Lo siento por vos

A fines de enero, apenas volvimos de Ushuaia, en la góndola de los fideos del Vea de mi barrio decidí que iba a retomar Preciosa. Hice un aviso en la lista de correo y lo tuiteé, sin esperar mucha respuesta.

Cuando salieron las primeras aplicaciones para "Precios Cuidados", Luciano Ferrer me preguntó si eran lo mismo que lo que yo quería hacer. Le respondí que Preciosa era mucho más que eso, pero todavía tenía dudas sobre cómo concretarlo:

Tres meses después Preciosa tiene una primera versión con casi 2000 descargas, 400 usuarios activos, múltiples aparaciones en radio y TV y muchísimas ideas y ganas para seguir creciendo.

Fueron semanas enteras de laburo, a pulmón, muchísimas horas por día (71 días sin pausa, dice github) y la colaboración desinteresada de decenas de personas e instituciones. La Incubadora de Empresas de la Universidad de Córdoba (donde funciona Phasety) nos dió espacio y asesoramiento, la asociación de consumidores más importante de Perú está interesada en implementarlo en su pais, Huayra Linux incluye Preciosa en su última versión, programadores de nivel internacional hicieron aportes al código, diseñadores y diseñadoras hicieron el logo y muchas otras piezas gráficas y hasta tuvimos que armar un ¡equipo de comunicación!.

Pero más emocionante aún (siempre queda lugar), fue notar que empezamos a hacer realidad algo que gente común estaba esperando. Daniel, un laburante de 47 años, me escribió esto:

"Te mando adjunto una carta que le mande al ministro de economia Kicillof en diciembre de 2013, con un bosquejo de lo que vos estas haciendo realidad. Yo no tengo los conocimientos para desarrollarlo, pero lo necesitamos, cualquier ayuda que este en mis posibilidades hacemelo saber"

En esa carta a Kicillof describe, con palabras sencillas y argumentos brillantes, casi exáctamente las intenciones de la primera versión de Preciosa. La carta termina así:

"Porque la inflación y los precios son una cuestion de estado, el estado somos nosotros, y nosotros DEBEMOS cuidarnos entre todos o fracasaremos en lo que hagamos (...) Esto es lo que me motiva al enviarle esta idea. Me interesa mi futuro,el de mis hijos y el de mis nietos, y el de nuestra tierra Argentina maravillosa."

Mi vieja está orgullosa de todo esto (y yo soy muy riquelmeano, sépanlo), así que estoy tranquilo, pero la "gente que sabe" me dijo, hace unos días, que el proyecto era malo y que se notaba que "no lo siento" (sic).

Qué sabe la gente que sabe

Hace algunas semanas que Preciosa no tiene mucha actividad pública. No hay nuevas versiones de la aplicación, tampoco cambios importantes en la web y hasta estamos flojos con las redes sociales. Pero sigo trabajando todo el día en el proyecto, intentando resolver el "bug Nº 0": necesito plata que me permita armar un equipo profesional full-time dedicado a hacer de Preciosa una herramienta concreta y masiva. No sólo una buena idea potencial: que permita que desde tu teléfono o el sitio web, puedas saber cuánto te va a costar toda tu lista de compras, no sólo un producto en particular. Y que te diga, por supuesto, a dónde te conviene ir y cuánta plata vas ahorrar.

Nunca mandé más mails en mi vida como en estos últimos días. Nunca hablé tanto por teléfono con personas que no conozco ni me animé a "encarar" a gente muy distinta a la que habitualmente me rodea, para contarle sobre el proyecto. Pero lo hice y lo seguiré haciendo porque confío (y sobre todo deseo) que esto funcione.

Por eso dije que sí a la invitación que me hicieron para presentar Preciosa en "El club del Pitch" un encuentro organizado por diversas empresas e instituciones del "ecosistema emprendedor" para presentar proyectos tecnológicos, a los que un panel le hace devoluciones breves, en una especie de simulacro de "ronda de inversión".

Sabía que son ambientes en los que no me siento muy cómodo, donde suele haber mucho ruido y pocas nueces:

Tenía que estar antes de las 9 de la mañana y haber preparado unas diapositivas para una charla de 10 minutos. Ahí estuve, un poco dormido, y me tocó ser el primero. Seis personas, a las que no había visto en mi vida, me harían comentarios en tres minutos, acotados al rol que les tocó: unos sólo las cosas que le parecieron bien, otros las cosas a mejorar, y otros se debían comportar como inversores y decir si pondrían plata en el proyecto.

Mi "pitch" (casi todo allí son anglicismos: pitch, mentors, feedback, coaching, coworking) no fue el mejor, pero creí transmitir bien la potencia de la idea y los desafíos que implica. Regulé mal el tiempo explicando algo superfluo y al final tuve que acelerar porque el máximo de 10 minutos era estricto. No logré explayar para qué necesitaba la plata que pedía y por qué parecía poca.

Una vez que terminás, las "reglas" impiden la interacción con el panel; sólo podés escuchar lo que te dicen. Y lo que me dijeron fueron algunas cosas buenas (las dos mujeres, de unos 40 años, dijeron que les parecía muy buena idea si implementamos la utilidad de encontrar el mejor precio para el "carrito") pero Juan Santiago, dueño de la empresa Santex, me fulminó:

— Me pareció pésimo tu pitch. Horrible. Da la sensación de que no crees en tu proyecto, que podrías estar haciendo esto o cualquier otra cosa, no le transmitis pasión, no llegás a motivar a nadie. Toda esa cosa samaritana de tu proyecto, no la entendí. Y es un disparate que pidas tan poca plata, no tenés ni idea.

Hubo un momento de tensión generalizada en el lugar. El muchacho que coordinaba el encuentro se dió cuenta y se apuró a aclarar:

— Esto es así, no te lo tomes como algo personal. No podés responder nada porque así es la dinámica, sólo podés escuchar. Es preferible que te digan esto ahora, que es gratis, que es un juego, antes de que te suceda en una reunion con inversores de verdad.

Si no es personal, no lo quiero

Me quedé con las explicaciones en la garganta. ¿Cómo podés decirme que no siento lo que estoy haciendo? Hace 10 minutos nunca habías visto mi cara ¿Sabés quién soy, qué hice, qué pienso? ¿Te enteraste que hay decenas de personas que están poniendo muchísimas horas de su tiempo, gratis, sólo porque creyeron en la idea? ¿No es eso "llegar"? ¿No tiene valor alguno para vos que un tipo como Daniel, un laburante, sienta que estamos haciendo lo que él quería pero no podía hacer?

Parece que han comprado en USA el librito del emprendedorismo, donde la idiosincracia y la relación de las personas con la plata es totalmente distinta, donde el lucro es el único motor posible. Pero hablan, siempre, de Latinoamérica, de las posibilidades que hay acá. Algo no encaja en el pitch del pitch.

Un muy buen artículo lo describe así:

Se nos presenta como un desafío, lo que en realidad no puede ser otra cosa, que la adaptación servil a un conjunto de reglas variables, indefinidas y cínicas que no son discutidas, sino acatadas. Para obtener el éxito tienes que seguir las pautas y si no lo consigues se debe a que no lo has hecho bien y por lo tanto, al igual que eres artífice de tu propio éxito, también lo eres del fracaso y de tu pobreza.

Es una lógica de asimetría, una puesta en escena frívola, donde el objetivo es impactar y enamorar (sic) a los inversores, lograr su atención en un standup estudiado de memoria pero que debe parecer, a la vez, espontáneo y pasional. Parece esa gente que está muchas horas frente al espejo peinándose prolíjamente para parecer despeinada. El "emprendedor" no tiene nada para aportarle al otro: está ahí para ser inspeccionado al paso y, pulgar arriba o abajo, enterarse si sirve o no. No hay diálogo posible, no hay enriquecimiento de la idea en un ida y vuelta. Nadie leyó a Freire en el ecosistema emprendedor.

Me lo crucé al coordinador, el que me dijo que no me lo tomara personal, en el Congreso de Periodismo Digital de Fopea al que fui invitado como programador. Le pregunté si sabía cómo podía conseguir una charla con Juan Santiago para explicarle mejor el proyecto.

— No entendiste absolutamente nada. ¿Te creés que el tipo tiene algo que aprender de vos? — me dijo, ofuscado, y luego intentó explicarme lo afortunado que había sido yo por tener la oportunidad que gente tan importante me ayudara desinteresadamente. — A mi me pasó. Yo fui a Sillicon Valley, tuve que pedir plata prestada para el pasaje, a pedir 250 mil dolares para mi proyecto. El inversor me atendió en el pasillo y nunca me miró, estaba así, mirá, mandando mensajitos con el celu.

Sé que hay otras maneras y existe gente que se anima a salirse del libreto. La incubadora de la UNC es uno de estos espacios, que apuesta por el conocimiento como generador de empleo de calidad, de mejorar la vida de la sociedad a través de la tecnología, sin ignorar que para llevarlo a cabo hace falta plata. También debo mencionar a Vanesa Kolodziej, inversora profesional, que no sólo se tomó el trabajo de leer el proyecto y se hizo lugar para charlar conmigo más de 30 minutos, sino que se interesó mucho por saber quién soy, qué busco, sin dejar de hacer su laburo y evaluar la idea desde el punto de vista del negocio.

Sí, necesito plata. La ayuda de la gente que me ama, que cree en mí y en lo que estoy haciendo es enorme, pero no alcanza.

No sé si lograré conseguirla, pero estoy muy seguro de que quiero intentarlo, de que este esfuerzo vale la pena, porque si funciona le servirá a muchos. Sé que es difícil pero me sobra pasión. "La estoy remando en dulce de leche, pero el dulce de leche es rico", le resumí a un amigo.

Y de algo sí estoy seguro: no quiero ser tu mercancía. Creo mucho en lo que hago. Lo siento. Y lo siento por vos.

Joaquin Tita: Interaction Design Guidelines for Home Automation

In the last years, home automation became a reality as a result of an increased availability of different commercial solutions. Some examples of these options can be X10, UPB, Insteon and Z-Wave. Also, the fact that costs decrease day by day making this type technology widely accessible to almost every home.

The idea of smart home, which is controlled by themselves, understands the context and performs actions, has provided new research fields and opportunities. In spite of that, there are still controversial opinions toward how can smart homes improve the life and care of the elderly or of people with different disabilities.

Among the different disabilities, people with impaired motor abilities can take advantages of eye tracking methods to control their homes. This kind of tracking strategies can exploit this limited ability to build a communication channel for interaction and as a result opening new possibilities for computer-based communication and control solutions. Home automation can be the link between software and tangible objects, enabling people with motor disabilities to effectively and physically communicate with their environment.

The European Network of Excellence, COGAIN (Communication by Gaze Interaction), studied in 2004 the advantages and drawbacks of using eye-based systems in the home automation field. Their results identified that there weren't advanced functionalities for controlling appliances and neither interoperability between them. Also, the execution of actions was an issue for the existing eye-tracking mechanisms.

A few years later, members of COGAIN proposed 21 guidelines to promote safety and accessibility in eye tracking methods for environmental control applications.
One of the first applications of this set of guidelines was the DOGeye project, a multimodal eye-based application for home management and control, based on tracking and home control.

COGAIN Guidelines
The COGAIN project was launched in September of 2004 with the goal of integrating vanguard expertise on gaze-based interface technologies for the benefit of users with disabilities. The project was quite successful as it gathered more than 100 researchers from different companies and research groups; all related with eye tracking integration with computers and in assistive technologies.

In 2007, the members of project published a “Draft Recommendations for Gaze Based Environmental Control”. This document proposed a set of guidelines for developing domotic control interfaces based on eye interaction. These guidelines were developed from real uses cases where people with impairments perform daily activities in domotic environments.
  
The document divided the guidelines into four categories:
  • Control Application Safety:  guidelines that determine the behaviour of the application under critical situations such as emergencies or alarms.
  • Input Methods for Control Application: guidelines about the input methods that the application should support.
  • Control Application Signification Features: guidelines impacting the management of commands and events within the house.
  • Control Application Usability: guidelines concerning the graphical user interface and the interaction patterns of the control applications.
Each guideline has a priority level compliant with the W3C style:
  • Priority 1: indicates that must be implemented by the applications as it is related with safety and basic features.
  • Priority 2: indicates that should be implemented by the applications.   

There are three important issues that control interfaces must deal with:
  • Asynchronous Control Sources: the control interface needs to continuously updatethe status of the house (icons, menus, labels, etc.) according to the home situation.
  • Time Sensitive Behaviour: in critical conditions, like an emergency, eye control may become unreliable. In these cases, the control interface must offer simple and clear options, easy to select and must be able to take the safest action in case that the user cannot answer on time. This kind of behaviours offer automated actions triggered by rules. For instance, if it is raining, close the windows. In any case, the user should be able to cancel the automated action and also be aware that it is been executed.
  • Structural and Functional Views: control interfaces can organize the information into structural or functional logic. The first one displays the information in a physical fashion, similar to the real disposition of elements in the house. The second option suits best with actions that doesn’t have a “localized” representation, like turning the anti-theft system on. Good interfaces should find a balance between these two views.

The a summary of the guidelines follows:
Guideline

Content

Priority Level
1.1
Provide a fast, easy to understand and multi-modal alarm notification.
1
1.2
Provide the user only few clear options to handle alarm events.
2
1.3
Provide a default safety action to overcome an alarm event.

1
1.4
Provide a confirmation request for critical & possibly dangerous operations.
1
1.5
Provide a STOP Functionality that interrupts any operation.
1
2.1
Provide a connection with the COGAIN ETU-Driver.
1
2.2
Support several input methods.
2
2.3
Provide re-configurable layouts.
2
2.4
Support more input methods at the same time.
2
2.5
Manage the loss of input control by providing automated default actions.
2
3.1
Respond to environment control events and commands at the right time.
1
3.2
Manage events with different time critical priority.
1
3.3
Execute commands with different priority.
1
3.4
Provide feedback when automated operations and commands are executing.
2
3.5
Manage Scenarios.
2
3.6
Communicate the current status of any device and appliance.
2
4.1
Provide a clear visualization of what is happening in the house.
1
4.2
Provide a graceful and intelligible interface.
2
4.3
Provide a visualization of status and location of the house devices.
2
4.4
Use colors, icons and text to highlight a change of status.
2
4.5
Provide an easy-to-learn selection method.
2

DOGeye
DOGeye was planned as a solution to fill the blank of a home control application in compliance with COGAIN guidelines, through multi-modal interaction with special attention on eye tracking technologies.


DOGeye communicates with Domotic OSGi Gateway (Dog)through a XML- RPC connection. This connection allows information exchange and controlling other devices inside the smart environment. This home control application can be controlled by gaze, by communicating with the eye tracker through a universal driver (ETU-Driver) or by external elements such as keyboard, mouse or touch screen devices.
Dog, an ontology-based domotic gateway, provides the interaction with smart homes. This gateway is able to integrate and abstract functionalities of different domotic systems, offering a uniform high-level access to the home technologies.
The interface was designed through an iterative process, starting from a scratch layout and iteration by iteration refining the design until the final design was reached compliance with COGAIN guidelines. A capture and video of the interface follows. 


DOGeye Interface


There are 8 main elements in the interface disposed in a top menu bar. Each element, when activated, displays a tab with the main details of that element.
  • Home Management contains the basic devices present in a house. These are the devices that belong to the mains electricity wiring such as shutters, doors, lamps, etc.
  • Electric Device contains the electrical appliances not belonging to the entertainment system, such as a coffee maker.
  • Entertainment contains the devices for entertainment, such as media centers and TVs.
  • Temperatureallows handling the heating and cooling system of the house.
  • Securitycontains the alarm systems, anti-theft systems, etc.
  • Scenarioshandles the set of activities and rules defined for groups of devices.
  • Everything Else contains devices not directly falling in the previous tabs, e.g., a weather station.
  • Settingsshows controls for starting, stopping and configuring the ETU-Driver. 

Scenario
If you wanted to turn on the lamp in the kitchen and warm coffee, you should follow the following steps. 

  • First, look briefly at “Home Management” to activate this tab. The map of the kitchen will appear rapidly. 
  • Then stare at the “Enter the room” tab for a time. After doing that, you will see the list of all devices present in that room. 
  • To select the lamp you would look at it and then stare at the “On” button presented in the command area. 
  • Finally, to warm the coffee look at “Electric Device”tab and use the same procedure.
Usability Testing of DOGEye
Previous to the testing, a short introduction to the study and the collection of demographic data was done. Afterwards, a static DOGeye screenshot was shown to the participants to gather a first impression on the interface.

The usability testing was divided into three main phases: warm-up, task execution and test conclusion.

The warm-up phase was executed after calibrating the eye tracker with the participant’s eye. Next, the participant played a simple game for getting used to the eye tracking interaction. This phase was considered finished after achieving a pre-established number of points in the game.

In the task phase each participant was told to complete a set of nine tasks, one at a time.  For two of them, the participants were asked to use the think-aloud protocol, to verify the actions performed.

In last phase, test conclusion, participants were given a questionnaire and asked to rate DOGeye in general, and to rate their agreement with the same sentences proposed earlier, just after seeing the screenshot of DOGeye.

The duration of the entire experiment was dependent on eye tracker calibration problems and on how quickly participants answered the questions, but it ranged between 20 and 30 minutes.

For testing this application, 8 participants (5 female and 3 male, aged 21 to 45) used DOGeye in a controlled environment. These participants performed nine tasks each, with Dog simulating the behaviour of a realistic home. The quality of the eye movement of each participant was not taken into account for the study, since eye tracking is only the input modality.
The tasks were the following ones:
  • Task 1: Turn on the lamp in the living room.
  • Task 2: Plug the microwave oven in the kitchen.
  • Task 3: Find a dimmer lamp, turn it on and set its luminosity to 10%.
  • Task 4: Cancel the alarm triggered by the smoke detector.
  • Task 5: Turn on all the lamps in the lobby.
  • Task 6: If the heating system in the bedroom and in the kitchen is off, turn it on.
  • Task 7: Set to 21 degree the heating system for the entire house.
  • Task 8: Send a general alarm to draw attention in the house.
  • Task 9: Read the smoke detector status and expand the video of the room to full screen.
Result of the Usability Testing
The result of the usability testing was positive and provided useful insights on the application explicitly designed for eye tracking support.
A short summary of the findings follows:
  • Some of the users suggested refactor the top menu. Like splitting the “Home Management” into two different tabs, “Lighting System” and “Doors and Windows”. Also, “Everything Else” tab should be removed because the participants could not understand the meaning.
  • None of the participants used the “multiple selection” feature. Each of them used “single selection”, therefore the feature was removed from the application (except from temperature since it is the only viable modality for multiple selection in this tab).
  • The users appreciated the vocal feedback and the tab divisions.
  • The presence of a camera in the “Security” tab was something that they found  marvellous.
The study concluded with very good feedback from participants, pointing out some errors in the design and motivating the developers to progress in the field and continue enhancing the product. Also, it is the kick off for helping and improving life quality for people with motor impairments from a common starting point.

Reference:
  • De Russis, Luigi, Emiliano Castellina, Fulvio Corno, and Darío Bonino. "DOGeye: Controlling Your Home with Eye Interaction." PORTO Publications Open Repository TOrino. Politecnico Di Torino, 16 June 2011. Web. 10 May 2014.

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

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)

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. 

Gonzalo Martinez: #Flisol2014 sede Agenda Digital



Panel de apertura "El vínculo entre el Software Libre y el Estado"
Constanza Necuzzi - Pablo Etcheverry - Santiago Ceria

Pablo Etcheverry hizo una exposición sobre los aprendizajes con respecto al Software Libre en el estado, algunos referentes a las dificultades en la coordinación de las necesidad de las areas especificas del estado que necesitan seguir gestionando sus recursos y la idea de ingresar cada vez con más software libre que por momentos son dispares, ya que el estado no puede dejar de funcionar por que se quieran cambiar sus sistemas a software libre hay cosas que llevan todo un proceso de migración.Constanza Necuzzi, hizo un analisis más profundo que el SoftLibre en sí, sino abarcando a "Las Comunidades de Práctica" [8] y como estas comunidades de práctica en general y la de software Libre en particular ayudan a generar una sociedad mejor. Santiago Ceria, nos contó sobre el programa Programar2020 [9] y como la programación y el conocimiento informático en general es importante para entender la complejidad del mundo moderno.

Panel: ¿Qué es el Grupo de Trabajo Software Libre del Foro de la Agenda Digital? [0] - Laura Marotias - Verónica Xhardez
Laura y Veronica contaron cual es su lugar dentro del Foro de la Agenda Digital y como de a poco van de manera transversal tocando las diferentes áreas que participan en aquel foro. Pero empecemos desde el principio la Agenda Digital Argentina "es una herramienta creada mediante el Decreto presidencial 512/2009 que impulsa la conformación de un Gabinete Multisectorial orientado al aprovechamiento de las posibilidades que ofrece la Sociedad de la Información y el Conocimiento." [1] y el Foro propiamente dicho, es un encuentro interinstitucional donde se debaten diferentes temáticas dentro de los que la agenda Digital tiene injerencia. Además, este lugar se convierte en un espacio "predecisional" donde diferentes organismos del estado, organizaciones civiles, etc. pueden participar de estas predecisiones, que luego, serán o no parte de una política pública según lo decidan quienes los funcionarios o las instituciones como el Congreso, etc. Los grupos que forman parte actualmente del foro son los siguientes:
Interoperabilidad, Gestión Documental/Digitalización, Profesionalización del Gestor de Información, Software Público, Datos Públicos, GeoInformación, Software Libre, Gobierno Abierto, Seguridad, Contenidos Públicos. [2]

En ese marco el Grupo de Software Libre [3] se encarga de concientizar a los diferentes interesados sobre la necesidad y/o conveniencia de utilizar Software Libre en el estado. Muy Pronto van a lanzar una Web donde presentarán casos éxitos de utilización de software Libre en el estado www.softwarelibre.gob.ar. Donde entre otras cosas se va a mostrar el caso de Éxito de la ANAC [4] y Xtech [5] que viene a continuación.

Panel: "El vínculo entre el Estado y las empresas de Software Libre: el caso ANAC - Xtech" - Sandra D'Agostino - Daniel Coletti

Sandra D'agostino nos relató la cantidad importante de Software Libre con el que trabaja la ANAC y como gracias a eso ahorran mucho en Licencias para invertir su "buen financiamiento" en lo que para ellos es más importante. Luego Daniel Coletti contó como por intermedio de una licitación pública que ganó Xtech la empresa de la que es dueño, empezaron un proceso de migración del correo electronico de la ANAC que antes funcionaba bajo software privativo, y que ahora, va a pasar a funcionar bajo Expresso Livre[6] que es la misma plataforma que funciona actualmente en el correo de Brasil, el cual implementó esta solución en forma acelerada desde que el Gobierno Brasilero se enteró del espionaje internacional que estaba sufriendo [7]. 

En síntesis

Las charlas a mi criterio fueron muy interesantes para saber como se mueve la comunidad de software libre dentro del estado, como se van ganando espacios de a poco y se va demostrando no solo lo importante que es a nivel económico sino lo importante que es a nivel soberanía tecnológica, independencia de las corporaciones y la apropiación de la dirección que se le quiere dar al software por parte del estado amoldandolo a sus necesidades reales.

Gonzalo Martinez: Pascal debe morir!

Pascal [0] ha sido un lenguaje muy interesante y posiblemente lo siga siendo para aprender algoritmos pero tengo la sensación que para aprender a Programar o como parte de una materia como Programación I, hace rato que es demasiado pobre, sobre todo por que hoy en día no sirve para nada más que aprender. Entonces los alumnos o quienes están aprendiendo pierden tiempo (no mucho en verdad pero todos sabemos que el tiempo es "dinero") aprendiendo su sintaxis aprendiendo algunas características particulares que no sirve para nada más que aprender no a programar :S en mi punto de vista sino para aprender algoritmos que debería ser utilizado capaz dentro de esa misma materia. Si bien quien lee este post sabe que soy Fan de Python también saben que Python es categorizado por muchos como un buen lenguaje para aprender, además de ser un lenguaje de propósito general, por lo cual aquel pibe que sabe la sintaxis de Python aprende (además del pensamiento algorítmico) un lenguaje que le puede servir para programar Web, para Programar aplicaciones de Escritorio y para hacer pequeños Scripts para automatizar cosas.
Sin ir más lejos el año pasado participé del PyDay Junin y allí en la UNNOBA[1] presentaron la muy buena iniciativa de cambiar su primer lenguaje de programación que era justamente Pascal por Python [2] [3]  y hay, desde hace unos años, cada vez más lugares donde se enseña Python como lenguaje de programación de entrada [4]. Igualmente aunque no parezca mi idea no es decir que Python DEBE ser el lenguaje de programación en verdad creo que cualquier otro lenguaje de los masomenos modernos (Python, Ruby, etc) puede ser útil para entusiasmar a los que aprenden programación en sus primeros pasos.

Esto se basa en algo que leí hace poco pero que siempre creí sin conocer esta frase.

"Si quieres construir un barco, no empieces por buscar madera, cortar tablas o distribuir el trabajo. Evoca primero en los hombres y mujeres el anhelo del mar libre y ancho."
Antoine de Saint-Exupéry

El proceso de conocer algo no siempre es hermoso, fluido y tangible generalmente es abstracto, a veces engorroso y pareciera poco útil por eso creo fervientemente que para hacer algunas cosas en programación o en cualquier trabajo en verdad. uno debe creer en lo que hace, debe amar lo que hace, por que sino no se entiende como alguien hace cosas tan complicadas. Por eso mi justificación es que Pascal no ayuda en ese proceso HOY de amar la programación, capaz si lo hacia hace años pero creo que el Rol de quienes enseñan hoy en día es actualizarse y no tenerle miedo al cambio y además ser autocríticos y analizar año a año el cambio de los paradigmas sino pasa que te quedás atrás inevitablemente y con eso atrasas a todos a los que les enseñás.
[0] http://es.wikipedia.org/wiki/Pascal_(lenguaje_de_programaci%C3%B3n)
[1] http://www.unnoba.edu.ar/
[2] http://prezi.com/haoscmd_yuca/cambio-de-lenguajes-para-programacion-imperativa/
[3] http://journal.info.unlp.edu.ar/journal/journal35/papers/JCST-Apr13-6.pdf
[4] http://python.org.ar/Proyectos/UsoDePythonEnLaUniversidad

Mariano Draghi (cHagHi): George R.R. Martin y el poder

Ruling is hard. This was maybe my answer to Tolkien, whom, as much as I admire him, I do quibble with. Lord of the Rings had a very medieval philosophy: that if the king was a good man, the land would prosper. We look at real history and it's not that simple. Tolkien can say that Aragorn became king and reigned for a hundred years, and he was wise and good. But Tolkien doesn't ask the question: What was Aragorn's tax policy? Did he maintain a standing army? What did he do in times of flood and famine? And what about all these orcs? By the end of the war, Sauron is gone but all of the orcs aren't gone – they're in the mountains. Did Aragorn pursue a policy of systematic genocide and kill them? Even the little baby orcs, in their little orc cradles?

George R.R. Martin, hablando sobre Tolkien, el poder y la responsabilidad de gobernar.

Fuente: George R.R. Martin: The Rolling Stone Interview (ojo, la entrevista en sí contiene algunos spoilers de la saga A Song of Ice and Fire y la serie de HBO Game of Thrones basada en ella).

La traducción de la cita sería más o menos así: "Gobernar es difícil. Esta [la forma en que los personajes de A Song Of Ice and Fire ejercen el poder] fue tal vez mi respuesta a Tolkien, con quien tengo mis objeciones, a pesar de lo mucho que lo admiro. El Señor de los Anillos tenía una filosofía muy medieval: si el rey era un buen hombre, la tierra prosperaría. Pero si miramos la historia real resulta que no es tan simple. Tolkien puede decir que Aragorn fue coronado y reinó por cien años, y que fue sabio y bueno. Pero Tolkien nunca formula la pregunta: ¿Cuál fue la política de impuestos de Aragorn? ¿Mantuvo un ejército permanente? ¿Cuáles fueron sus medidas en tiempos de inundaciones y hambruna? ¿Y qué pasó con los orcos? Al terminar la guerra, Sauron ya no está, pero los orcos sí — están en las montañas. ¿Acaso Aragorn siguió una política de genocidio sistemático y los mató? ¿Incluso a los bebitos orco, en sus cunitas para orcos?

Mariano Draghi (cHagHi): George R.R. Martin y el poder

Ruling is hard. This was maybe my answer to Tolkien, whom, as much as I admire him, I do quibble with. Lord of the Rings had a very medieval philosophy: that if the king was a good man, the land would prosper. We look at real history and it's not that simple. Tolkien can say that Aragorn became king and reigned for a hundred years, and he was wise and good. But Tolkien doesn't ask the question: What was Aragorn's tax policy? Did he maintain a standing army? What did he do in times of flood and famine? And what about all these orcs? By the end of the war, Sauron is gone but all of the orcs aren't gone – they're in the mountains. Did Aragorn pursue a policy of systematic genocide and kill them? Even the little baby orcs, in their little orc cradles?

George R.R. Martin, hablando sobre Tolkien, el poder y la responsabilidad de gobernar.

Fuente: George R.R. Martin: The Rolling Stone Interview (ojo, la entrevista en sí contiene algunos spoilers de la saga A Song of Ice and Fire y la serie de HBO Game of Thrones basada en ella).

La traducción de la cita sería más o menos así: "Gobernar es difícil. Esta [la forma en que los personajes de A Song Of Ice and Fire ejercen el poder] fue tal vez mi respuesta a Tolkien, con quien tengo mis objeciones, a pesar de lo mucho que lo admiro. El Señor de los Anillos tenía una filosofía muy medieval: si el rey era un buen hombre, la tierra prosperaría. Pero si miramos la historia real resulta que no es tan simple. Tolkien puede decir que Aragorn fue coronado y reinó por cien años, y que fue sabio y bueno. Pero Tolkien nunca formula la pregunta: ¿Cuál fue la política de impuestos de Aragorn? ¿Mantuvo un ejército permanente? ¿Cuáles fueron sus medidas en tiempos de inundaciones y hambruna? ¿Y qué pasó con los orcos? Al terminar la guerra, Sauron ya no está, pero los orcos sí — están en las montañas. ¿Acaso Aragorn siguió una política de genocidio sistemático y los mató? ¿Incluso a los bebitos orco, en sus cunitas para orcos?