Ruby: Patrones de recurrencia estándar

Una de las cosas que comúnmente me engancho en ruby son los patrones de recursión. Por ejemplo, supongamos que tengo una matriz, y que puede contener matrices como elementos a una profundidad ilimitada. Así, por ejemplo:Ruby: Patrones de recurrencia estándar

my_array = [1, [2, 3, [4, 5, [6, 7]]]]

Me gustaría crear un método que puede aplanar la matriz en [1, 2, 3, 4, 5, 6, 7].

Soy consciente de que .flatten haría el trabajo, pero este problema se entiende como un ejemplo de problemas de recurrencia con los que me encuentro regularmente, y como tal, estoy tratando de encontrar una solución más reutilizable.

En resumen: supongo que hay un patrón estándar para este tipo de cosas, pero no se me ocurre nada particularmente elegante. Cualquier idea apreciada

Fuente

2012-05-21 PlankTon

La recursividad es un método que no depende del idioma. Se escribe el algoritmo con dos tipos de casos en mente: los que llaman a la función nuevamente (casos de recursión) y los que la rompen (casos base). Por ejemplo, para hacer un aplanar recursiva en Ruby:

class Array 
    def deep_flatten 
    flat_map do |item| 
     if item.is_a?(Array) 
     item.deep_flatten 
     else 
     [item] 
     end 
    end 
    end 
end 

[[[1]], [2, 3], [4, 5, [[6]], 7]].deep_flatten 
#=> [1, 2, 3, 4, 5, 6, 7]

¿Esto ayuda? de todos modos, un patrón útil que se muestra aquí es que cuando usa recusion en matrices, generalmente necesita flat_map (la alternativa funcional a each + concat/push).

Fuente

2012-05-21 07:43:53 tokland

Gracias por la respuesta. Originalmente estaba intentando con una función fuera de una clase, que no llamaría de manera recursiva a item.my_flatten ... pero esto funciona. Cheers – PlankTon

@PlankTon. Escribir my_flatten como una función requiere solo algunos cambios menores en el código anterior. Pero al ser un lenguaje OOP, y 'my_flatten' un algoritmo genérico, tiene sentido agregarlo a Array. – tokland

Bueno, si usted sabe un poco de C, sólo hay que visitar los documentos y haga clic en la función de rubí para obtener el código fuente de C y es todo lo que hay ..

http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-flatten

Y para este caso, aquí hay una implementación de Ruby

def flatten values, level=-1 
    flat = [] 
    values.each do |value| 
    if level != 0 && value.kind_of?(Array) 
     flat.concat(flatten(value, level-1)) 
    else 
     flat << value 
    end 
    end 
    flat 
end 

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7]

Fuente

2012-05-21 07:43:51 peter

Ahh - concat. Intentaba llamar recursivamente a la función en sí, pero eso lo hará. Cheers – PlankTon

Aquí hay un ejemplo de un aplanado que está escrito en estilo recursivo de cola.

class Array 

    # Monkeypatching the flatten class 
    def flatten(new_arr = []) 
    self.each do |el| 
     if el.is_a?(Array) 
     el.flatten(new_arr) 
     else 
     new_arr << el 
     end 
    end 

    new_arr 
    end 
end 

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7]

ruby

Aunque parece que Ruby no siempre está optimizado para la recursión de cola: Does ruby perform tail call optimization?

Fuente

2013-12-11 07:34:21

Ruby: Patrones de recurrencia estándar

Respuesta

Cuestiones relacionadas