It might not be that surprising to use a list if you are already using that list to keep track of your position in the hierarchy. You can probably assume that most of the time the depth is fairly low so the cost of scanning is low enough that the cost of building and updating the set costs enough that there aren't significant savings.
On 1/1/21 7:38 PM, Samuel Freilich via Python-ideas wrote: > Interesting to look at the code for some of this. > > list.repr and dict.repr seem to be taking the "construct a set of seen > items" approach. Except it's not using a set of ids, it's doing a > linear pass over a list of visited PyObjects each time (which seems > somewhat surprising to me, though it's only O(n*d) where d is the > nesting depth, not O(n^2)): > https://github.com/python/cpython/blob/3bf05327c2b25d42b92795d9d280288c22a0963d/Objects/object.c#L1974 > <https://github.com/python/cpython/blob/3bf05327c2b25d42b92795d9d280288c22a0963d/Objects/object.c#L1974> > > copy.deepcopy keeps track with a dict: > https://github.com/python/cpython/blob/3bf05327c2b25d42b92795d9d280288c22a0963d/Lib/copy.py#L138 > <https://github.com/python/cpython/blob/3bf05327c2b25d42b92795d9d280288c22a0963d/Lib/copy.py#L138> > > (That uses a sentinel object as the default for the lookup so it can > tell if that's explicitly set to None, though that seems convoluted > compared to just checking whether the value is None or not. Is that > considering that "copy.deepcopy(x) is None and x is not None" might be > true?) > > Peace, > -Sam > > On Fri, Jan 1, 2021 at 7:07 PM Greg Ewing <greg.ew...@canterbury.ac.nz > <mailto:greg.ew...@canterbury.ac.nz>> wrote: > > On 2/01/21 6:14 am, Jeff Allen wrote: > > we may as > > well say that the required result takes the form of an iterable > of the > > nodes, which may subsequently be iterated by a consumer. > > In general you need more than that, I think. If you're printing > a representation of the graph, you want to know about the structure, > not just get a flat list of nodes. > > > But we must have to do something > > very similar to pickle arbitrary (potentially cyclic) > structures, which > > is likewise dependent on special help from the particular > built-in type. > > Can something be founded on |||__getstate__| ? > > I don't think so. All the logic for dealing with cycles is buried > inside pickle -- __getstate__ just gets info about one object. > > -- > Greg > -- Richard Damon _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/M55CUGTDN56E34WJANQ4CZZPKPBDMP74/ Code of Conduct: http://python.org/psf/codeofconduct/
