Inteligencia y conocimiento versus fuerza bruta Leandro Rabindranath León

Este post es largo, pero leíble, enteramente o por partes. Leerlo de una sola pasada depende de tu ánimo, buffer y capacidad de cómputo ;-). El nivel de programación que necesitas no es alto; sólo debes conocer un poco de árboles binarios de búsqueda, al menos como idea. Si prefieres leerlo por partes, entonces hazlo así.

Por si acaso te es útil, antes de comenzar colocaré un índice, de manera que puedas saltar directamente a la sección que te interese.

El post tiene dos propósitos. El primero es mostrar, mediando un simple ejemplo de programación en la vida real, la importancia de conjugar inteligencia y conocimiento y cómo esta comunión es más efectiva que la fuerza bruta. Mi segundo propósito está bastante vinculado al primero: mostrar la importancia de que el conocimiento sea compartido entre todos los seres humanos. Si no fuera porque el conocimiento se comparte, nuestro mundo actual sería muy distinto, pues sin conocimiento o, mucho peor, con conocimiento errado, la inteligencia no tiene mucha posibilidad ante la fuerza bruta, sea esta natural o cultural.

¿Por qué este doble propósito? Porque nadie puede llegar a ser un auténtico programador, y en realidad nada de nada, si no se comparte el conocimiento.

El ejemplo de programación del que me valdré es bastante simple: el cálculo de la moda en versiones secuenciales y paralelas. Debe ser sencillo para poder mostrar bien los bemoles del conocimiento inteligente aplicado y la fuerza bruta. Sin embargo, por más sencillos que éstos sean, creo que los algoritmos que presentaré son de interés, así como los razonamientos de diseño.

Los códigos hacen uso de la biblioteca Aleph-w.

Contents

• 1  Introducción
• 2  El contexto
• 3  La moda cándida
• 4  La cándida moda paralela
• 5  La inteligente moda
  • 5.1  La inteligencia y los instrumentos
  • 5.2  El conocimiento (mangos bajitos y mangos altos)
  • 5.3  El aplicar inteligentemente el conocimiento
  • 5.4  La solución
  • 5.5  La evidencia
    • 5.5.1  La evidencia concreta abstracta
    • 5.5.2  La evidencia concreta concreta
• 6  Sobre una versión paralela inteligente
• 7  Los mangos y el conocimiento

1  Introducción

Dicen que el futuro de la programación está en el paralelismo, lo que a mi juicio es completamente cierto. Algún día, creo que más cercano que lejano, se programará en paralelo y probablemente el paradigma secuencial quedará en el olvido.

Pero cuando llegue ese día, como sucede desde tiempos inmemoriales, seguirá prevaleciendo la inteligencia y el conocimiento sobre la mera fuerza bruta.

En este contexto, el calificativo bruto no tiene nada que ver con violencia, estupidez o torpeza. El calificativo bruto refiere a la ausencia o poca influencia de la inteligencia, lo que a menudo proviene de la falta de conocimiento. Y es que la mayor parte de las veces la inteligencia no tiene sentido sin conocimiento.

Se puede ser muy inteligente, pero si no se tiene el conocimiento gana la fuerza bruta. Se puede tener conocimiento, pero si no se aplica inteligentemente, gana la fuerza bruta. En realidad, inteligencia y conocimiento no son tan fácilmente separables, pero, en pos de la compresión, en este momento vale la pena pensarlos por separado.

Por supuesto, a veces la fuerza bruta es tan abrumadora que se puede perder aun siendo inteligente, conociendo bastante y aplicando lo que se conoce inteligentemente.

La fuerza puede emplearse inteligentemente y con conocimiento. Muchas veces mejor, pero no necesariamente ideal.

El conocimiento debe ser verdadero y quien es inteligente se asegura de ello; es decir, de que lo que conozca tenga asidero mostrativo y no sea un prejuicio.

Hay una especie de espada de doble filo entre la fuerza bruta versus la inteligencia. La gran ventaja de la fuerza bruta es que puedes usarla rápidamente, casi inmediatamente. La desventaja de la inteligencia y conocimiento es que a menudo necesitas más tiempo para ejercerla; tiempo para pensar y encontrar al genio. Esta es una muy buena razón para estudiar y buscar conocer más.

Digan lo que te digan sobre el determinismo, la suerte existe. Aun si la cosa en realidad fuese determinista, puesto que no lo puedes saber todo, siempre dependerás de lo que sucede en todo aquello que ignoras. A efectos prácticos, esto es lo mismo que la suerte. Y la lección es la misma, a siempre tener en cuenta: aun teniéndolo todo para ganar se podría perder o quedarse bloqueado.

2  El contexto

En un curso de programación paralela se asignó como tarea el diseñar e instrumentar el cálculo de la moda de un conjunto de números almacenados en un archivo. El programa más rápido obtendría la nota más alta.

Por si acaso no lo sabes o recuerdas, la moda es el valor del elemento que más se repite.

Te voy a revelar el final de la película: ganó un estudiante estudioso que conocía bien de algoritmos y estructuras de datos. Combinó inteligentemente una buena estructura de datos con un simple barrido en un solo procesador y superó, por mucho, a los algoritmos paralelos con muchos procesadores.

La “fuerza bruta” fueron los a las plataformas paralelas y los algoritmos diseñados para meramente explotar esta fuerza bruta.. La “inteligencia y el conocimiento” fue el estudiante que escribió su programa secuencial, pero que tomó decisiones prácticas inteligentes, a partir de lo que bien conocía y aplicó inteligentemente sus conocimientos para obtener una solución considerablemente mejor que la de la fuerza bruta.

Cuestión de satisfacer curiosidades y de dignidad al crédito, comento que el estudiante fue Alejandro Mujica.

¿Cómo hizo?

3  La moda cándida

Siempre le he recomendado a mis estudiantes noveles que estudien muy bien cómo uno mismo resuelve el problema. Si tienes un conjunto, ¿cómo determinas el elemento que más se repite? Fácil, revisa cada elemento y cuentas sus ocurrencias. A medida que vas haciéndolo, vas memorizando el elemento que más se te ha repetido; los demás, podrías olvidarlos, pues el resultado que deseas es el que más se repite. Al final tendrás el que más se repite; la moda.

Esta es una manera simple de contar las ocurrencias de un elemento en un arreglo:

int count_number(DynArray<short> & a, short number)
{
  int count = 0;

  for (int i = 0, n = a.size(); i < n; ++i)
    if (a.access(i) == number)
      ++count;

  return count;
}

Para calcular la moda, revisamos cada elemento del arreglo, lo contamos y nos quedamos con el mayor. He aquí cómo se puede hacer:

Aleph::pair<int, int> mode(DynArray<short> & a)
{
  int max_freq = 0;
  Aleph::pair<int, int> ret_val = -1;

  for (int i = 0, n = a.size(); i < n; ++i)
    {
      short num = a.access(i);
      int freq = count_num(a, num);

      if (freq > max_freq)
        {
          max_freq = freq;
          ret_val = Aleph::pair<int, int>(num, freq);
        }
    }

  return ret_val;
}

Se retorna un par contentivo de la moda y de su frecuencia de aparición. Conocer la frecuencia tiene utilidad estadística, pero también nos ayudaría a cotejar el resultado con otro algoritmo que encuentre otra moda.

Este “cándido” pero efectivo algoritmo revisa en su for todos los elementos del arreglo. El barrido consume O(n) iteraciones.

Dentro del for se llama a la rutina count_number(), la cual también barre enteramente el arreglo, por lo que es O(n).

Así la cosas, nuestro cálculo cándido de la moda es O(n)×O(n) = O(n²).

La efectividad siempre prima a la eficiencia. Obtener la solución es esencial antes que nada y muchísimas veces suficiente. Pero si estás compitiendo o el tamaño del conjunto es muy grande, entonces podrías estar consciente de que este algoritmo, aunque efectivo, no es muy eficiente a medida que n aumenta.

Dicen que el conocimiento se fundamenta más en preguntas que en sus respuestas. La actitud inteligente es preguntar; la inteligencia es encontrar una buena pregunta, una tal cuya respuesta nos revele.

Una pregunta inteligente podría ser: ¿Cómo mejorar este algoritmo? Saltemos la pregunta y dejémosla abierta, pues yo creo que saltar esta pregunta fue el error que algunos cometieron.

4  La cándida moda paralela

La manera cándida de paralelizar el algoritmo cándido es usar cada procesador como un agente contador. Si tenemos, por ejemplo, 64 procesadores, entonces podemos caminar de 64 en 64 por los elementos del arreglo y así acelerar la rutina mode().

Grosso modo, suponiendo, por simplicidad, que cada procesador se refiere como cpu[i ], que tenemos N procesadores y un compilador suficientemente inteligente como para detectar que la instrucción marcada con (**) se hace en paralelo (cuestión perfectamente factible), seria algo así:

Aleph::pair<int, int> mode(DynArray<short> & a)
{
  int max_freq = 0;
  int freq[N];
  Aleph::pair<int, int> ret_val[N] = -1;

  for (int i = 0, n = a.size(); i < n; i += 64)
    {
      freq[i] = cpu[i] . count_num(a, num); // (**)

      for (int k = 0; k < N; ++k)
        if (freq > max_freq)
          {
            max_freq = freq;
            ret_val = Aleph::pair<int, int>(num, freq);
          }
    }

  return ret_val;
}
 

Este código, que no dista mucho de uno real, es equivalente a realizar n/N pasadas en lugar de las n Así por ejemplo, si tenemos 1024 números y 64 procesadores, entonces, el lugar de realizar 1024 pasadas sólo hacemos 16, más un poco de coste por el for k=0..., el cual es constante.

De 1024 a 16 es una rebaja considerable. Parecido, si n=4096 entonces sólo hacemos 64 pasadas. Si n=2²⁰ = 1048576 sólo hacemos 16384 pasadas.

La verdad es que en apariencia la mejora parece ser substancial. Sin embargo, si analizamos con más rigor el algoritmo, entonces podríamos percatarnos de que la cantidad de procesadores, por mayor que ésta sea, siempre será una constante. Consecuentemente la complejidad de este algoritmo es 1/NO(n)×O(n) = O(n²). Por muchos procesadores que podamos tener, la eficiencia asintótica del algoritmo seguirá igual ... casi de la misma manera en que la fuerza bruta no ayudará mucho si no hay inteligencia y conocimiento.

5  La inteligente moda

Veamos ahora cómo pudo haber razonado nuestro estudiante.

5.1  La inteligencia y los instrumentos

Para comenzar, nuestro estudiante se planteó la pregunta ¿cómo puedo mejorar el algoritmo cándido?. A lo cual él se respondió: anoto en una hoja de papel los valores de los elementos del conjunto junto con su frecuencia; cada vez que reviso un elemento, lo busco en la hoja de papel, si ya se encuentra, entonces incremento su frecuencia, si no, lo anoto con frecuencia 1. Con este simple truco se efectúa una sola pasada sobre el conjunto y varias sobre la hoja del papel. Al final, efectúo una última pasada sobre el papel para buscar y encontrar el elemento con más frecuencia.

El razonamiento anterior es el primer detalle de inteligencia. Consistió en encontrar un instrumento que le ayudase a resolver su problema: la hoja de papel. ¿Cuáles son las ventajas de este instrumento? Observemos, en primer lugar, que sólo se realiza una pasada por el conjunto, una sola y no más. El resto de las revisiones se efectúan sobre la hoja de papel. Qué tan buena es la idea depende de conocer la relación entre el total de números y el total que anotaríamos en la hoja de papel. Puesto que estamos calculando la moda, parece lógico esperar que unos cuantos número estén repetidos; si no, ¿para qué determinar la moda?. Así pues, el mero problema de calcular la moda ofrece una clara indicación de que la cantidad de números y frecuencias que guardaríamos en la hoja de papel es menor que el total de números. Por consiguiente, a condición de que todos los pares <elemento,frecuencia> quepan en la hoja de papel, es más rápido usar la hoja de papel que no usarla.

