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

https://stackoverflow.com/questions/405540

03-07-2019
|

Вопрос

я просто читал «Изучение Python» Марка Лутца и наткнулся на этот пример кода.:


>>> 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, это будет график структура данных.Этот граф будет иметь циклы.

Другие советы

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

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

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

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

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

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

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

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

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

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

но и

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

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

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

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

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

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

при моделировании решетки часто используются циклические/тороидальные граничные условия.обычно простой lattice[i%L] было бы достаточно, но я полагаю, что можно было бы создать циклическую решетку.

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

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

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

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

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

При нажатии пункта меню мы активируем действие пункта меню и затем переходим к следующему меню.Таким образом, наше меню будет представлять собой простой список словарей, например:

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