循环数据结构有什么用？

发布于 2024-07-10 07:02:35 字数 592 浏览 16 评论 0原文


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

它被识别为循环数据结构。

所以我想知道，这是我的问题：

现实生活编程中使用的“循环数据结构”是什么？

似乎有点混乱，我认为这源于非常简短的代码示例...这里还有几行使用相同的对象 L


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

原文

I was just reading through "Learning Python" by Mark Lutz and came across this code sample:


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

It was identified as a cyclic data structure.

So I was wondering, and here is my question:

What is a 'cyclic data structure' used for in real life programming?

There seems to be a little confusion, which i think stems from the very brief code sample... here's a few more lines using the same object L


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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

梦中的蝴蝶 2024-07-17 07:02:35

很多东西。例如，循环缓冲区：您有一些具有正面和背面的数据集合，但节点数量是任意的，并且最后一个项目的“下一个”项目应该带您回到第一个项目。

图结构通常是循环的；非周期性是一种特殊情况。例如，考虑一个包含旅行推销员问题中的所有城市和道路的图表。

好的，这是一个适合您的特殊示例。我在科罗拉多州建立了一系列城镇：

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

然后我建立了一对有道路连接的城市。

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

这有很多循环。例如，您可以从科罗拉多斯普林斯驾车前往利蒙，再前往丹佛，然后返回科罗拉多斯普林斯。

如果您创建一个包含 V 中的所有城市和 E 中的所有道路的数据结构，那么这就是一个图数据结构。该图会有循环。

Lots of things. Circular buffer, for example: you have some collection of data with a front and a back, but an arbitrary number of nodes, and the "next" item from the last should take you back to the first.

Graph structures are often cyclic; acyclicity is a special case. Consider, for example, a graph containing all the cities and roads in a traveling salesman problem.

Okay, here's a particular example for you. I set up a collection of towns here in Colorado:

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

I then set up pairs of cities where there is a road connecting them.

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

This has a bunch of cycles. For example, you can drive from Colorado Springs, to Limon, to Denver, and back to Colorado Springs.

If you create a data structure that contains all the cities in V and all the roads in E, that's a graph data structure. This graph would have cycles.

回复收藏 0 原文

奈何桥上唱咆哮 2024-07-17 07:02:35

我最近创建了一个循环数据结构来表示八个基本方向和序数方向。对于每个方向了解其邻居很有用。例如，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);
}

证明这非常方便，并且使很多事情变得不那么复杂。

I recently created a cyclic data structure to represent the eight cardinal and ordinal directions. Its useful for each direction to know its neighbors. For instance, Direction.North knows that Direction.NorthEast and Direction.NorthWest are its neighbors.

This is cyclic because each neighor knows its neighbors until it goes full swing around (the "->" represents clockwise):

North -> NorthEast -> East -> SouthEast -> South -> SouthWest -> West -> NorthWest -> North -> ...

Notice we came back to North.

That allows me to do stuff like this (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);
}

This turned out to be quite handy and made a lot of things much less complicated.

回复收藏 0 原文

染火枫林 2024-07-17 07:02:35

嵌套结构可用于垃圾收集器的测试用例。

回复收藏 0 原文

荆棘i 2024-07-17 07:02:35

这有点令人困惑，因为它是一个包含自身的列表，但我理解它的方式是不要将 L 视为列表，而是一个节点，而不是列表中的事物，而是将其视为其他该节点可到达的节点。

举一个更现实的例子，将它们视为来自城市的飞行路径。

因此，芝加哥 = [丹佛、洛杉矶、纽约市、芝加哥]（实际上，您不会列出芝加哥本身，但为了举例，您可以从芝加哥到达芝加哥）

然后您有丹佛 = [菲尼克斯、费城] 和很快。

phoenix = [芝加哥，纽约市]

现在您拥有来自以下位置的循环数据

芝加哥 -> 芝加哥

但也

芝加哥 -> 丹佛 -> 凤凰-> 芝加哥

现在您拥有：

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

It is a bit confusing since it is a list that contains itself, but the way I made sense of it is to not think of L as a list, but a node, and instead of things in a list, you think of it as other nodes reachable by this node.

To put a more real world example, think of them as flight paths from a city.

So chicago = [denver, los angeles, new york city, chicago] (realistically you wouldn't list chicago in itself, but for the sake of example you can reach chicago from chicago)

Then you have denver = [phoenix, philedelphia] and so on.

phoenix = [chicago, new york city]

Now you have cyclic data both from

chicago -> chicago

but also

chicago -> denver -> phoenix -> chicago

Now you have:

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

回复收藏 0 原文

小瓶盖 2024-07-17 07:02:35

确定性有限自动机迭代的数据结构通常是循环的。

回复收藏 0 原文

遇见了你 2024-07-17 07:02:35

L 仅包含对自身的引用作为其元素之一。这没什么特别的。

循环结构有一些明显的用途，其中最后一个元素知道第一个元素。但常规 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', [...]]

L just contains a reference to itself as one of it's elements. Nothing really special about this.

There are some obvious uses of cyclical structures where the last element knows about the first element. But this functionality is already covered by regular python lists.

You can get the last element of L by using [-1]. You can use python lists as queues with append() and pop(). You can split python lists. Which are the regular uses of a cyclical data structure.

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

回复收藏 0 原文

感性 2024-07-17 07:02:35

一个例子是链表，其中最后一个项目指向第一个项目。这将允许您创建固定数量的项目，但始终能够获得下一个项目。

回复收藏 0 原文

瑕疵 2024-07-17 07:02:35

在进行晶格模拟时，经常使用循环/环形边界条件。通常一个简单的格子[i%L]就足够了，但我想可以创建循环的格子。

回复收藏 0 原文

幸福％小乖 2024-07-17 07:02:35

假设您的存储空间有限，并且数据不断积累。在许多现实生活中，您不介意删除旧数据，但不想移动数据。您可以使用循环向量；使用大小为 N 的向量 v 实现，具有两个特殊索引：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
}

Suppose you have limited storage, and data constantly accumulates. In many real life cases, you don't mind getting rid of old data, but you don't want to move data. You can use a cyclic vector; implemented using a vector v of size N with two special indices: begin and end, which initiate on 0.

Insertion of "new" data now goes like this:

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

You can insert "old" data and erase "old" or "new" data in a similar way.
Scanning the vector goes like this

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

回复收藏 0 原文

一腔孤↑勇 2024-07-17 07:02:35

任何类型的对象层次结构，其中父母了解其孩子并且孩子了解其父母。我总是不得不在 ORM 中处理这个问题，因为我希望数据库知道它们的表，也希望表知道它们属于哪个数据库，等等。

回复收藏 0 原文

无法回应 2024-07-17 07:02:35

让我们看一个实际的例子。

假设我们正在为游戏编写菜单导航。我们想要存储每个菜单项

的名称
按下它后我们将到达的另一个菜单。
按菜单时将执行的操作。

当按下菜单项时，我们将激活菜单项操作，然后移至下一个菜单。因此，我们的菜单将是一个简单的字典列表，如下所示：

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对循环数据结构的支持很有用。

Let's look at a single practical example.

Let us say we're programming a menu navigation for a game. We want to store for each menu-item

The entry's name
The other menu we'll reach after pressing it.
The action that would be performed when pressing the menu.

When a menu-item is pressed, we'll activate the menu-item action and then move to the next menu. So our menu would be a simple list of dictionaries, like 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}
    ]

See how about is cyclic:

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

When a menu item is pressed we'll issue the following on-click function:

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

Now, if we wouldn't have cyclic data structures, we wouldn't be able to have a menu item that points to itself, and, for instance, after pressing the volume-up function we would have to leave the options menu.

If cyclic data structures wouldn't be possible, we'll have to implement it ourselves, for example the menu item would be:

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

the menu_item_pressed function would be:

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

The first example is a little bit nicer, but yes, not supporting self references is not such a big deal IMHO, as it's easy to overcome this limitation.

The menus example is like a graph with self references, where we store the graph by lists of vertex pointers (every vertex is a list of pointers to other vertices). In this example we needed self edges (a vertex that points to itself), thus python's support for cyclic data structures is useful.

回复收藏 0 原文

我偏爱纯白色 2024-07-17 07:02:35

循环数据结构通常用来表示循环关系。这听起来很明显，但这种情况发生的次数比你想象的要多。我想不出我曾使用过非常复杂的循环数据结构，但双向关系相当常见。例如，假设我想制作一个 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!")

诚然，这有点像人为的示例，但它应该为您提供何时可能想要使用循环数据结构的示例。

Cyclic data structures are usually used to represent circular relationships. That sounds obvious, but it happens more than you think. I can't think of any times I've used terribly complicated cyclical data structures, but bidirectional relationships are fairly common. For example, suppose I wanted to make an IM client. I could do something like this:

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)

Then if Bob wanted to send a message to Jill, you could just do this: