Finalmente para analizar el caso promedio, decidí realizar una serie de simulaciones en Python, aproveche de paso, para presentar este programa como trabajo práctico final en la materia “Lenguajes de Scripting” de la facultad. El código del programa de la simulación puede encontrarse aquí, para correrlo compilar algo.c, ejecutar limpiar.sh y luego version-1-0.py. Las muestras se guardan en formato CSV en la carpeta “resultados/muestras” y los reportes en “resultados/reportes”.

Algunas notas sobre la simulación

Me interesaba analizar específicamente el comportamiento de la porción del algoritmo en la que se itera a travéz de la lista pasados que es la porción variable del mismo. Para hacer esto, cree una variable global total y en cada iteración por la lista pasados en la función esta_en_lista() se la incrementa en uno. El programa escribe luego en STDOUT el valor de esta variable al finalizar. Ver algo.c.

En el script de Python se genera una lhttps://github.com/emluque/Post_Stuff/blob/master/Problema_Algoritmia_Basico/Simulacion/version-1-0.pyista randomizada se levanta un proceso al que se le pasa esta lista como argumento y luego se lee el STDOUT del proceso para obtener el costo. Esto se hace en el archivo: muestras.py y la porción de código que hace esto es:


  def generar_lista(self):
    lista = []
    for i in range(self.n):
      lista.append(random.randint(1, self.k))
    return ",".join( [str(x) for x in lista])

  def generar_resultado(self, lista ):
    process = subprocess.Popen(["algoritmo/algo", lista] , shell=False, stdin=subprocess.PIPE, stdout=subprocess.PIPE)
    res = ""
    for char in process.stdout.read():
      res += char
    
    process.wait()
    #Esta linea que sigue es medio al dope
    if (process.returncode != None):
      if(process.returncode < 0):
        print("----")
        print(process.returncode)
        print("----")
        raise NameError("Tio, No andubo el proceso.") 
    else:   
      process.kill()

    return int(res)

  def generar_resultados(self):
    for i in range(self.cant):
      strr = self.generar_lista();
      a = self.generar_resultado( strr )
      self.resultados.append(a)

Resultados

Un conjunto de resultados pregenerados (una corrida completa del programa puede tardar varias horas) puede verse aquí.

Reportes de Tipo 1

Lo primero que podemos ver en los reportes de tipo 1 es como a mayor tamaño de muestra, la función va tendiendo a un tipo de gráfica especifica. Que no es exactamente igual para diferentes tamaños de alfabeto y cadena, pero se acerca a un Campana de Gauss aunque un poco deformada en la región derecha y con una media corrida un poco hacia la izquierda del rango de valores posibles.

Por ejemplo, este es el gráfico obtenido para tamaño de cadena 10, tamaño de alfabeto 10 con 100000 muestras:

Y este es para 200,200,100000:

Reportes de Tipo 2

Los reportes de tipo 2, permiten ver el comportamiento de la gráfica manteniendo fijo el tamaño de cadena y de muestra.

Que nos muestra el reporte de tipo 2?

Bueno lo que vemos es que manteniendo el tamaño de cadena fijo, al ir aumentando el tamaño de alfabeto, los valores estadísticos (promedio, mediana, modo) van siendo cada vez mayores, lo mismo sucede con la gráfica. Podemos pensar que la posibilidad de ocurrencia de un elemento mayor a los elementos precedentes aumenta a mayor tamaño de alfabeto, lo cual mueve los valores hacia la derecha. Ver el comportamiento de los valores en el reporte para tamaño de cadena 200.

Por otro lado si el tamaño de alfabeto es significativamente mayor al tamaño de cadena, este comportamiento va disminuyendo. Lo cual indica que luego de un determinado valor en función al tamaño de la cadena, la posibilidad de que ocurra un elemento mayor a los elementos anteriores va estabilizándose. Ver reporte para tamaño de cadena 10.

Reportes de Tipo 3

Los reportes de tipo 3, nos muestran que la gráfica de la función se encuentra corrida hacia la izquierda en relación al rango de valores posibles, y que a mayor valor de n y k más hacia la izquierda se mueve en proporción al rango. Esto parecería coincidir con nuestras intuiciones de los posts anteriores, y parecería confirmarse gráficamente los factores de atenuamiento que habíamos considerado en estey este posts.

Gráfico de la función con alfabeto n=50, k=50 y muestra de tamaño 500: