Можно ли заставить cPickle использовать рекурсию в ширину, а не в глубину? - PullRequest
Новая
       10

Можно ли заставить cPickle использовать рекурсию в ширину, а не в глубину?

2 голосов
/ 06 марта 2011

Я понимаю, что ответ, скорее всего, будет «нет»!

По сути, у меня есть график (вид узлов и ребер), который представляет собой сетку квадратов; каждый объект узла содержит ссылки на каждый другой узел, к которому этот узел имеет ребро, что, по-видимому, означает, что когда сериализуется граф с использованием cPickle.dump, он пересекает каждый узел в графе в порядке глубины, что означает, что для скважины -связанный граф, представляющий сетку 16x16, он фактически обрабатывает его как структуру данных глубиной 256 уровней. Это означает, что большие сетки очень быстро выходят за пределы максимальной глубины рекурсии Python, особенно потому, что эксперименты показывают, что кажется, что требуется около 4 вызовов в стеке, чтобы перейти на дополнительный уровень в структуру данных.

Дело в том, что у меня также есть диктат, который ссылается на этот граф таким образом, чтобы позволить мне использовать декартовы координаты для поиска определенных узлов (например, "node = node [3] [6]") ). Таким образом, концептуально, это вовсе не вложенная структура данных, это довольно плоская структура, которая имеет много боковых ссылок, но кажется, что cPickle работает полностью в глубину (что, я понимаю, на сегодняшний день является самым простым способом работа).

Теперь я знаю о sys.setrecursionlimit (), и я провел некоторые эксперименты, чтобы выяснить, насколько большим мне нужно будет установить ограничение на размер графика, так что это самый простой вариант. Я знаю, что мог бы просто выйти из связей между узлами и полагаться на диктовку, чтобы поддерживать сетку и отдельную плоскую структуру, чтобы поддерживать веса ребер, но есть несколько причин, по которым я бы хотел избежать это - не в последнюю очередь, что связи между узлами позволяют более интуитивно использовать структуру данных. Из того, что я прочитал, я полагаю, что я должен быть в состоянии предоставить свои собственные реализации __getstate__ и __setstate__ и переопределить функциональность травления, но, очевидно, это нетривиальный объем работы. Если бы был способ заставить cPickle (или pickle, я не привереда!) Использовать обход в ширину, это решило бы проблему довольно просто!

1 Ответ

1 голос
/ 06 марта 2011

Написание подходящего __getstate__() метода не кажется таким уж сложным. Попробуйте что-то вроде 

class Node(object):
    def __getstate__(self):
        state = self.__dict__.copy()
        state.pop("neighbours")
        return state

Это выберет все атрибуты экземпляра Node, кроме атрибута neighbours, который, как я предполагаю, содержит ссылки на соседей. (Вам не нужен __setstate__() метод.)

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

...