循環データ構造は何に適していますか？

StackOverflow https://stackoverflow.com/questions/405540

質問

＆quot; Pythonを学ぶ＆quot;マーク・ルッツによってこのコードサンプルに出くわしました：


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

循環データ構造として識別されました。

だから私は疑問に思っていました、そしてここに私の質問があります：

実際のプログラミングで使用される「循環データ構造」とは何ですか？

少し混乱しているように見えますが、これは非常に短いコードサンプルに起因すると考えられます...同じオブジェクトLを使用するいくつかの行があります


>>> L[0]
'grail'
>>> L[1][0]
'grail'
>>> L[1][1][0]
'grail'
役に立ちましたか？

解決

多くのもの。たとえば、循環バッファ：前面と背面を持つデータのコレクションがありますが、ノードの数は任意で、「次」は最後からのアイテムは最初に戻ります。

グラフ構造はしばしば循環的です。非周期性は特別な場合です。たとえば、巡回セールスマン問題のすべての都市と道路を含むグラフを考えてみましょう。

さて、これはあなたのための特定の例です。ここコロラド州の町のコレクションをセットアップしました：

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

次に、それらを結ぶ道路がある都市のペアを設定します。

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

これには多数のサイクルがあります。たとえば、コロラドスプリングスからリモン、デンバー、そしてコロラドスプリングスに戻ることができます。

Vのすべての都市とEのすべての道路を含むデータ構造を作成する場合、それはグラフデータ構造です。このグラフにはサイクルがあります。

他のヒント

最近、8つの基本方向と順序を表す循環データ構造を作成しました。各方向が隣人を知るのに役立ちます。たとえば、Direction.Northは、Direction.NorthEastとDirection.NorthWestが隣接していることを知っています。

各ネイバーはフルスイングするまで隣人を知っているので、これは周期的です（「-&>」は時計回りを表します）：

北-＆gt;ノースイースト-＆gt;東-＆gt;サウスイースト-＆gt;南-＆gt;南西-＆gt;西-＆gt;北西-＆gt;北-＆gt; ...

北に戻ったことに注意してください。

これにより、次のようなことができます（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);
}

これは非常に便利であることが判明し、多くのことがそれほど複雑ではなくなりました。

ガベージコレクターのテストケースでは、ネストされた構造を使用できます。

それはそれ自体を含むリストなので少し混乱しますが、私がそれを理解した方法は、Lをリストではなくノードと考え、リスト内の物の代わりに考えることですこのノードから到達可能な他のノードとして。

より現実的な例を挙げると、都市からの飛行経路と考えてください。

つまり、chicago = [デンバー、ロサンゼルス、ニューヨーク、シカゴ]（現実には、シカゴ自体はリストしませんが、例として、シカゴからシカゴにアクセスできます）

その後、デンバー= [フェニックス、フィレデルフィア]などとなります。

phoenix = [シカゴ、ニューヨーク市]

今、あなたは両方からの循環データを持っています

  

シカゴ-＆gt;シカゴ

また

  

シカゴ-＆gt;デンバー-＆gt;フェニックス-＆gt;シカゴ

次のようになりました：

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

決定論的有限オートマトンによって反復されるデータ構造は、多くの場合循環的です。

L には、その要素の1つとして自身への参照のみが含まれています。これについて特別なことは何もありません。

最後の要素が最初の要素について知っている循環構造のいくつかの明らかな使用があります。しかし、この機能はすでに通常のpythonリストでカバーされています。

[-1] を使用して、 L の最後の要素を取得できます。 append（）および pop（）を使用して、Pythonリストをキューとして使用できます。 Pythonリストを分割できます。循環データ構造の通常の使用方法。

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

1つの例は、最後の項目が最初の項目を指すリンクリストです。これにより、一定数のアイテムを作成できますが、常に次のアイテムを取得できます。

格子シミュレーションを行う場合、周期的/トロイダル境界条件がよく使用されます。通常、単純な lattice [i％L] で十分ですが、循環するようにラティスを作成できると思います。

ストレージが限られており、データが常に蓄積されているとします。多くの実際のケースでは、古いデータを削除してもかまいませんが、データを移動する必要はありません。循環ベクトルを使用できます。 2つの特別なインデックスを持つサイズNのベクトルvを使用して実装されます：beginとend、0で始まります。

＆quot; new＆quot;の挿入データは次のようになります。

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

＆quot; old＆quot;を挿入できますデータと消去「古い」または＆quot; new＆quot;同様の方法でデータ。 ベクターのスキャンは次のようになります

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

親が自分の子供について知っており、子供が親について知っているあらゆる種類のオブジェクト階層。データベースがテーブルを認識し、テーブルがどのデータベースに属しているかなどを知りたいので、私は常にORMでこれに対処する必要があります。

1つの実用的な例を見てみましょう。

ゲームのメニューナビゲーションをプログラミングしているとしましょう。メニュー項目ごとに保存したい

  1. エントリの名前
  2. もう1つのメニューは、押すと表示されます。
  3. メニューを押したときに実行されるアクション。

メニュー項目を押すと、メニュー項目アクションがアクティブになり、次のメニューに移動します。したがって、メニューは次のような辞書の単純なリストになります。

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

about の周期性を確認してください：

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

メニュー項目が押されると、次のオンクリック機能が発行されます。

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

今、周期的なデータ構造がない場合、それ自体を指すメニュー項目を使用することはできません。たとえば、ボリュームアップ機能を押した後、オプションを残す必要があります。メニュー。

循環データ構造が不可能な場合は、自分で実装する必要があります。たとえば、メニュー項目は次のようになります。

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

menu_item_pressed 関数は次のようになります。

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

最初の例はもう少し良いですが、はい、この制限を克服するのは簡単なので、自己参照をサポートしないことはそれほど大したことではありません。

メニューの例は、自己参照を持つグラフのようなものです。ここでは、頂点ポインターのリストによってグラフを保存します（すべての頂点は、他の頂点へのポインターのリストです）。この例では、セルフエッジ（それ自体を指す頂点）が必要でした。したがって、Pythonの循環データ構造のサポートは便利です。

循環データ構造は通常、循環関係を表すために使用されます。それは明白に聞こえますが、それはあなたが思っている以上に起こります。ひどく複雑な循環データ構造を使用したことは考えられませんが、双方向の関係はかなり一般的です。たとえば、IMクライアントを作成したいとします。このようなことができます：

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)

その後、ボブがジルにメッセージを送信したい場合、これを行うことができます：

Bob.send("Hi, Jill!")

もちろん、ジルはメッセージを送り返したいと思うかもしれません。 

Jill.send("Hi, Bob!")

確かに、これは少し不自然な例ですが、循環データ構造を使用したい場合の例を示す必要があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top