metodos - listas por comprensión python

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

Question

Estaba leyendo "Learning Python" de Mark Lutz y encontré esta muestra de código :

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

Fue identificado como una estructura de datos cíclicos.

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

¿Para qué sirve una "estructura de datos cíclica" en la programación de la vida real?

Parece que hay un poco de confusión, que creo proviene de la muy breve muestra 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''

Answer 1

Erm, no estoy seguro ya que no los he usado en la vida real, ¿pero podría usarse para simular una estructura de datos anidada? Ver este enlace

Answer 2

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

La inserción de datos "nuevos" ahora es así:

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

Puede insertar datos "antiguos" y borrar datos "antiguos" o "nuevos" de forma similar. Escanear el vector es como esto

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

Answer 3

Un ejemplo sería una lista vinculada donde el último elemento apunta al primero. Esto le permitiría crear una cantidad fija de artículos, pero siempre podrá obtener un próximo artículo.

Answer 4

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

Answer 5

al hacer simulaciones de celosía, se usan a menudo condiciones de contorno cíclico / toroidal. por lo general, un simple lattice[i%L] sería suficiente, pero supongo que uno podría crear el enrejado para que sea cíclico.

Answer 6

Cualquier tipo de jerarquía de objetos donde los padres saben sobre sus hijos y los niños saben acerca de sus padres. Siempre tengo que lidiar con esto en los 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.

Answer 7

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

Para poner un ejemplo del mundo más real, piense en ellos como trayectorias de vuelo de una ciudad.

Así que chicago = [denver, los angeles, new york city, chicago] (de manera realista, no harías una lista de Chicago en sí misma, pero por el bien del ejemplo puedes llegar a Chicago desde Chicago)

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

phoenix = [chicago, ciudad de nueva york]

Ahora tiene datos cíclicos de ambos

chicago -> chicago

pero también

chicago -> denver -> phoenix -> chicago

Ahora tu tienes:

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

Answer 8

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

Answer 9

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 ocasión en que haya utilizado estructuras de datos cíclicas terriblemente complicadas, pero las relaciones bidireccionales son bastante comunes. Por ejemplo, supongamos que quisiera crear 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 quería enviarle un mensaje a Jill, podría hacer esto:

Bob.send("Hi, Jill!")

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

Jill.send("Hi, Bob!")

Es cierto que este es un pequeño ejemplo inventado, pero debería darle un ejemplo de cuándo es posible que desee utilizar una estructura de datos cíclica.

Answer 10

Veamos un solo ejemplo práctico.

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

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

Cuando se presiona un elemento de menú, activaremos la acción del elemento de 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 qué tal 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 hacer 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íclicos, no podríamos tener un elemento de menú que apunta a sí mismo y, por ejemplo, después de presionar la función de aumento de volumen, tendríamos que abandonar el menú de opciones.

Si las estructuras de datos cíclicas no fueran posibles, tendremos que implementarlas 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 mejor, pero sí, no apoyar auto-referencias no es una gran cosa 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 referencias propias, donde almacenamos el gráfico mediante listas de punteros de vértices (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 el soporte de Python para estructuras de datos cíclicos es útil.

Answer 11

Muchas cosas. Memoria intermedia circular, por ejemplo: tiene una colección de datos con un frente y una parte posterior, pero un número arbitrario de nodos, y el elemento "siguiente" de la última debe llevarlo de regreso al primero.

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

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

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

Luego establezco pares de ciudades donde hay un camino que los 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 Limon, a Denver, y de regreso a Colorado Springs.

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

Answer 12

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 da un giro completo (el "->" representa el sentido de las agujas del reloj):

Norte -> Nordeste -> Este -> Sudeste -> Sur -> Sudoeste -> Oeste -> Noroeste -> Norte -> ...

Tenga en cuenta 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.

Answer 13

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 listas regulares de Python.

Puedes obtener el último elemento de L usando [-1] . Puede usar listas de Python como colas con append() y pop() . Puede dividir listas de Python. ¿Cuáles son los usos regulares de una estructura de datos cíclicos?

>>> 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'', [...]]