Punto de inflexión
Definir la función
|
1 |
inflexion :: Ord a => [a] -> Maybe a |
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,
|
1 2 3 4 |
inflexion [2,2,3,5,4,6] == Just 4 inflexion [9,8,6,7,10,10] == Just 7 inflexion [2,2,3,5] == Nothing inflexion [5,3,2,2] == Nothing |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
import Data.List (find) import Data.Maybe (isJust, fromJust) -- 1ª solución -- =========== inflexion :: Ord a => [a] -> Maybe a inflexion (x:y:zs) | x == y = inflexion (y:zs) | x < y = decreciente (y:zs) | otherwise = creciente (y:zs) inflexion _ = Nothing -- (creciente xs) es el segundo elemento de la primera parte creciente -- de xs y Nothing, en caso contrario. Por ejemplo, -- creciente [4,3,5,6] == Just 5 -- creciente [4,3,5,2,7] == Just 5 -- creciente [4,3,2] == Nothing creciente (x:y:zs) | x >= y = creciente (y:zs) | otherwise = Just y creciente _ = Nothing -- (decreciente xs) es el segundo elemento de la primera parte -- decreciente de xs y Nothing, en caso contrario. Por ejemplo, -- decreciente [4,2,3,1,0] == Just 2 -- decreciente [4,5,3,1,0] == Just 3 -- decreciente [4,5,7] == Nothing decreciente (x:y:zs) | x <= y = decreciente (y:zs) | otherwise = Just y decreciente _ = Nothing -- 2ª solución -- =========== inflexion2 :: Ord a => [a] -> Maybe a inflexion2 = aux . signos where aux [] = Nothing aux ((s,_):ys) | null zs = Nothing | otherwise = Just (snd (head zs)) where zs = dropWhile (\(p,_) -> p == s) ys -- (signos xs) es la lista de los pares dormado por el signo de -- crecimiento o decrecimiento de cada elemento de xs respecto de su -- anterior. Por ejemplo, -- λ> signos [2,2,2,3,5,5,4,5,2] -- [(1,3),(1,5),(-1,4),(1,5),(-1,2)] signos :: Ord a => [a] -> [(Int,a)] signos xs = [(signo x y,y) | (x,y) <- zip xs (tail xs), x /= y] -- (signo x y) es el signo de crecimiento o decrecimiento de y respecto -- de x. signo :: Ord a => a -> a -> Int signo x y | x > y = 1 | x < y = -1 | otherwise = 0 -- 3ª solución -- =========== inflexion3 :: Ord a => [a] -> Maybe a inflexion3 (x:y:xs) | x == y = inflexion3 $ y:xs | x < y = buscaMenor $ y:xs | otherwise = buscaMayor $ y:xs inflexion3 _ = Nothing buscaMenor :: Ord a => [a] -> Maybe a buscaMenor (y:xs) | isJust busca = Just (snd (fromJust busca)) | otherwise = Nothing where busca = find parDecreciente (zip (y:xs) xs) buscaMayor :: Ord a => [a] -> Maybe a buscaMayor (y:xs) | isJust busca = Just (snd (fromJust busca)) | otherwise = Nothing where busca = find parCreciente (zip (y:xs) xs) parCreciente :: Ord a => (a,a) -> Bool parCreciente (a,b) = a < b parDecreciente :: Ord a => (a,a) -> Bool parDecreciente (a,b) = a > b -- Comparación de eficiencia -- ========================= -- λ> inflexion (replicate (10^7) 5 ++ [0,1]) -- Just 1 -- (4.73 secs, 3,360,141,912 bytes) -- λ> inflexion2 (replicate (10^7) 5 ++ [0,1]) -- Just 1 -- (2.71 secs, 2,480,144,352 bytes) -- λ> inflexion3 (replicate (10^7) 5 ++ [0,1]) -- Just 1 -- (5.06 secs, 3,360,143,680 bytes) -- -- λ> inflexion ([1..10^7] ++ [0,1]) -- Just 0 -- (3.60 secs, 3,120,146,728 bytes) -- λ> inflexion2 ([1..10^7] ++ [0,1]) -- Just 0 -- (11.33 secs, 6,480,143,376 bytes) -- λ> inflexion3 ([1..10^7] ++ [0,1]) -- Just 0 -- (3.28 secs, 3,280,140,784 bytes) -- -- λ> inflexion ([10^7,10^7-1..1] ++ [2,1]) -- Just 2 -- (3.62 secs, 3,200,141,784 bytes) -- λ> inflexion2 ([10^7,10^7-1..1] ++ [2,1]) -- Just 2 -- (10.01 secs, 5,840,144,200 bytes) -- λ> inflexion3 ([10^7,10^7-1..1] ++ [2,1]) -- Just 2 -- (3.56 secs, 3,360,145,728 bytes) |
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 ^^
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.
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.
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:
No es correcta. Contraejemplo: La lista [1,1,0].
Sí ya, sería más bien esta definición:
Te digo lo mismo que a alerodrod5, la linea en la que
debería ser la primera comprobación en la función inflexion.
Dos definiciones:
Una primera, quizá mas intuitiva, lineal en (length [a]) , y una segunda, aunque también lineal en (length [a]), ligeramente mas eficiente:
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:
Falla por ejemplo en [3,1,1,4]
Debería de dar Just 4
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:
En la evaluación no se aprecia que la inflexionEficiente mejore notablemente el tiempo respecto de la primera definición de alerodrod5
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).
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
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.
Falla para [0,8,8,2]. Da Nothing en lugar de (Just 2).
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.
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.
Cierto, habría que dejar la definición así:
Gracias por el comentario ^^