algorithm - science - ¿Puedo convertir siempre algoritmos mutables en una única asignación y seguir siendo eficiente?

php paradigm

Question

El contexto

El contexto de esta pregunta es que quiero jugar con Gene Expression Programming (GEP), una forma de algoritmo evolutivo, usando Erlang . GEP hace uso de una DSL basada en cadenas llamada '' notación Karva ''. La notación de Karva se traduce fácilmente en árboles de análisis de expresión, pero el algoritmo de traducción supone una implementación que tiene objetos mutables: las subexpresiones incompletas se crean temprano en el proceso de traducción y sus propias subexpresiones se completan posteriormente con valores que fueron desconocido en el momento en que fueron creados.

El propósito de la notación de Karva es que garantiza que las expresiones sintácticamente correctas se crean sin ninguna técnica de codificación costosa o correcciones de código genético. El problema es que con un lenguaje de programación de asignación única como Erlang, tengo que volver a crear el árbol de expresión a medida que se completa cada sub expresión. Esto lleva un bajo costo - ¿O (n)? - actualice la operación y conviértala en una que se complete en tiempo exponencial (a menos que esté equivocado). Si no puedo encontrar un algoritmo funcional eficiente para convertir expresiones K en árboles de expresión, entonces se pierde una de las características atractivas de GEP.

La pregunta

Aprecio que el problema de la traducción de la expresión K sea bastante oscuro, así que lo que quiero es consejos sobre cómo convertir un algoritmo intrínsecamente no funcional (alg que explota estructuras de datos mutables) en uno que no lo haga. ¿Cómo adaptan los lenguajes de programación puramente funcionales muchos de los algoritmos y estructuras de datos que se produjeron en los primeros tiempos de la informática que dependen de la mutabilidad para obtener las características de rendimiento que necesitan?

Answer 1

Creo que descubrí cómo resolver tu problema particular con los árboles K, (el problema general es muy difícil: P). Mi solución se presenta en un horrible tipo de psudocódigo tipo Python (estoy muy lento en mi FP hoy) pero no cambia un nodo después de crear uno (el truco es construir el árbol de abajo hacia arriba)

Primero, necesitamos encontrar qué nodos pertenecen a qué nivel:

levels currsize nodes = 
    this_level , rest = take currsize from nodes, whats left
    next_size = sum of the arities of the nodes
    return [this_level | levels next_size rest]
(initial currsize is 1)

Entonces, en el +/*abcd , ejemplo, esto debería darte [+, /*, abcd] . Ahora puedes convertir esto en un árbol de abajo hacia arriba:

curr_trees = last level
for level in reverse(levels except the last)
    next_trees = []
    for root in level:
        n = arity of root
        trees, curr_trees = take n from curr_trees, whats left
        next_trees.append( Node(root, trees) )
    curr_trees = next_trees

curr_trees should be a list with the single root node now.

Estoy bastante seguro de que podemos convertir esto en una sola tarea Erlang / Haskell muy fácilmente ahora.

Answer 2

No hay una sola forma de hacerlo, realmente debe intentarse caso por caso. Por lo general, intento dividirlos en operaciones más simples usando plegar y desplegar y luego optimizar desde allí. El caso de decodificación de Karva es un árbol de amplitud de primer plano como otros han notado, así que comencé con treeUnfoldM_BF. Quizás haya funciones similares en Erlang.

Si la operación de decodificación es irracionalmente costosa, podría memorizar la decodificación y compartir / reutilizar los subárboles ... aunque probablemente no encajaría en una estructura de árbol genérica y tendría que escribir una función especializada para hacerlo. Si la función de acondicionamiento físico es lo suficientemente lenta, puede estar bien usar un decodificador ingenuo como el que he enumerado a continuación. Reconstruirá completamente el árbol en cada invocación.

import Control.Monad.State.Lazy
import Data.Tree

type MaxArity = Int
type NodeType = Char

treeify :: MaxArity -> [Char] -> Tree NodeType
treeify maxArity (x:xs) = evalState (unfoldTreeM_BF (step maxArity) x) xs
treeify _ [] = fail "empty list"

step :: MaxArity -> NodeType -> State [Char] (NodeType, [NodeType])
step maxArity node = do
  xs <- get
  -- figure out the actual child node count and use it instead of maxArity
  let (children, ys) = splitAt maxArity xs
  put ys
  return (node, children)

main :: IO ()
main = do
 let x = treeify 3 "0138513580135135135"
 putStr $ drawTree . fmap (:[]) $ x
 return ()

Answer 3

La inmutabilidad cuidadosamente diseñada evita una actualización innecesaria

Las estructuras de datos inmutables son solo un problema de eficiencia si cambian constantemente, o las construye de forma incorrecta. Por ejemplo, agregar continuamente más al final de una lista creciente es cuadrático, mientras que concatenar una lista de listas es lineal. Si lo piensas bien, generalmente puedes construir tu estructura de una manera sensata, y tu amiga es la evaluación perezosa: reparte la promesa de resolverlo y deja de preocuparte.

A ciegas, intentar replicar un algoritmo imperativo puede ser ineficaz, pero te equivocas en tu afirmación de que la programación funcional tiene que ser asintóticamente mala aquí.

Estudio de caso: GEP pura funcional: notación de Karva en tiempo lineal

Me quedaré con su estudio de caso de analizar la notación de Karva para GEP. (He jugado con esta solución más completamente en esta respuesta ).

Aquí hay una solución funcional pura y limpia para el problema. Aprovecharé la oportunidad para mencionar algunos buenos esquemas generales de recursión en el camino.

Código

(Importación de data Tree a = Node {rootLabel :: a, subForest :: Forest a} suministra data Tree a = Node {rootLabel :: a, subForest :: Forest a} donde type Forest a = [Tree a] .)

import Data.Tree
import Data.Tree.Pretty -- from the pretty-tree package for visualising trees

arity :: Char -> Int
arity c 
  | c `elem` "+*-/" = 2
  | c `elem` "Q" = 1
  | otherwise = 0

Un hylomorphism es la composición de un anamorphism (build up, unfoldr) y un catamorphism (combine, foldr). Estos términos se presentan a la comunidad de PF en el documento seminal Functional Programming with Bananas, Lenses and Barbed wire .

Vamos a sacar los niveles (ana / unfold) y volver a combinarlos (cata / fold).

hylomorphism :: b -> (a -> b -> b) -> (c -> (a, c)) -> (c -> Bool) -> c -> b
hylomorphism base combine pullout stop seed = hylo seed where
 hylo s | stop s = base
        | otherwise = combine new (hylo s'') 
          where (new,s'') = pullout s

Para sacar un nivel, usamos la aridad total del nivel anterior para encontrar dónde dividir este nuevo nivel y transferir el arity total para este listo para la próxima vez:

pullLevel :: (Int,String) -> (String,(Int,String))
pullLevel (n,cs) = (level,(total, cs'')) where
                   (level,        cs'') = splitAt n cs
                   total = sum $ map arity level

Para combinar un nivel (como una cadena) con el nivel siguiente (que ya es un bosque), simplemente eliminamos la cantidad de árboles que necesita cada personaje.

combineLevel :: String -> Forest Char -> Forest Char
combineLevel "" [] = []
combineLevel (c:cs) levelBelow = Node c subforest : combineLevel cs theRest 
      where (subforest,theRest) = splitAt (arity c) levelBelow

Ahora podemos analizar el Karva usando un hylomorphism. Tenga en cuenta que lo iniciamos con una arity total desde fuera de la cadena de 1 , ya que solo hay un nodo en el nivel raíz. En consecuencia, aplicamos la head al resultado para que este singleton vuelva a salir después del hylomorphism.

karvaToTree :: String -> Tree Char
karvaToTree cs = let
  zero (n,_) = n == 0          
    in head $ hylomorphism [] combineLevel pullLevel zero (1,cs) 

Tiempo lineal

No hay una explosión exponencial, ni repetidas búsquedas O (log (n)) ni modificaciones costosas, por lo que no deberíamos tener demasiados problemas.

• arity es O ( 1 )
• splitAt part es O ( part )
• pullLevel (part,cs) es O ( part ) para agarrar usando splitAt para obtener el level , más O ( part ) para el map arity level del map arity level , por lo que O ( part )
• combineLevel (c:cs) es O ( arity c ) para splitAt , y O ( sum $ map arity cs ) para la llamada recursiva

• hylomorphism [] combineLevel pullLevel zero (1,cs)

  • realiza una llamada pullLevel para cada nivel, por lo que el costo total de pullLevel es O ( sum partes) = O (n)
  • realiza una llamada combineLevel para cada nivel, por lo que el costo total de combineLevel es O ( sum $ map arity niveles de sum $ map arity ) = O (n), ya que la aridad total de toda la entrada está vinculada por n para cadenas válidas.
  • hace O (#levels) llama a zero (que es O ( 1 )), y #levels está vinculado por n , por lo que está por debajo de O (n) también

  Por karvaToTree tanto, karvaToTree es lineal en la longitud de la entrada.

Creo que eso pone fin a la afirmación de que necesitas usar la mutabilidad para obtener un algoritmo lineal aquí.

Manifestación

Vamos a tener un sorteo de los resultados (¡porque Tree está tan lleno de sintaxis que es difícil leer la salida!). Tienes que cabal install pretty-tree Data.Tree.Pretty cabal install pretty-tree para obtener Data.Tree.Pretty .

see :: Tree Char -> IO ()
see = putStrLn.drawVerticalTree.fmap (:"")

ghci> karvaToTree "Q/a*+b-cbabaccbac"
Node {rootLabel = ''Q'', subForest = [Node {rootLabel = ''/'', subForest = [Node {rootLabel = ''a'', subForest = []},Node {rootLabel = ''*'', subForest = [Node {rootLabel = ''+'', subForest = [Node {rootLabel = ''-'', subForest = [Node {rootLabel = ''b'', subForest = []},Node {rootLabel = ''a'', subForest = []}]},Node {rootLabel = ''c'', subForest = []}]},Node {rootLabel = ''b'', subForest = []}]}]}]}

ghci> see $ karvaToTree "Q/a*+b-cbabaccbac"
      Q      
      |      
      /      
      |      
 ------      
/      /     
a      *     
       |     
       ----- 
      /     /
      +     b
      |      
     ----    
    /    /   
    -    c   
    |        
    --       
   /  /      
   b  a  

que coincide con el resultado esperado de este tutorial donde encontré el ejemplo :

Answer 4

Hay un par de soluciones cuando se requiere un estado mutable en la programación funcional.

1. Use un algoritmo diferente que resuelva el mismo problema. Por ejemplo, el quicksort generalmente se considera mutable y, por lo tanto, puede ser menos útil en un entorno funcional, pero el mergesort generalmente es más adecuado para un entorno funcional. No puedo decir si esta opción es posible o tiene sentido en su caso.

2. Incluso los lenguajes de programación funcionales suelen proporcionar algún modo de mutar el estado. ( Esta publicación de blog parece mostrar cómo hacerlo en Erlang). Para algunos algoritmos y estructuras de datos, esta es de hecho la única opción disponible (creo que hay una investigación activa sobre el tema); por ejemplo, las tablas hash en lenguajes de programación funcional generalmente se implementan con estado mutable.

En su caso, no estoy tan seguro de que la inmutabilidad realmente conduzca a un cuello de botella de rendimiento. Tiene razón, el (sub) árbol se recreará en la actualización, pero la implementación de Erlang probablemente reutilizará todos los subárboles que no han cambiado, lo que lleva a una complejidad O (log n) por actualización en lugar de O (1) con estado mutable . Además, los nodos de los árboles no se copiarán, sino las referencias a los nodos, que deberían ser relativamente eficientes. Puede leer sobre actualizaciones de árboles en una configuración funcional, por ejemplo, en la tesis de Okasaki o en su libro "Estructuras de datos puramente funcionales" basadas en la tesis. Intentaría implementar el algoritmo con una estructura de datos inmutable y cambiar a uno mutable si tienes un problema de rendimiento.

También vea algunas preguntas relevantes aquí y aquí .