Obviamente, como instrumento la hoja de papel tiene un límite de escala. Si tuviésemos que calcular la moda entre un conjunto de un millón de números, entonces nos sería muy difícil y laborioso emplear la hoja de papel (probablemente serían varías). Pero casi igual o más de difícil y laborioso sería hacerlo sin la hoja de papel. Y aquí subyace una idea muy importante: la de instrumento, pues muchas veces la solución de un problema estriba en encontrar o fabricar el instrumento adecuado. Si el medio “papel” no fuese suficiente como instrumento, entonces podríamos usar o crear un instrumento que cumpla el mismo fin pero que sea más eficiente.

Una vez que se nos revela la hoja de papel como instrumento, tienen sentido preguntas como ¿cómo encontrar lo más rápidamente posible un número en la hoja de papel? y ¿cómo anotarlo lo más lo más rápido que se pueda?.

Algunos dicen que la inteligencia consiste en encontrar o inventar instrumentos y luego saber aplicarlos. Si bien yo no creo que esto defina toda la inteligencia, no me cabe la menor duda de que es parte importante de la inteligencia.

5.2  El conocimiento (mangos bajitos y mangos altos)

Resulta que en lo instrumental mucho intervienen el conocimiento y la experiencia.

Debería yo ahora mostrar dónde y cómo interviene el conocimiento. Pero para ello, yo quisiera estar más seguro de que se entienda qué es el conocimiento. Con ese fin, plantearé el ejercicio primitivo y actual de tomar frutos del mango.

Hubo una primera vez en que se acabaron los “mangos bajitos”. El Hombre se quedada sin mangos durante más tiempo mientras veía pudrirse a los altos, los que no podía alcanzar con su estatura. Pero hubo también una primera vez en que a alguien se le ocurrió emplear una vara larga para alcanzar los mangos altos. Se inventó un instrumento ... o se descubrió ... que es casi lo mismo. Luego de aquel descubrimiento, quienes ya conocían la existencia del instrumento y tenían a su alcance una vara jamás volvieron a ver pudrirse a los mangos altos (aunque probablemente, si fueron consumistas, tuvieron que esperar igual o más tiempo, que antes del descubrimiento de la vara, pues se los comieron más rápido). Un poco después del descubrimiento de la vara aparecieron tres tipos o grupos nuevos de personas: (1) las que pensaban cómo hacer varas más altas, mejores o más eficientes, (2) las que pensaban cómo mejor usar las varas para tomar los mangos altos y (3) las que pensaban en otras maneras distintas, con otros instrumentos, existentes o no, de alcanzar los mangos altos.

El caso de los mangos nos permite identificar varios tipos de conocimiento (hay más, pero estos son lo que nos competen en este momento):

• Conocimiento de tipo 1: la existencia del instrumento.
• Conocimiento de tipo 2: cómo se usa el instrumento.
• Conocimiento de tipo 3: cómo se hace el instrumento.
• Conocimiento de tipo 4: cuáles otros instrumentos sirven para el mismo el fin.
• Conocimiento de tipo 5: otros usos o fines del instrumento (a veces peligroso).
• Conocimiento de tipo 6: otros instrumentos que aún no han sido completa o del todo descubiertos.

Todos estos tipos de conocimiento son muy importantes en el mundo ingenieril.

Regresemos al problema de la moda y cómo se aplica inteligentemente lo que se conoce.

Aparte de la inteligencia de encontrar un buen instrumento, nuestro estudiante tenía bastante conocimiento sobre algunos tipos de instrumentos cuyo fin en la algorítmica y programación es muy similar al de la hoja de papel: estructuras de datos para la búsqueda (conocimiento de tipo 1). Él conocía la interfaz general del problema fundamental de estructura de datos (conocimiento de tipo 2), así como también varias estructuras de datos que lo resuelven muy bien: tablas hash y diversos tipos de árboles de búsqueda (conocimiento de tipo 4).

Nuestro estudiante no se hubiese bloqueado por ausencia de conocimiento de tipo 3, pues él sabe cómo se hace cada uno de los tipos de instrumento que hemos mencionado.

5.3  El aplicar inteligentemente el conocimiento

Como el estudiante estaba muy distante de tener suficiente tiempo, él no se preocupó por inventar un nuevo instrumento (conocimiento de tipo 6). Como tenía claridad práctica: sabía perfectamente cuál era su problema y cómo resolverlo, no se distrajo peligrosamente en otros instrumentos o problemas parecidos (conocimiento de tipo 5).

Por decirlo de una forma, su primer dilema práctico fue decidir entre dos grandes tipos de papel: una tabla hash o un árbol binario de búsqueda. Las tablas hash prometen O(1) mientras que los árboles garantizan O(lgn). O(1) es mejor que O(lgn), pero, puesto que el primero es una promesa y el segundo es una garantía, nuestro estudiante apeló a su inteligencia para dilucidar su dilema y lo reformuló bajo la siguiente pregunta ¿qué es mejor, un probable O(1) o un seguro O(lgn)?. La pregunta es inteligente porque revela otro asunto práctico: el O(1) de la tabla hash es probable, pero no es seguro. Al revelársele esto, nuestro estudiante se dio cuenta de que para estar seguro de poder ganar con una tabla hash tenía que indagar cuán probable es el O(1).

Surgió pues la pregunta: ¿que tan probable sería el O(1) de su tabla? Su inteligencia directamente le indicó varias desconocimientos: no conocía el tamaño de la entrada, ni tenía idea de su patrón, ni cuántas repeticiones habría. Este es un tipo de conocimiento extraño, a veces paradójico y sorprendente, pero muy importante. Es el conocimiento de lo que no se conoce o, quizá sea más apropiado decir en este caso, es la conciencia de. Lo fascinante es que esta conciencia se gana mientras más se conoce. Mas uno conoce, más uno sabe que no conoce nada.

En una tabla hash es indispensable una buena función hash; si no, la promesa O(1) se derrumba de entrada. Con claves numéricas, cual es el caso, es muy fácil y directo usar el propio número como función hash. Pero aquí intervino la conciencia de lo que no se sabe. Veamos.

Toda buena función hash debe “dispersar”, “desordenar” y “ser lo más impredecible” posible. Pero para poder lograr esta emulación de lo impredecible, hay que conocer cómo se construye el conjunto de claves. Conocer el patrón en que se presentan las claves es esencial para diseñar una función hash que comience por romper ese patrón. Ahora bien, en el caso de la moda y los números, ¿cómo podía conocer nuestro estudiante la manera en que se generaría el conjunto de números? No tenía este conocimiento a su alcance, pero sí conocía el riesgo de la multiplicidad en común que pueden tener dos números distintos. Sabía que este riesgo se evade escogiendo un tamaño de tabla primo. Pero, ¿cuál primo? si para empezar no conocía el tamaño de la entrada ni tenía mayor aproximación a éste que la cantidad de memoria disponible,

Luego de todas estas breves reflexiones, nuestro estudiante eligió sin mayor aprensión, un “completamente seguro O(lgn)” en lugar de un “no sé que tan probable O(1)”. Escogió usar árboles binarios basado en lo que de seguro conocía.

La conciencia de lo que no se sabe es muy importante en la toma de buenas decisiones. Una buena decisión no garantiza la solución, pero hay mucho más probabilidad de encontrarla con buenas decisiones que con decisiones incorrectas o malas.

Una decisión incorrecta es aquella en la cual la razón está más dominada por lo desconocido que por lo conocido. En esta categoría encajan decisiones dominadas por conocimiento que no es relevante para el problema. A veces, especialmente en situaciones contingentes y urgentes, se debe decidir en lo desconocido. Pero es labor de todo ingeniero -y en general de cada quien-, hacer el máximo esfuerzo por decidir sobre lo conocido. Parte del arte de la guerra es hacer que el adversario decida por lo desconocido o por conocimiento errado, a veces por ignorancia, pero mucho más por engaño.

Una mala decisión es aquella en que el conocimiento que la sustenta es falso o no es relevante para el problema. Esto es grave y sucede más a menudo de lo que uno se imagina.

Por supuesto, desconocemos casi todo. Pero en aquello en lo cual tenemos responsabilidad y decisión debemos hacer todo lo posible por conocer lo mejor. Siempre habrá incertidumbre, pero a mayor conocimiento, mayor es la posibilidad de solución.

¡El conocimiento! Gracias a que lo tenía bien aprendido, nuestro estudiante decidió inteligentemente por el instrumento “árbol binario de búsqueda”. Creo que pudo haber decidido por una tabla hash y a lo mejor le hubiese ido mejor. Pero prefirió apostar a lo seguro en lugar de lo más probable.

Finalmente quedó un último dilema práctico: decidir fabricar el instrumento o usar uno ya existente. Si tienes una vara larga cercana al árbol de mango, ¿para qué alejarse a buscar otra vara? Usa la que ya tienes y todos los mangos serán bajitos. Así, a pesar de que él sabía cómo hacer el instrumento, decidió utilizar uno ya hecho. En el caso de la estructura de dato, transó por una en biblioteca (la Aleph-w).

El problema ya estaba resuelto.

5.4  La solución

Vamos a ver directamente la solución:

    template <template <class, class> class Tree>
Aleph::pair<int, int> tree_mode(std::ifstream & file)
{
  DynSetTree<Tree, Number_With_Frequency, Cmp> tree;

  while (not file.eof())
    {
      int n; 
      file >> n;
      if (not file.eof())
        {
          Number_With_Frequency nf(n);
          Number_With_Frequency * __nf = tree.search(nf);
          if (not __nf)  // Si no existe inserto
            tree.insert(nf);
          else // Sino incremento frecuencia
            ++__nf->f;
        }
    }

  Number_With_Frequency _nf(0);
  tree. template for_each <Op> (&_nf);

  return Aleph::pair<int, int> (_nf.n, _nf.f);
}
 

La primera cosa a notar es que la rutina es una plantilla (template); su parámetro es la clase de árbol binario de búsqueda que se emplearía para guardar los pares. La segunda es que la rutina lee los números desde un archivo y no desde un arreglo. En realidad, para resolver el problema con un arreglo, primero debemos cargar los números desde el archivo; si calculásemos la moda desde un archivo entonces sería mucho más lento. Ahora bien, si usamos el instrumento entre el disco y la memoria, o sea, el árbol binario de búsqueda, entonces, como elproblema se ha trasladado hacia el instrumento, sólo requerimos leer los números una sola vez. Por tanto, podemos leerlos directamente desde el archivo.

Para aquellos que no tengan familiaridad con Aleph-w, debo explicar la primera línea de la rutina:

• DynSetTree es una clase que modeliza un conjunto de claves. La clase es una plantilla con tres parámetros: la clase de árbol binario de búsqueda, el tipo de clave y la función de comparación entre las claves.
• Number_With_Frequency es el par <número,frecuencia> definido así:

  struct Number_With_Frequency
  {
    int n; // el número
    int f; // la frecuencia o cantidad de veces que aparece
  };
   

  El criterio de comparación se encargará de sólo considerar n.

El while tiene el mismo rol que el for en la versión para arreglos y es O(n). Lo que está dentro del if del while es una operación sobre el árbol, que está acotada por O(lgn). Por tanto, todo el while es O(n)×O(lgn) = O(n lgn).

