A cosa serve una struttura di dati ciclica?

Question

Stavo solo leggendo " Learning Python " di Mark Lutz e ho trovato questo esempio di codice :

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

È stato identificato come una struttura di dati ciclica.

Quindi mi chiedevo, ed ecco la mia domanda:

A cosa serve una "struttura di dati ciclica" utilizzata nella programmazione di vita reale?

Sembra che ci sia un po 'di confusione, che penso provenga dal brevissimo esempio di codice ... ecco alcune altre righe che usano lo stesso oggetto L

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

Answer 1

Molte cose. Buffer circolare, ad esempio: hai una raccolta di dati con un fronte e un retro, ma un numero arbitrario di nodi e il "successivo" l'elemento dall'ultimo dovrebbe riportarti al primo.

Le strutture grafiche sono spesso cicliche; l'aciclicità è un caso speciale. Considera, ad esempio, un grafico che contiene tutte le città e le strade in un problema del commesso viaggiatore.

---

Ok, ecco un esempio particolare per te. Ho creato una raccolta di città qui in Colorado:

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

Ho quindi creato coppie di città in cui è presente una strada che le collega.

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

Questo ha un sacco di cicli. Ad esempio, puoi guidare da Colorado Springs, a Limon, a Denver e tornare a Colorado Springs.

Se crei una struttura di dati che contiene tutte le città in V e tutte le strade in E, si tratta di una struttura di dati grafico . Questo grafico avrebbe dei cicli.

Answer 2

Di recente ho creato una struttura di dati ciclica per rappresentare le otto direzioni cardinali e ordinali. È utile per ogni direzione conoscere i suoi vicini. Ad esempio, Direction.North sa che Direction.NorthEast e Direction.NorthWest sono i suoi vicini.

Questo è ciclico perché ogni vicino conosce i suoi vicini fino a quando non gira a pieno ritmo (il "quot - - >" rappresenta in senso orario):

Nord - > NordEst - > Est: > Sud-est - > Sud: > SouthWest - > Ovest: > NorthWest - > Nord: > ...

Si noti che siamo tornati al Nord.

Questo mi permette di fare cose del genere (in 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);
}

Questo si è rivelato abbastanza utile e ha reso molte cose molto meno complicate.

Answer 3

Una struttura nidificata potrebbe essere utilizzata in un caso di test per un garbage collector.

Answer 4

È un po 'confuso poiché è un elenco che contiene se stesso, ma il modo in cui ne ho dato senso è non pensare a L come a un elenco, ma a un nodo e invece di cose in un elenco, si pensa a come altri nodi raggiungibili da questo nodo.

Per dare un esempio più reale del mondo, pensali come percorsi di volo da una città.

So chicago = [denver, los angeles, new york city, chicago] (realisticamente non elencheresti chicago in sé, ma per esempio puoi raggiungere chicago da chicago)

Quindi hai denver = [fenice, philedelphia] e così via.

phoenix = [chicago, new york city]

Ora hai dati ciclici sia da

  

chicago - > Chicago

ma anche

  

chicago - > denver - > fenice: > Chicago

Ora hai:

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

Answer 5

Le strutture di dati ripetute da deterministic finite autata sono spesso cicliche.

Answer 6

L contiene solo un riferimento a se stesso come uno dei suoi elementi. Niente di veramente speciale in questo.

Vi sono alcuni usi ovvi delle strutture cicliche in cui l'ultimo elemento conosce il primo elemento. Ma questa funzionalità è già coperta da normali elenchi di Python.

Puoi ottenere l'ultimo elemento di L usando [-1] . Puoi usare gli elenchi di Python come code con append () e pop () . Puoi dividere gli elenchi di Python. Quali sono gli usi regolari di una struttura di dati ciclica.

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

Answer 7

Un esempio potrebbe essere un elenco collegato in cui l'ultimo elemento punta il primo. Ciò ti consentirebbe di creare un numero fisso di articoli ma di essere sempre in grado di ottenere un articolo successivo.

Answer 8

quando si eseguono simulazioni reticolari vengono spesso utilizzate condizioni al contorno cicliche / toroidali. di solito sarebbe sufficiente un semplice reticolo [i% L] , ma suppongo che si potrebbe creare un reticolo ciclico.

Answer 9

Supponi di avere una memoria limitata e che i dati si accumulino costantemente. In molti casi reali, non ti dispiace sbarazzarti dei vecchi dati, ma non vuoi spostare i dati. Puoi usare un vettore ciclico; implementato usando un vettore v di dimensione N con due indici speciali: inizio e fine, che iniziano con 0.

Inserimento di " nuovo " i dati ora vanno così:

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

Puoi inserire " vecchio " dati e cancella "vecchio" o " nuovo " dati in modo simile. La scansione del vettore procede in questo modo

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

Answer 10

Qualsiasi tipo di gerarchia di oggetti in cui i genitori conoscono i loro figli e i loro figli conoscono i loro genitori. Ho sempre a che fare con questo negli ORM perché voglio che i database conoscano le loro tabelle e tabelle per sapere di quale database fanno parte, e così via.

Answer 11

Diamo un'occhiata a un singolo esempio pratico.

Diciamo che stiamo programmando una navigazione nel menu per un gioco. Vogliamo archiviare per ogni voce di menu

1. Il nome della voce
2. L'altro menu che raggiungeremo dopo averlo premuto.
3. L'azione che verrebbe eseguita premendo il menu.

Quando si preme una voce di menu, si attiva l'azione della voce di menu e quindi si passa al menu successivo. Quindi il nostro menu sarebbe un semplice elenco di dizionari, in questo modo:

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}
    ]

Guarda come su è ciclico:

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

Quando si preme una voce di menu, viene emessa la seguente funzione al clic:

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

Ora, se non avessimo strutture di dati cicliche, non saremmo in grado di avere una voce di menu che punta a se stessa e, ad esempio, dopo aver premuto la funzione di aumento del volume dovremmo lasciare le opzioni menu.

Se le strutture di dati cicliche non fossero possibili, dovremo implementarle da soli, ad esempio la voce di menu sarebbe:

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 funzione menu_item_pressed sarebbe:

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

Il primo esempio è un po 'più carino, ma sì, non supportare i riferimenti personali non è un grosso problema IMHO, in quanto è facile superare questa limitazione.

L'esempio di menu è come un grafico con riferimenti automatici, in cui memorizziamo il grafico mediante elenchi di puntatori di vertici (ogni vertice è un elenco di puntatori ad altri vertici). In questo esempio avevamo bisogno di self edge (un vertice che punta a se stesso), quindi il supporto di Python per strutture di dati cicliche è utile.

Answer 12

Le strutture di dati cicliche sono generalmente utilizzate per rappresentare relazioni circolari. Sembra ovvio, ma succede più di quanto pensi. Non riesco a pensare a nessuna volta in cui ho usato strutture di dati cicliche terribilmente complicate, ma le relazioni bidirezionali sono abbastanza comuni. Ad esempio, supponiamo che volessi creare un client di messaggistica istantanea. Potrei fare qualcosa del genere:

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)

Quindi, se Bob volesse inviare un messaggio a Jill, potresti semplicemente farlo:

Bob.send("Hi, Jill!")

Certo, Jill potrebbe voler rispedire un messaggio, quindi potrebbe farlo:

Jill.send("Hi, Bob!")

Certamente, questo è un po 'un esempio inventato, ma dovrebbe darti un esempio di quando potresti voler usare una struttura di dati ciclica.