¿Para qué sirve una estructura de datos cíclica?

https://stackoverflow.com/questions/405540

03-07-2019
|

Pregunta

Estaba leyendo " Aprendizaje de Python " por Mark Lutz y encontré este ejemplo de código :


>>> L = ['grail']
>>> L.append(L)
>>> L
['grail', [...]]

Se identificó como una estructura de datos cíclica.

Entonces me preguntaba, y aquí está mi pregunta:

¿Para qué se utiliza una 'estructura de datos cíclica' en la programación de la vida real?

Parece haber una pequeña confusión, que creo que se deriva del breve ejemplo de código ... aquí hay algunas líneas más que usan el mismo objeto L


>>> L[0]
'grail'
>>> L[1][0]
'grail'
>>> L[1][1][0]
'grail'

Solución

Muchas cosas. Búfer circular, por ejemplo: tiene una colección de datos con un frente y un reverso, pero un número arbitrario de nodos, y el '' siguiente '' el elemento del último debería llevarlo de regreso al primero.

Las estructuras gráficas son a menudo cíclicas; La aciclicidad es un caso especial. Considere, por ejemplo, un gráfico que contiene todas las ciudades y carreteras en un problema de vendedor ambulante.

Bien, aquí hay un ejemplo particular para ti. Instalé una colección de ciudades aquí en Colorado:

V=["Boulder", "Denver", "Colorado Springs", "Pueblo", "Limon"]

Luego configuro pares de ciudades donde hay una carretera que las conecta.

E=[["Boulder", "Denver"],
   ["Denver", "Colorado Springs"],
   ["Colorado Springs", "Pueblo"],
   ["Denver", "Limon"],
   ["Colorado Springs", "Limon"]]

Esto tiene un montón de ciclos. Por ejemplo, puede conducir desde Colorado Springs, a Limón, a Denver y de regreso a Colorado Springs.

Si crea una estructura de datos que contiene todas las ciudades en V y todas las carreteras en E, esa es una estructura de datos de gráfico . Este gráfico tendría ciclos.

Otros consejos

Recientemente creé una estructura de datos cíclicos para representar las ocho direcciones cardinales y ordinales. Es útil para cada dirección conocer a sus vecinos. Por ejemplo, Direction.North sabe que Direction.NorthEast y Direction.NorthWest son sus vecinos.

Esto es cíclico porque cada vecino conoce a sus vecinos hasta que se balancea por completo (el " - > " representa en sentido horario):

Norte - > Nordeste - > Este - > Sureste - > Sur - > Suroeste - > Oeste - > Noroeste - > Norte - > ...

Observe que volvimos al norte.