Cuando se termina el while, tree contiene todos los elementos del archivo junto con sus frecuencias. Sólo nos queda una última pasada sobre el árbol y no sobre el archivo. Esta pasada es O(n). Por tanto, el algoritmo es O(n) + O(n lgn) = O(n lgn). Una cota con creces mejor que O(n²) de las previas y brutales versiones secuencial y paralela.

Un comentario particular con la línea:

 tree. template for_each <Op> (&_nf);
  

for_each <Op> (&_nf) es un método plantilla de la clase DynSetTree que recorre todos los elementos del conjunto (DynSetTree) y aplica la operación Op, que el parámetro plantilla del método. El parámetro de for_each <Op> (&_nf) es de tipo void*, por el cual se le puede pasar a la operación datos de entrada y salida. Op recibe como parámetro la clave que se está revisando y un parámetro opaco de tipo void* ; en este caso un par donde se guardará el par con mayor frecuencia. Así, la operación se define así:

struct Op
{
  void operator () (Number_With_Frequency & nf, void * ptr)
  {
    Number_With_Frequency * n = (Number_With_Frequency*) ptr;
     if (nf.f > n->f)
       {
         n->f = nf.f;
         n->n = nf.n;
       }
  }
};
 

Notemos la palabra template en la llamada al método tree. template for_each <Op> (&_nf). Debemos colocar este prefijo (template), porque en ese momento de la compilación el compilador no tiene manera de saber que el objeto tree de tipo clase Tree tiene un método llamado for_each(). No lo puede saber porque Tree es una plantilla y el valor exacto de sus métodos se sabrá cuando ocurra una instanciación. Al antecederle template a for_each() estamos recordándole al compilador que for_each() es una plantilla y que no sea muy quisquilloso con la verificación de nombres (no lo puede ser). Dije “recordándole” porque aunque el compilador no conoce los métodos que tiene Tree y su instancia tree, él sí conoce que tree es una plantilla.

Hay una mejora substancial sobre este algoritmo. Como ves, se efectúa una búsqueda y, si la clave no se encuentra, se efectúa una inserción. Ahora bien, puesto que la inserción requiere una búsqueda fallida y ya tenemos una hecha, podría modificarse la interfaz del árbol para que guarde la última búsqueda a efectos de ahorrarla si ocurre una inserción

Debe notarse que el consumo en espacio de nuestro algoritmo es O(n), mientras que el de las versiones brutales es O(1). Después de todo, todo instrumento pesa y consume energía hacerlo y usarlo. Aunque presumo que este peso es mucho menor, al menos en costes económicos, que el de los 64 procesadores.

5.5  La evidencia

El sentido común recomienda no asumir un conocimiento como verdadero si no se tiene evidencia concreta de su veracidad. Muchísimo más de lo que creemos, creemos en mucho conocimiento sin evidencia. Si no me crees, piensa en la gran cantidad de cosas que asumimos como ciertas por el mero hecho de que alguien nos dijo que eran ciertas. ¡Piensa bien!

Una de las bondades de ser ingeniero es que se vive entre dos mundos de búsqueda de conocimiento más o menos opuestos: el racionalismo y el empirismo. Muy grosso modo, los racionalistas adoran lo abstracto mientras que los empiristas lo concreto. Cada uno de estos mundos tiene sus pros y cons y merecen respeto.

Nosotros, los ingenieros, tratamos de mediar entre estos dos mundos. Por eso, bien podría decirse que somos intelectualistas.

Como nos movemos entre estos mundos, podemos manejar varias clasificaciones del conocimiento: (1) abstracto abstracto, o sea vivir en las nebulosas (y se puede ser auténticamente útil y feliz allí); (2) abstracto concreto: una abstracción bien dominada (3) concreto abstracto: un conocimiento desde lo abstracto (racional), pero a menudo sin contacto con la realidad y (4) concreto concreto: un conocimiento desde lo concreto, pisando o aterrizando (suavemente) en tierra.

5.5.1  La evidencia concreta abstracta

Concretemos conclusión desde aquel mundo abstracto que llamamos el ∞ (infinito), cual es en donde se cumplirían las promesas de un análisis asintótico y preguntémosnos: ¿por qué O(n lgn) = O(n)× O(lgn) es mucho mejor que O(n²) = O(n) × O(n)?,

Saquemos lo común, que es O(n), lo que simplifica la pregunta ¿por qué es mejor O(lgn) que O(n)?. Para mí la respuesta es directa. Un algoritmo O(n) consume tiempo directamente proporcional a n; si tengo 2²⁶ números entonces gastaré k 2²⁶; si tengo 2²⁷ = 2 × 2²⁶ números entonces gastaré k 2× 2²⁶ = k 2²⁷; o sea, se duplica la cantidad y entonces la duración se duplica proporcionalmente.

En el caso de un algoritmo O(lgn), para que la duración aumente en una unidad de tiempo, la entrada debe duplicarse. Si tengo 2²⁶ números entonces gastaré k lg(2²⁶) = 26 k; pero si tengo el doble, o sea 2²⁷ números entonces gastaré 27 k; sólo una unidad de tiempo más.

En lo concreto abstracto, es demasiado evidente que O(lgn) es mejor que O(n).

5.5.2  La evidencia concreta concreta

Algunos al final necesitan lo concreto concreto para convencerse; especialmente los empiristas. En cambio, los ingenieros podemos manejarnos en lo concreto abstracto mientras estudiamos y diseñamos. Pero a menos que se trate de una situación desesperada y contingente, la guerra por ejemplo, un buen ingeniero no se casa con la realización de un proyecto sin conocimiento concreto concreto.

Lo concreto concreto refiere al mundo real, aquel en el cual vivimos y que los ingenieros tendemos muchísimo a despreciar, muchas veces inconscientemente. Para obtener conocimiento concreto concreto requerimos hacer experimentos o estudiar la experiencia. Experienciar con lo que sería real, “jugar” en condiciones reales y no abstractas. A los racionalistas les incomoda la experiencia, a los empíricos lo abstracto, pero los ingenieros no sólo podemos aceptar los dos modos, sino que es ingeniería manejarse en los dos.

