desarrollo

Algoritmos: subarray máximo

Hoy vamos a hablar de desarrollo web en particular. Ni de nada relacionado con las últimas tecnologías de programación. Vamos a estudiar varios algoritmos de cálculo del subarray máximo, en mi opinión, muy bonitos. Pero primero planteemos el problema:

Se trata del problema del subarray máximo: Tenemos un array numérico que incluye valores tanto positivos como negativos. Queremos saber cuál es su subarray, de elementos contiguos, cuya suma de sus elementos nos da un valor máximo. Por ejemplo, supongamos el siguiente array:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Su subarray máximo sería (en índices basados en cero) el que va de la posición 3 a la 6:

[4, -1, 2, 1]

Cuyo resultado nos da 6.

Tómate un minuto para esbozar sobre papel un algoritmo que resuelva este problema. O al menos trata de esbozarlo mentalmente. Cuando hayas terminado, continúa leyendo.

Lo más probable es que hayas llegado a una solución de complejidad cuadrática O(n²), o dicho mal y rápido: un bucle dentro de otro bucle. Vamos a ver una posible solución de este tipo en PHP:

function max_subarray($array) {
   $max = 0;

   for ($i = 0; $i < count($array); $i++) {
      $sum = 0;
      for ($j = $i; $j < count($array); $j++) {
         $sum += $array[$j];
         if ($sum > $max) {
            $max = $sum;
         }
      }
   }
   return $max;
}

Es decir, es una solución de fuerza bruta con la que calculamos todas las sumas posibles de todos los subarrays que podemos extraer del array principal. Este algoritmo está bien. Es sencillo, eficiente, su resultado es siempre correcto; pero los hay mejores.

Podemos resolverlo mediante un enfoque recursivo mediante la técnica de divide-y-vencerás, obteniendo una complejidad del tipo O(n log n). Pero, ¿y si te digo que lo puedes resolver mediante un algoritmo lineal de O(n)? ¿Te animas a demostrarte a ti mismo lo buen programador que eres? Pista: la clave está en las sumas inferiores a cero.

Vamos a ver la solución:

function max_subarray2($A) {
   $mejorHastaAhora = $mejorDeAhora = 0;

   for ($i = 0; $i<count($A); $i++) {
      $mejorDeAhora += $A[$i];
      if ($mejorDeAhora < 0) {
         $mejorDeAhora = 0;
      }
      if ($mejorDeAhora > $mejorHastaAhora) {
         $mejorHastaAhora = $mejorDeAhora;
      }
   }

   return $mejorHastaAhora;
}

Tenemos dos contadores:

  1. mejorDeAhora, que lleva la suma parcial en curso.
  2. mejorDeTodos, que almacena el mejor resultado de todos los calculados. Si mejorDeAhora es superior a mejorDeTodos, actualizamos este último.

Como decíamos, la clave está en las sumas inferiores a cero: cada vez que una suma parcial baje de cero, reiniciamos el sumatorio “mejorDeAhora”: Recuerda que una de las precondiciones era que hubiera tanto números positivos como negativos, luego alguna suma de uno o más elementos debe ser superior a cero.

Si además hacemos uso de la función max() disponible en la mayoría de lenguajes de programación, nos quedaría así de sencillo:

function max_subarray3($A) {
   $mejor = $sumatorio = 0;
   for ($i = 0; $i<count($A); $i++) {
      $sumatorio = max($sumatorio+$A[$i], 0);
      $mejor = max($sumatorio, $mejor);
   }
   return $mejor;
}

Y así es como, mediante un poco de ingenio, hemos pasado de tener una función de orden cuadrático a orden lineal. Puedes hacerte una idea del impacto en rendimiento que puede tener esto en grandes volúmenes de datos.

¡Esperamos que hayas disfrutado de este post!

Flexbox, las nuevas interfaces flexibles de CSS3

Flexbox es la palabreja con la que se denomina al flexible box layout, que podríamos traducir como maquetación de cajas flexibles. ¿Y qué se esconde tras esto? Ni más ni menos que una nueva forma de maquetar interfaces mediantes CSS3.

Webshims: Polyfill para JavaScript

Webshims Lib es una biblioteca polyfill modular centrada en implementaciones preciosas de las características ya estables de HTML5, de manera que los desarrolladores puedan escribir código moderno, interoperable y robusto para todos los navegadores. Funciona sobre jQuery y Modernizr.

¿Pero qué es un polyfill?

Es un término acuñado por Remy Sharp que define una porción de código (o un plugin) que proporciona la base tecnológica que tú, como programador, esperas que ofrezca nativamente el navegador.

Por ejemplo, el propio Remy Sharp colgó un gist con un ejemplo de polyfill que permite que navegadores antiguos ofrezcan soporte a localStorage y a sessionStorage mediante las cookies. Fue a partir de este gist desde el que hace dos años comenzó el desarrollo de Webshims Lib.

Webshims Lib

Actualmente funciona sobre la mayoría de navegadores (incluso IE6), y su funcionamiento es vergonzosamente sencillo:

<!-- dependencies: jQuery + Modernizr with yepnope -->
<script src="js/jquery-1.7.1.js"></script>
<script src="js/modernizr-yepnope-custom.js"></script>

<!-- reference the base script -->
<script src="js-webshim/minified/polyfiller.js"></script>
<script>
   // implement all unsupported features || call polyfill
   // before DOM-Ready to implement everything as soon and
   // as fast as possible
   $.webshims.polyfill();

   // or load only specific features you need
   // $.webshims.polyfill('forms json-storage');

   $(function(){
      //use all implemented API-features on DOM-ready
   });
</script>

Características:

Ámbitos en eventos JavaScript

Últimamente mi buen amigo Álex me está animando a que dé una oportunidad a CoffeeScript, el preprocesador de JavaScript que más está triunfando. Hablando de todo un poco, hemos comentado que JavaScript tiene algunas peculiaridades que, cuando uno empieza a trabajar con él, le descoloca un poco. Por ejemplo, el hecho de que su orientación a objetos esté basada en prototipos. Otra de esas peculiaridades que han salido a relucir es el cómo se manejan los ámbitos en eventos JavaScript. O dicho de otra forma: ¿Dónde debería apuntar this cuando estamos en la función manejadora de un evento?

Sombras y degradados en CSS3

Esta vez no voy a hablar de nada nuevo. Muchos diseñadores y maquetadores web están ya incluyendo estos efectos a sus trabajos. Sin embargo, para mí son nuevos :) Los he utilizado con anterioridad pero muy brevemente, y sin tener muy claro qué hacían y por qué exactamente. Si quieres ir directo a los ejemplos, los tienes aquí. ¡Al lío!

Tipos de posts personalizados en WordPress

Wordpress es una maravilla de software. Nacido en 2003, actualmente es el gestor de contenidos más usado (53.9% de cuota de mercado). La clave de su éxito, en mi opinión, radica en su sencillez de uso, en su versatilidad, en ser un proyecto libre, y sobre todo en su comunidad de usuarios, que crean plugins para casi cualquier cosa que podamos imaginar.

¿Pero sabías que se pueden crear tipos de posts personalizados en los que alojar cualquier tipo de dato que se te ocurra?

Introducción a la programación en Facebook V

Quinta y última parte de esta guía introductoria al desarrollo de aplicaciones web sobre la Facebook Platform. Ya conoces el ecosistema de tecnologías de Facebook, sabes cómo crear distintos tipos de aplicaciones, y conoces el SDK JavaScript por completo. Hoy vamos a ver el PHP SDK.

Antes de seguir leyendo, puedes echar un vistazo a la página GitHub donde está alojado el proyecto PHP SDK, y desde donde te lo podrás descargar. Nosotros vamos a hablar sobre la última versión estable, la 3.1.0.

Introducción a la programación en Facebook IV

En la primera parte vimos una introducción a las tecnologías usadas para programar en Facebook. En la segunda, creamos una aplicación, y le añadimos algún Social Plugin y etiquetas Open Graph. En el tercero, nos zambullimos en el SDK JavaScript, y autenticamos al usuario en nuestra aplicación, le solicitamos permisos extra, publicamos en su muro, y mostramos algún diálogo.

Hasta ahora hemos trabajado sobre una aplicación que funcione sobre nuestra página web. Sin embargo, como ya sabes, Facebook nos da más opciones: aplicaciones en móviles, y aplicaciones dentro de Facebook. Hoy vamos a ver cómo crear una aplicación dentro de Facebook. Esto se hace mediante un canvas (iframe) en Facebook en el que se mostrará la página web que deseemos. Por supuesto, en esa página web podremos gestionar JavaScript, CSS y HTML como queramos.

Introducción a la programación en Facebook III

Tercera parte de esta guía de introducción a la programación de aplicaciones en Facebook. Si seguiste la primera y la segunda parte, a estas alturas ya le habrás perdido el medio a muchos de los conceptos clave (tipos de aplicaciones, SDKs, Social Plugins, Open Graph, XFBML, Insights). Pero hay otros conceptos igualmente importantes que todavía no conocemos. Hoy vamos a tratar la autenticación OAuth, el SDK de JavaScript a fondo, y veremos cómo crear diálogos.

Introducción a la programación Facebook II

Ok, el anterior artículo no estuvo mal; vimos una introducción conceptual a las piezas clave para la construcción de aplicaciones en Facebook. ¡Pero no llegamos a hacer nada! En este post vamos a construir algo sencillo, jugando con el SDK en JavaScript. Vamos a probar a mostrar algunos de los social plugins, usaremos Open Graph, y presentaremos dos nuevas tecnologías: XFBML y Facebook Insights. ¡Al lío!