Was ist eine zyklische Datenstruktur gut?

https://stackoverflow.com/questions/405540

03-07-2019
|

Frage

Ich habe nur das Lesen durch " Learning Python“von Mark Lutz und über dieses Codebeispiel kam:


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

Es wurde als eine zyklische Datenstruktur identifiziert.

Also ich frage mich, und hier ist meine Frage:

Was ist eine 'zyklische Datenstruktur' für im wirklichen Leben Programmierung verwendet?

Es scheint ein wenig Verwirrung zu sein, was ich denke, ergibt sich aus der sehr kurzen Codebeispiel ... hier ein paar mehr Zeilen das gleiche Objekt L mit


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

Lösung

Viele Dinge. Ringpuffer, zum Beispiel: Sie haben einige Sammlung von Daten mit einer vorderen und einem hinteren, sondern einer beliebigen Anzahl von Knoten, und die „nächsten“ aus dem letzten sollten Sie zurück zum ersten nehmen

Graph Strukturen sind oft zyklisch; Azyklizität ist ein Sonderfall. Betrachten wir zum Beispiel eine grafische Darstellung, alle Städte und Straßen in einem Reiseproblem enthält.

Okay, hier ist ein besonderes Beispiel für Sie. Ich habe eine Sammlung von Städten hier in Colorado bis:

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

ich dann Paare von Städten eingerichtet, wo eine Straße dort verbindet sie.

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

Dies hat eine Reihe von Zyklen. Zum Beispiel können Sie von Colorado Springs fahren, nach Limon, nach Denver und zurück nach Colorado Springs.

Wenn Sie eine Datenstruktur erstellen, die alle Städte in V enthält und alle Straßen in E, das ist eine Graph Datenstruktur. Dieser Graph würde Zyklen haben.

Andere Tipps

Ich habe vor kurzem eine zyklische Datenstruktur, die die acht Kardinal und Ordnungs Richtungen darzustellen. Seine nützlich für jede Richtung seiner Nachbarn zu kennen. Zum Beispiel weiß Direction.North dass Direction.NorthEast und Direction.NorthWest seine Nachbarn sind.

Dies ist zyklisch, weil jeder neighor seine Nachbarn kennt, bis er um vollen Gang geht (der „->“ steht im Uhrzeigersinn):

Nord -> Northeast -> Ost -> Südost -> Süd -> SüdWest -> West -> NordWest -> Nord -> ...

Beachten Sie kamen wir nach Norden zurück.

Das erlaubt mir Sachen wie dies zu tun (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);
}

Dies wurde ganz praktisch, und machte eine Menge Dinge viel weniger kompliziert.

Eine verschachtelte Struktur könnte in einem Testfall für eine Garbage Collector verwendet werden.

Es ist ein wenig verwirrend, da es sich um eine Liste, die selbst enthält, aber die Art, wie ich sinnvoll von ihm gemacht ist nicht als eine Liste von L zu denken, aber ein Knoten, und statt der Dinge in einer Liste, die Sie sich vorstellen als anderer Knoten erreichbar von diesem Knoten.

Um ein Beispiel aus der Praxis setzen, denken Sie an sich als Flugrouten von einer Stadt.

So chicago = [denver, Los Angeles, New York City, Chicago] (realistisch würden Sie nicht chicago Liste an sich, sondern aus Gründen der Beispiel können Sie Chicago von Chicago erreichen)

Dann haben Sie denver = [phoenix, philedelphia] und so weiter.

phoenix = [chicago, new york city]

Jetzt können Sie zyklische Daten sowohl von

Chicago -> chicago

, sondern auch

Chicago -> denver -> phoenix -> chicago

Jetzt haben Sie:

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

Die Datenstrukturen iteriert von deterministischen endlichen Automaten oft zyklisch sind.

L enthält nur einen Verweis auf sich selbst als eines seiner Elemente. Nichts wirklich Besondere daran.

Es gibt einige offensichtliche Verwendung von zyklischen Strukturen, in denen das letzte Element über das erste Element kennt. Aber diese Funktionalität bereits durch regelmäßige Python Listen abgedeckt ist.

Sie können das letzte Element von L erhalten, indem [-1] verwenden. Sie können Python-Listen als Warteschlangen mit append() und pop() verwenden. Sie können Python-Listen aufgeteilt. Welches ist der regelmäßige Gebrauch einer zyklischen Datenstruktur.

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

