Punto de inflexión

Definir la función

tal que (inflexion xs) es el primer elemento de la lista en donde se cambia de creciente a decreciente o de decreciente a creciente y Nothing si no se cambia. Por ejemplo,

Soluciones

22 Comentarios

    1. Puede optimizarse si cambias las lineas 3 y 4, 9 y 10, 15 y 16, tal que así:

      El por qué te lo dejo como ejercicio ^^

      1. Los tiempos de las dos definiciones son casi iguales

        El primero es con la definición de alerodrod5 y el segundo con la de jaibengue.

        1. Hay CIERTAS listas para las que la definición de alerodrod5 no es del todo eficiente.
          En una lista suficientemente grande en el que todos los elementos sean el mismo, por ejemplo.

    1. La primera función no cubre casos de listas de dos elementos iguales, y la segunda no cubre la lista vacía ni listas de un elemento. La siguiente solución arregla estos casos:

        1. Sí ya, sería más bien esta definición:

          1. Te digo lo mismo que a alerodrod5, la linea en la que

            debería ser la primera comprobación en la función inflexion.

  1. Dos definiciones:
    Una primera, quizá mas intuitiva, lineal en (length [a]) , y una segunda, aunque también lineal en (length [a]), ligeramente mas eficiente:

    1. Buenas, la definición de inflexion no es correcta. Por ejemplo:

      λ> inflexion3 [2,2,1]
      Just 1

      Cuando debería devolver Nothing.
      Empleando la misma idea se me ocurre definir:

        1. Ciertamente usando esta idea habría que añadirle el caso de que el punto de inflexión sea el último elemento de la lista, por tanto (si no me he vuelto a equivocar) debería ser:

    2. En la evaluación no se aprecia que la inflexionEficiente mejore notablemente el tiempo respecto de la primera definición de alerodrod5

      1. Realmente sí lo hace, lo que pasa que no en todos los casos. Por ejemplo en este caso sí es más eficiente:

        λ> inflexion $ replicate (10^7) 5 ++ [0,1]
        Just 1
        (14.39 secs, 3,920,115,104 bytes)
        λ> inflexionEficiente $ replicate (10^7) 5 ++ [0,1]
        Just 1
        (11.41 secs, 3,840,117,440 bytes)

        La cuestión de esto es que cada vez que la función inflexion toma dos valores y los compara no sabe de por sí si son menores, mayores o iguales. Con esto quiero decir que primero comprobara en el caso de la función inflexion si x < y, y si no lo es pasará a comprobar si son iguales y en caso de no serlo aplicaría el otherwise. En el caso de inflexionEficiente comprobaría primero la igualdad y posteriormente que x < y, de ahí la mejora que se aprecia en el ejemplo que he puesto (pues se ahorra comprobar cada vez que aplica la función que x < y = False).

        Por otro lado, la mejora de Jaime se basa (si no me equivoco) en que solo en el caso de que x == y se vuelve a aplicar la función inflexion, pues en otro caso pasaría a aplicar la función creciente o decreciente. Por tanto nada más que x sea distinto de y la función inflexion no se vuelve a aplicar, mientras que si son iguales se aplicará un número determinado de veces (en la que si compruebas x < y antes que x == y irás perdiendo eficiencia).

        En el caso de las funciones creciente o decreciente yo diría que la eficiencia no varía pues si un caso es falso se va directamente al otro. La única variación que observo que podría darse es que sea menos eficiente comparar x y (o viceversa), y en este caso sería más eficiente la función de Alejandro.

        No estoy seguro de si me he explicado demasiado bien pero espero que se entienda ^^ (y no estar equivocado).

  2. Se puede definir sin usar recursión y mejorar el tiempo de la definición inflexionEficiente de jaibengue en el ejemplo de angruicam1.

    La comparación de tiempos es

    1. Esa sólo sirve para listas numéricas, pero con la misma idea se hace

      Esta sirve para cualquier dato de tipo Ord pero es menos eficiente en valores numéricos que la primera.

  3. Otra definición que podría proponerse sería la siguiente:

    Comparación de la eficiencia:

    Donde inflexion es la función inflexionEficiente de jaibengue, inflexion3 es mi propuesta de solución e inflexion4 es la función inflexion de antgongar.

    1. En la definición de inflexion falta el caso de listas con menos de dos elementos.

      Además, en el caso en que los dos primeros elementos sean iguales, en lugar de inflexion3 debe de ser inflexion.

      A parte de esos dos pequeños detalles, es la solución que más me gusta.

      1. Cierto, habría que dejar la definición así:

        Gracias por el comentario ^^

Escribe tu solución