En el caso de nuestro problema ejemplo, lo concreto concreto debemos descubrirlo o comprobarlo en el cálculo de la moda. Dejando a un lado muchísimas consideraciones, entre ellas, por ejemplo, si vale o no la pena la inversión económica en un computador paralelo, lo que estudiaremos, real o realísticamente, es la ejecución concreta de nuestros tres algoritmos.

Nuestra plataforma de experimentación es un computador basado en un Intel Core(TM) 2 Duo CPU E7400 a 2.8Ghz y 4 GB de ram. Este es nuestro piso real, donde experimentaremos con nuestros diseños. Aquí podemos probar realmente la moda cándida y la moda inteligente, mas no, “realmente”, la moda cándida paralela, pero sí, “realísticamente”.

El no disponer de una plataforma exacta a la real no necesariamente impide que ésta no se pueda emplear para experimentar “realísticamente”.

En ciencias e ingeniería se experimenta “realmente” o “realísticamente”. Por ejemplo, se puede probar realmente el diseño de un avión construyendo uno, volándolo, midiendo datos y armando información que dé conocimiento. Al fin de cuentas, si el diseño es bueno y se reúnen un montón de condiciones, esto ocurrirá y deberá de hacerse. Pero si se está en una etapa de diseño, se pueden hacer experimentos realistas, es decir, experimentos que no se hacen sobre el diseño real, porque no se tiene, no se puede, no se quiere, es muy costoso o es innecesario, sino sobre una plataforma modificada que emule la realidad. En el caso del avión, se podría modificar uno ya existente, añadirle funcionalidades del nuevo diseño; también podríamos construir uno a escala reducida, manejable física y económicamente, y experimentar con él.

Para poder estudiar empíricamente la moda cándida paralela, debemos hacer experimentación realista pero no real, pues, en mi caso particular, no tengo directamente a mi alcance una plataforma paralela. Y aquí debe verse la importancia del conocimiento concreto abstracto. Fíjate.

Aunque no conocemos una función que caracterice precisamente a la duración de ejecución de la moda cándida paralela, sí conocemos desde lo concreto abstracto un patrón general que la describe: la cota O. Al respecto, sabemos que la moda cándida paralela es O(n²). También sabemos, por inspección del algoritmo en § 4, que éste es algo proporcional a la duración de la moda cándida § 3 dividida entre el número de procesadores. Consecuentemente, podemos estudiar realísticamente la moda cándida paralela § 4 dividiendo la duración real de la moda cándida entre el número de procesadores.

Así las cosas, para aproximarme al conocimiento concreto concreto de la duración de la moda cándida paralela, dividiremos la duración real de la moda cándida entre 64, que es una cantidad de procesadores aceptablemente grande.

Cuando se hace experimentación realista, es importante manejar cotas inferiores y no superiores. En este sentido, la aproximación que hacemos a la duración de la moda cándida paralela es proporcionalmente menor que la duración real que tendría si se ejecutase en un computador paralelo con 64 procesadores. De la inspección del algoritmo en § 4 te das cuenta que estamos saltando las pasadas secuenciales para decidir la moda actual calculada por los N procesadores. También nos estamos saltando otros costes de sincronización. Nuestra aproximación realista no es exacta a la duración real, pero es de seguro menor (la cota inferior), por eso es realísticamente útil para compararla con las otras versiones secuenciales.

Con todo esto en mente experimentamos con distintas escalas entre de 10³ y 10⁷ conjuntos de números generados al azar.

La moda cándida aborta por falta de memoria para el arreglo a partir de 10⁷ números. De todos modos, si se pudiese, entonces tendríamos que esperar bastante.

Una posible solución sería calcularla desde el archivo, pero esto sería extremadamente mucho más leeeeeeento.

La moda inteligente emplea una estructura de datos (el árbol binario) esparcida en memoria, la cual, aunque en suma consume más memoria, tolera mejor la fragmentación.

Así que para estimar una duración de las modas cándidas a escala 10⁷, de nuevo aplicaremos el conocimiento concreto abstracto O(n²) . Para estar más seguros de nuestra estimación, la cotejamos con las duraciones previas. La siguiente tabla resume el asunto:

n=10k	Duración real moda cándida (dk)	Cuadrado duración n=10k−1: dk−12/64	Duración realista
103	9 ms	-	140 µs
104	428 ms	1.27 ms	6.69 ms
105	42.547 s	2.86 s	0.664 s
106	71 m con 14.747 s	30.17 s	230 ms
107	712 ≈ 84	712/64 ≈ 78.77 m ≈ 1.31 h	No ejecuta

La estimación de interés se muestra en la última fila, pero son las anteriores las que nos permiten verificar. Puesto que son pocas, podríamos comentarlas una a una, pero como veremos inmediatamente lo que nos interesa es la tendencia. La primera fila no es en si relevante; sólo sirve de referencia para construir la estimación de la segunda. A partir de la segunda fila notamos algo muy interesante: la duración realista es mayor que la duración estimada d_k−1²/64; lo mismo ocurre con las siguientes. Esto es muy importante, pues, el conocimiento concreto concreto elementalmente nos dice que las funciones de los algoritmos § 3, § 4 y § 5.4 son monótonas crecientes. Siempre, a mayor entrada, mayor duración. Por esta razón, estimar una cota de duración de la moda cándida paralela en 10⁷ mediante d_k−1²/64 tiene sentido. Igualmente, todas los valores de d_k−1²/64 son menores que los realistas, los cuales a su vez son menores que los reales. Así, nuestra estimación para la duración con n=10⁷ números es una cota inferior, por tanto realista.

Otra manera de hacer la estimación, más concreta concreta, consiste en emular a través de un programa derivado de § 3 el cálculo. Nuestro programa no calcularía la moda, pero sí haría las repeticiones necesarias para tener una aproximación. Puesto que es más rápido y, como veremos inmediatamente, suficiente, preferimos la estimación fundamentada en la tabla anterior.

Ahora comparemos nuestros números concretos y concretemos conocimiento:

n	Moda cándida	Moda cándida paralela (Moda cándida/64)	Moda inteligente
103	9 ms	140 µs	4 ms
104	428 ms	6.69 ms	6 ms
105	42.547 s	664 ms	20 ms
106	71 m con 14.747 s	66.79 s	230 ms
107	≈ 84 h	≈ 1.32 h	3.364 s

Como se puede apreciar, la moda inteligente es con creces mucha más rápida que la moda cándida paralela. Esto se aprecia a partir de la 2da fila, pero conforme miramos las siguientes, la superioridad es abrumadora.

El conocimiento concreto concreto, o la realidad concreta, demuestra con creces una situación en la cual el conocimiento inteligentemente aplicado superó de lejos a la fuerza bruta.

Partimos desde lo abstracto concreto con conocimientos que aprendimos en nuestra formación de ingenieros. Rápida y peripatéticamente, en el tiempo en que demora una caminata, concluimos el conocimiento concreto abstracto de que un algoritmo secuencial que emplease como instrumento un árbol binario de búsqueda sería muy bueno. Finalmente, probamos y comprobamos en un plano concreto concreto de experiencia lo que ya sabíamos desde lo concreto abstracto. Lo que en un inicio comenzó abstracto devino concreto.

6  Sobre una versión paralela inteligente

¿Qué hubiera podido suceder si el problema se aborda desde el inicio con inteligencia y conocimiento sobre la algorítmica paralela?

Hay dos grandes enfoques para este estilo de pensamiento: (1) partir de una versión secuencial y estudiar cómo paralelizarla y (2) desde el principio pensar en paralelo. La primera hoy no es más simple y “natural”, pero hay fuertes razones para pensar que en el futuro prevalecerá la segunda. Lamentablemente no dispongo del tiempo (y sospecho que estas alturas tú tampoco) para explayar en qué consiste cada estilo; especialmente el 2do, el cual es al que probablemente no estés acostumbrado. Además, sucede que, en mi particular opinión, la moda no da mucho espacio para paralizarse según el 2do estilo.

Desde nuestros cursos sobre algoritmos conocemos la técnica dividir/combinar. Por lo general un algoritmo de este tipo es susceptible de paralelizarse; envías cada partición a un procesador distinto.

Supongamos un conjunto C = {e₁, e₂, e₃, …, e_n}. Podríamos dividirlo en dos C = C₁∪ C₂ ∣ C₁={e₁,e₂,…,e_n/2}, C₂ = {e_n/2+1,e_n/2+2…,e_n }. Podríamos calcular las modas m₁ y m₂ con frecuencias f₁ y f₂ de los dos conjuntos. Examinemos algunos escenarios:

1. Si m₁ = m₂ = m entonces probablemente esta sea la moda. ¡Probablemente!
2. Si m₁ ≠ m₂ entonces probablemente la moda es alguno de estos elementos. ¡Probablemente!

   Supongamos que f₁>f₂. Entonces m₁ tiene mayor probabilidad de ser la moda. Simétrico el negado. Si son iguales, entonces podríamos escoger uno y con 0.5 más de probabilidad sería una moda probable.

   Pero para estar seguros, podríamos examinar de nuevo las particiones y contabilizar el total. Esto tiene el problema de que recorre de nuevo el conjunto. Si caemos aquí, entonces es muy probable perder ante otro algoritmo, pues recordemos que la moda inteligente efectúa una sola pasada.

Si no fuera estrictamente necesario conocer la moda absoluta y pudiésemos conformamos con una moda probable, o sea, un elemento que se repite mucho pero que no necesariamente es el que más se remite, entonces esta técnica sería muy eficiente. Si se requiere la moda con certitud, entonces este camino no parece adecuado.

Por cada partición podríamos calcular un arreglo de los elementos que más se repiten y luego, en la fase de combinación, determinaríamos por sumas de frecuencia aquel de ellos que tenga la mayor probabilidad de ser la moda. Con esto lo que hacemos es aumentar la confianza de que el resultado en la moda, pero no la garantizamos.

Algoritmos de este tipo se denominan aleatorizados tipo Montercalo.

Cada fase del algoritmo aleatorizado podría emplear un árbol binario como la moda inteligente § 5.4. En este caso, aunque probable, o más probable si calculamos arreglos de los más repetidos, el algoritmo aleatorizado sería más rápido que la moda inteligente. Podríamos llamarlo “moda inteligente aleatorizada paralela”.

El razonamiento anterior es híbrido entre los dos estilos. Particionar data y recursos es parte del pensar en paralelo, pero lo hicimos desde nuestro conocimiento de un algoritmo secuencial.

Una crítica que se le podría hacer a la moda cándida paralela § 4 es que reparte el cómputo sobre los procesadores pero no reparte la data. Por eso es que el algoritmo es tan similar a la versión secuencial.

Hay una observación que puede sernos crucial, si queremos calcular con exactitud la moda, sin conocer la cantidad de elementos, entonces tenemos que inspeccionar todos los elementos. Si conocemos a priori la cantidad de elementos, tenemos una ligera ventaja, pues podríamos parar el calculo una vez que tengamos una moda segura.

Con lo anterior en mente, parece lógico tratar de paralelizar la moda inteligente. Una alternativa sería dividir el conjunto en C₁ ∪ C₂ ∪ ⋯ ∪ C_N; o sea, repartir los datos entre los N procesadores, los cuales comparten el árbol binario. En este caso deberíamos de asegurarnos de que el árbol soporte la coherencia ante operaciones concurrentes. Una manera simple de hacerlo es protegerlo con un simple semáforo binario. Pero esto causaría contención: un procesador debe esperar a que otro que esté usando el árbol lo libere para poder usarlo. La contención se puede mitigar considerablemente con un cerrojo lector/escritor: sólo se bloquean los escritores; los lectores pasan sin problema. Aquí probablemente habría poca contención, pues tanto la búsqueda como la inserción requieren buscar y ésta es una operación lectora. Sólo se modificaría la topología del árbol cuando se añada una nueva clave, lo que ocurre mucho al principio y poco hacia el final. De nuevo probablemente, pues estas consideraciones se hacen desde lo abstracto concreto.

Una alternativa más paralela aún es emplear un árbol por procesador. Puesto que al final de su pasada, cada procesador tendría todos los pares <número,frecuencia> de cada conjunto, podría dilucidar rápidamente la moda real. Este algoritmo sería bastante paralelo y su complejidad sería O(n/N lgn), lo cual sin duda, desde lo concreto abstracto, batiría a la moda inteligente que es O(nlg n). De pasapalo, no requiere protección para los árboles, pues éstos son manejados por un solo procesador. La fase secuencial de mirar todos los árboles es la parte delicada, pues requiere varias pasadas sobre los árboles cuya suma probablemente sería mayor que n. Para paliar esto, yo emplearía una 2da estructura de datos que me mantenga en a lo sumo O(lgn) las claves con mayores frecuencia. ¡Te invito ha desarrollarlo!

7  Los mangos y el conocimiento

Regresemos a nuestro hombre primitivo (en el sentido de la era; para nada de su inteligencia) y el momento en que él descubre que con una vara puede alcanzar los mangos altos. Llamemos a este hombre Jose.

Si Jose viviese solo y hubiese tenido muy poco contacto con otros hombres, entonces lo más probable es que él deje la vara cerca de donde la encontró (lo que probablemente no tendría nada de perjudicial), pues sus conocimientos serían sumamente concretos concretos: sólo los que le diese su experiencia. Jose tendría muy poco conocimiento abstracto. A veces es interesante y provocador preguntarse si no se más feliz en esta situación.

El Hombre existe como especie porque es Hombre y no un hombre; o sea, entre otras cosas, porque vive en comunidad. Vivir en comunidad tiene algo maravilloso, cual yo creo está posibilitado por el lenguaje: podemos compartir conocimientos. Pero hay más, podemos iniciar nuestra vida con base a conocimientos descubiertos por otros, independientemente del momento en que aquellos conocimientos fueron descubiertos. Aun más, hoy en día, desde que naces, comienzas a recibir una miríada de conocimientos cuya edad varía desde los milenarios a los muy recientes, como el uso de los blogs.

Algo que nos permite emplear conocimientos que no hemos descubierto, y que también inclusive nos permite entenderlos, es nuestra imaginación. Podemos imaginar la aplicación de los conocimientos sin ningún asidero de tangibilidad. Esta actividad es lo que yo llamo “abstracción”. Pero fíjate una cosa, para abstraer y aprender usamos muchísimo el lenguaje y cuando usamos el lenguaje compartimos. Nuestro poder de abstracción depende, entre otras cosas, de que lo que hayamos aprendido compartiendo.

A menos que hubiese sido sumamente fuerte y rápido, Jose hubiese perecido bajo las fauces de un diente de sable o lo hubiese aplastado un Mamut (y se lo hubiera merecido por egoísta). Pero como Jose nació en comunidad, a él no sólo se le hizo conocer lo que su instinto le decía sobre lo peligroso que podía ser el diente de sable o el mamut, sino que el aprendió a tomar distancia de estas amenazas; más aun, aprendió a defenderse e inclusive a cazarlos. No fue él solo quien aprendió, fue una larga historia de aprendizaje reiterativo de otros congéneres que lo precedieron, partiendo del plan concreto abstracto, pasando por ensayo concreto concreto y aprendiendo lecciones concretas abstractas/concretas.

Imagínate que Jose al descubrir la vara hubiese decidido no compartir su descubrimiento con otros. Para empezar, él hubiese tenido que alcanzar los mangos altos sigilosamente, sin que sus congéneres se percatasen de ello. Pero sus congéneres, que no serían idiotas, se hubiesen percatado de que algo estaba sucediendo con los mangos altos. Por otra parte, si sus congéneres le descubren su sigilo, entonces se abrirían las puertas para el conflicto.

Podría ocurrir que el razonamiento de Jose fuese que si él compartía el descubrimiento de la vara, entonces los mangos altos se agotarían rápidamente. A menos que fuese asunto de supervivencia, esta sería una actitud sumamente estúpida y egoísta, pues si Jose logra improbablemente terminar su vida tranquilamente sin que nadie descubra su secreto, no sólo nadie lo recordará por haber descubierto la vara, sino que su comunidad, incluidos sus queridos, no se beneficiarán del descubrimiento.

Algunos suelen ver en el egoísmo una actitud inteligente. Pero en el caso de Jose es una actitud bruta, pues va contra su comunidad, contra lo que le permitió a Jose, justamente, descubrir la vara y ocultar su descubrimiento. Pero también va contra su propio enriquecimiento, pues si Jose actúa encubiertamente, entonces se restringe beneficiarse del conocimiento de los otros. Por ejemplo, supón que la vara no sea suficientemente alta para alcanzar los mangos muy altos. En este caso, Jose tiene que trabajar solo y descubrir por si mismo otras técnicas e instrumentos. En comunidad, este tipo de actividad no sólo es mucho más fácil, sino que tiene sentido, pues Jose tiene más probabilidad de trascender más allá de su vida y de su comunidad compartiendo que ocultando.

Como en todo ámbito y tipo de ingeniería, para ser buen programador hay que ser inteligente. Ser inteligente es mucha medida de lo que se conozca. Para conocer es esencial compartir.

---

This document was translated from L^AT_EX by H^EV^EA.