Ein Beispiel wäre eine verknüpfte Liste, wo der letzte Punkt Punkte die ersten. Dies würde ermöglicht es Ihnen, eine feste Anzahl von Elementen zu schaffen, sondern immer in der Lage sein, einen nächsten Punkt zu erhalten.

, wenn Gittersimulationen zyklisch / toroidalen Randbedingungen tun werden oft verwendet. in der Regel ein einfaches lattice[i%L] würde genügen, aber ich denke, man könnte das Gitter erzeugt zyklisch sein.

Angenommen, Sie Speicher beschränkt haben, und Daten sammelt sich ständig. In vielen realen Fällen macht es dir nicht von alten Daten loszuwerden, aber Sie wollen nicht, Daten zu bewegen. Sie können einen zyklischen Vektor verwenden; Verwendung eines Vektors v der Größe N implementiert mit zwei speziellen Indizes. beginnen und enden, die auf 0 initiieren

Einfügen von „neuen“ Daten geht nun wie folgt aus:

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

Sie können „alte“ Daten einfügen und „alte“ oder „neue“ Daten in ähnlicher Weise löschen. Scannen des Vektors geht so

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

Jede Art von Objekt-Hierarchie, wo die Eltern wissen über ihre Kinder und Kinder wissen über ihre Eltern. Ich bin immer mit diesem in ORMs beschäftigen, weil ich Datenbanken will ihre Tabellen und Tabellen wissen, zu wissen, welche Datenbank sie sind ein Teil, und so weiter.

Lassen Sie sich an einem Beispiel aus der Praxis aussehen.

Lassen Sie uns sagen, dass wir eine Menüführung für ein Spiel sind zu programmieren. Wir wollen für jeden Menüpunkt speichern

Der Eintrag des Namens
Das andere Menü wir nach dem Drücken sie erreichen werden.
Die Aktion, die durchgeführt werden würde, wenn das Menü drücken.

Wenn ein Menüpunkt gedrückt wird, werden wir den Menüpunkt Aktion aktivieren und dann zum nächsten Menü. So ist unser Menü wäre eine einfache Liste der Wörterbücher sein, etwa so:

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

Sehen Sie, wie about ist zyklisch:

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

Wenn ein Menüpunkt gedrückt werden wir die folgende Vor-Klick-Funktion ausgeben:

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

Wenn wir jetzt nicht zyklische Datenstrukturen haben würde, würden wir nicht in der Lage sein, einen Menüpunkt zu haben, der auf sich selbst verweist, und zum Beispiel nach der Lautstärke-up-Funktion drücken würden wir die Optionen verlassen müssen Menü.

Wenn die zyklische Datenstrukturen nicht möglich wäre, werden wir es selbst implementieren müssen, zum Beispiel der Menüpunkt wäre:

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

die menu_item_pressed Funktion wäre:

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

Das erste Beispiel ist ein wenig schöner, aber ja, nicht unterstützen Referenzen selbst ist nicht so eine große Sache IMHO, da es einfach ist, diese Einschränkung zu überwinden.

Die Menüs Beispiel ist wie ein Diagramm mit Selbstreferenzen, wo wir die grafische Darstellung von Listen von Vertex Zeigern speichern (jede Ecke ist eine Liste von Zeigern auf andere Knoten). In diesem Beispiel mussten wir selbst Kanten (eine Ecke, die auf sich selbst verweist), so dass Python Unterstützung für die zyklische Datenstrukturen sinnvoll ist.

Die zyklischen Datenstrukturen werden in der Regel darstellen Kreis Beziehungen verwendet. Das klingt offensichtlich, aber es passiert mehr, als Sie denken. Ich kann nicht glauben, von irgendwelchen Zeiten habe ich furchtbar kompliziert zyklische Datenstrukturen verwendet, aber bidirektionale Beziehungen sind relativ häufig. Zum Beispiel nehme ich an ein IM-Client machen wollte. Ich könnte so etwas tun:

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)

Dann, wenn Bob eine Nachricht an Jill schicken wollte, könnte man dies nur tun:

Bob.send("Hi, Jill!")

Natürlich Jill möchte kann eine Nachricht zurück schicken, so konnte sie dies tun:

Jill.send("Hi, Bob!")

Zugegeben, das ist ein bisschen ein konstruiertes Beispiel, aber es sollte Ihnen ein Beispiel geben, wenn Sie möchten, können eine zyklische Datenstruktur verwenden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow