14

Mark Lutzによる「LearningPython」を読んでいて、このコードサンプルに出くわしました。


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

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

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

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

少し混乱しているようですが、これは非常に短いコードサンプルに起因すると思います...同じオブジェクトLを使用した行がさらに数行あります


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

12 に答える 12

17

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

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

さて、ここにあなたのための特定の例があります。ここコロラド州に町のコレクションを設定しました。

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

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

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

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

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

于 2009-01-01T22:17:30.567 に答える
6

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

これは、各隣人がフルスイングするまでその隣人を知っているため、循環的です (「->」は時計回りを表します)。

北 -> 北東 -> 東 -> 南東 -> 南 -> 南西 -> 西 -> 北西 -> 北 -> ...

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

これにより、（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);
}

これは非常に便利であることが判明し、多くのことがより簡単になりました。

于 2009-01-01T22:21:42.600 に答える
1

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

于 2009-01-01T22:18:04.310 に答える
1

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

于 2009-05-27T23:35:20.757 に答える
1

L要素の 1 つとして自分自身への参照が含まれているだけです。これについては特に何もありません。

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

Lを使用して の最後の要素を取得できます[-1]。append()およびを使用して、python リストをキューとして使用できますpop()。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', [...]]
于 2009-05-27T22:38:53.210 に答える
0

循環データ構造は通常、循環関係を表すために使用されます。当たり前のように聞こえますが、思った以上に起こります。非常に複雑な循環データ構造を使用したことはありませんが、双方向の関係はかなり一般的です。たとえば、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!")

確かに、これは少し不自然な例ですが、循環データ構造を使用する場合の例を示すはずです。

于 2009-05-27T21:27:11.453 に答える
0

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

于 2009-05-27T21:32:23.500 に答える
0

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

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

  1. エントリの名前
  2. それを押した後に到達する他のメニュー。
  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による循環データ構造のサポートが役立ちます。

于 2009-05-28T07:00:04.310 に答える
0

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

于 2009-01-01T22:17:08.897 に答える
0

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

于 2009-01-01T22:17:42.157 に答える
0

ストレージが限られており、データが絶えず蓄積されているとします。多くの実際のケースでは、古いデータを削除しても問題ありませんが、データを移動したくはありません。巡回ベクトルを使用できます。サイズ N のベクトル v を使用して実装され、2 つの特別なインデックス: begin と end が 0 で開始されます。

「新しい」データの挿入は次のようになります。

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

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

for (i=begin; i != end; i = (i+1) % N) {
 // do stuff
}
于 2009-01-01T22:37:49.637 に答える