Eso me permite hacer cosas como esta (en C #):

public class Direction
{
    ...
    public IEnumerable<Direction> WithTwoNeighbors
    {
        get {
           yield return this;
           yield return this.CounterClockwise;
           yield return this.Clockwise;
        }
    }
}
...
public void TryToMove (Direction dir)
{
    dir = dir.WithTwoNeighbors.Where (d => CanMove (d)).First ()
    Move (dir);
}

Esto resultó ser bastante útil e hizo que muchas cosas fueran mucho menos complicadas.

Una estructura anidada podría usarse en un caso de prueba para un recolector de basura.

Es un poco confuso ya que es una lista que se contiene a sí misma, pero la forma en que lo entendí es no pensar en L como una lista, sino como un nodo, y en lugar de cosas en una lista, piensas en como otros nodos accesibles por este nodo.

Para poner un ejemplo más real, piense en ellos como rutas de vuelo desde una ciudad.

Entonces chicago = [denver, los ángeles, nueva york, chicago] (en realidad no enumerarías a chicago en sí mismo, pero por ejemplo puedes llegar a chicago desde chicago)

Entonces tienes denver = [phoenix, philedelphia] y así sucesivamente.

phoenix = [chicago, nueva york]

Ahora tiene datos cíclicos tanto de

chicago - > chicago

pero también

chicago - > denver - > fénix - > chicago

Ahora tienes:

chicago[0] == denver
chicago[0][0] == phoenix
chicago[0][0][0] == chicago

Las estructuras de datos iteradas por autómatas deterministas finitos suelen ser cíclicos.

L solo contiene una referencia a sí mismo como uno de sus elementos. Nada realmente especial sobre esto.

Hay algunos usos obvios de estructuras cíclicas donde el último elemento sabe sobre el primer elemento. Pero esta funcionalidad ya está cubierta por las listas regulares de Python.

Puede obtener el último elemento de L utilizando [-1] . Puede usar listas de python como colas con append () y pop () . Puedes dividir las listas de python. Cuáles son los usos habituales de una estructura de datos cíclica.

>>> L = ['foo', 'bar']
>>> L.append(L)
>>> L
['foo', 'bar', [...]]
>>> L[0]
'foo'
>>> L[1]
'bar'
>>> L[2]
['foo', 'bar', [...]]
>>> L[2].append('baz')
>>> L
['foo', 'bar', [...], 'baz']
>>> L[2]
['foo', 'bar', [...], 'baz']
>>> L[2].pop()
'baz'
>>> L
['foo', 'bar', [...]]
>>> L[2]
['foo', 'bar', [...]]

Un ejemplo sería una lista vinculada donde el último elemento señala el primero. Esto le permitirá crear un número fijo de elementos, pero siempre podrá obtener el siguiente elemento.

cuando se realizan simulaciones de celosía, a menudo se utilizan condiciones de límite cíclicas / toroidales. por lo general, una simple retícula [i% L] sería suficiente, pero supongo que uno podría crear la retícula para que sea cíclica.

Suponga que tiene un almacenamiento limitado y que los datos se acumulan constantemente. En muchos casos de la vida real, no le importa deshacerse de los datos antiguos, pero no desea moverlos. Puedes usar un vector cíclico; implementado usando un vector v de tamaño N con dos índices especiales: comienzo y fin, que se inician en 0.

Inserción de " nuevo " los datos ahora son así:

v[end] = a;
end = (end+1) % N;
if (begin == end)
  begin = (begin+1) % N;

Puede insertar " viejo " datos y borrar " viejo " o "nuevo" datos de manera similar. Escanear el vector es así

for (i=begin; i != end; i = (i+1) % N) {
 // do stuff
}

Cualquier tipo de jerarquía de objetos donde los padres sepan de sus hijos y los hijos sepan de sus padres. Siempre tengo que lidiar con esto en ORM porque quiero que las bases de datos conozcan sus tablas y tablas para saber de qué base de datos forman parte, y así sucesivamente.

Veamos un solo ejemplo práctico.

Digamos que estamos programando un menú de navegación para un juego. Queremos almacenar para cada elemento del menú

El nombre de la entrada
Al otro menú llegaremos después de presionarlo.
La acción que se realizaría al presionar el menú.

Cuando se presiona un elemento del menú, activaremos la acción del elemento del menú y luego pasaremos al siguiente menú. Entonces nuestro menú sería una simple lista de diccionarios, así:

options,start_menu,about = [],[],[]

def do_nothing(): pass

about += [
    {'name':"copyright by...",'action':None,'menu':about},
    {'name':"back",'action':do_nothing,'menu':start_menu}
    ]
options += [
    {'name':"volume up",'action':volumeUp,'menu':options},
    {'name':"save",'action':save,'menu':start_menu},
    {'name':"back without save",'action':do_nothing,'menu':start_menu}
    ]
start_menu += [
    {'name':"Exit",'action':f,'menu':None}, # no next menu since we quite
    {'name':"Options",'action':do_nothing,'menu':options},
    {'name':"About",'action':do_nothing,'menu':about}
    ]

Vea cómo about es cíclico:

>>> print about
[{'action': None, 'menu': [...], 'name': 'copyright by...'},#etc.
# see the ellipsis (...)

Cuando se presiona un elemento del menú, emitiremos la siguiente función de clic:

def menu_item_pressed(item):
    log("menu item '%s' pressed" % item['name'])
    item['action']()
    set_next_menu(item['menu'])

Ahora, si no tuviéramos estructuras de datos cíclicas, no podríamos tener un elemento de menú que apunte a sí mismo y, por ejemplo, después de presionar la función de subir volumen, tendríamos que dejar las opciones menú.

Si las estructuras de datos cíclicos no fueran posibles, tendremos que implementarlo nosotros mismos, por ejemplo, el elemento del menú sería:

class SelfReferenceMarkerClass: pass
#singleton global marker for self reference
SelfReferenceMarker = SelfReferenceMarkerClass()
about += [
    {'name':"copyright by...",'action':None,'menu':srm},
    {'name':"back",'action':do_nothing,'menu':start_menu}
    ]

la función menu_item_pressed sería:

def menu_item_pressed(item):
    item['action']()
    if (item['menu'] == SelfReferenceMarker):
        set_next_menu(get_previous_menu())
    else:
        set_next_menu(item['menu'])

El primer ejemplo es un poco más agradable, pero sí, no es compatible con autorreferencias, en mi humilde opinión, ya que es fácil superar esta limitación.

El ejemplo de menús es como un gráfico con auto-referencias, donde almacenamos el gráfico por listas de punteros de vértice (cada vértice es una lista de punteros a otros vértices). En este ejemplo, necesitábamos bordes propios (un vértice que apunta a sí mismo), por lo que es útil el soporte de Python para estructuras de datos cíclicos.

Las estructuras de datos cíclicos se usan generalmente para representar relaciones circulares. Eso suena obvio, pero sucede más de lo que piensas. No puedo pensar en ninguna vez que haya usado estructuras de datos cíclicas terriblemente complicadas, pero las relaciones bidireccionales son bastante comunes. Por ejemplo, supongamos que quiero hacer un cliente de mensajería instantánea. Podría hacer algo como esto:

class Client(object):
    def set_remote(self, remote_client):
        self.remote_client = remote_client

    def send(self, msg):
        self.remote_client.receive(msg)

    def receive(self, msg):
        print msg

Jill = Client()
Bob = Client()
Bob.set_remote(Jill)    
Jill.set_remote(Bob)

Entonces, si Bob deseaba enviar un mensaje a Jill, podría hacer esto:

Bob.send("Hi, Jill!")

Por supuesto, Jill puede querer enviar un mensaje de regreso, para que pueda hacer esto:

Jill.send("Hi, Bob!")

Es cierto que este es un ejemplo un poco artificial, pero debería darle un ejemplo de cuándo puede querer usar una estructura de datos cíclica.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow