Для чего нужна циклическая структура данных? - PullRequest
Новая
       49

Для чего нужна циклическая структура данных?

14 голосов
/ 02 января 2009

Я только что прочитал "Learning Python" Марка Лутца и наткнулся на этот пример кода : 


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

Он был идентифицирован как циклическая структура данных.

Так мне было интересно, и вот мой вопрос:

Для чего используется «циклическая структура данных» в программировании в реальной жизни?

Кажется, есть небольшая путаница, которая, я думаю, проистекает из очень короткого примера кода ... вот еще несколько строк, использующих тот же объект L 


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

Ответы [ 12 ]

18 голосов
/ 02 января 2009

много вещей. Круговой буфер, например: у вас есть некоторая коллекция данных с передней и задней частями, но с произвольным числом узлов, и «следующий» элемент из последнего должен вернуть вас к первому.

Графовые структуры часто являются циклическими; ацикличность - это особый случай. Рассмотрим, например, график, содержащий все города и дороги в задаче коммивояжера.

Хорошо, вот вам конкретный пример. Я создал коллекцию городов здесь, в Колорадо: 

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

Затем я создал пары городов, в которых есть дорога, соединяющая их. 

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

У этого есть куча циклов. Например, вы можете ехать из Колорадо-Спрингс в Лимон, в Денвер и обратно в Колорадо-Спрингс.

Если вы создаете структуру данных, которая содержит все города в V и все дороги в E, это структура данных graph . Этот график будет иметь циклы.

6 голосов
/ 02 января 2009

Недавно я создал циклическую структуру данных для представления восьми основных и порядковых направлений. Полезно для каждого направления знать своих соседей. Например, 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);
}

Это оказалось довольно удобно и сделало многое намного менее сложным.

1 голос
/ 28 мая 2009

Структуры данных, повторяемые детерминированными конечными автоматами , часто цикличны.

1 голос
/ 28 мая 2009

L просто содержит ссылку на себя как на один из своих элементов. Ничего особенного в этом нет.

Существует несколько очевидных применений циклических структур, когда последний элемент знает о первом элементе. Но эта функциональность уже покрыта обычными списками Python.

Вы можете получить последний элемент L, используя [-1]. Вы можете использовать списки Python как очереди с append() и 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', [...]]
1 голос
/ 28 мая 2009

Это немного сбивает с толку, так как это список, который содержит сам себя, но, как я понял, это не думать о L как о списке, а как о узле, и вместо вещей в списке, вы думаете о это как другие узлы, достижимые этим узлом.

Чтобы привести пример более реального мира, подумайте о них как о путях полета из города.

Итак, Чикаго = [Денвер, Лос-Анджелес, Нью-Йорк, Чикаго] (реально вы бы не указали Чикаго в себе, но ради примера вы можете добраться до Чикаго из Чикаго)

Тогда у вас есть Денвер = [Феникс, Филидельфия] и так далее.

Феникс = [Чикаго, Нью-Йорк]

Теперь у вас есть циклические данные как от

Чикаго -> Чикаго

но также

Чикаго -> Денвер -> Феникс -> Чикаго

Теперь у вас есть: 

chicago[0] == denver
chicago[0][0] == phoenix
chicago[0][0][0] == chicago
1 голос
/ 02 января 2009

Вложенная структура может использоваться в тестовом примере для сборщика мусора.

0 голосов
/ 28 мая 2009

Давайте рассмотрим один практический пример.

Допустим, мы программируем навигацию по меню для игры. Мы хотим хранить для каждого пункта меню

  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 для циклических структур данных полезна.

0 голосов
/ 28 мая 2009

Любая иерархия объектов, где родители знают о своих детях, а дети знают о своих родителях. Мне всегда приходится иметь дело с этим в ORM, потому что я хочу, чтобы базы данных знали свои таблицы, а таблицы знали, в какую базу данных они входят, и так далее.

0 голосов
/ 28 мая 2009

Циклические структуры данных обычно используются для представления циклических отношений. Это звучит очевидно, но это происходит больше, чем вы думаете. Я не могу вспомнить ни разу, когда использовал ужасно сложные циклические структуры данных, но двунаправленные отношения довольно распространены. Например, предположим, я хотел сделать 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!")

Правда, это немного надуманный пример, но он должен дать вам пример того, когда вы можете захотеть использовать циклическую структуру данных.

0 голосов
/ 02 января 2009

Предположим, у вас ограниченное хранилище и данные постоянно накапливаются. Во многих реальных случаях вы не возражаете избавиться от старых данных, но вы не хотите перемещать данные. Вы можете использовать циклический вектор; реализовано с использованием вектора v размера N с двумя специальными индексами: начало и конец, которые начинаются с 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
}
Страница:
...