set and dict iteration

[MRAB]

Am 19.08.2012 00:14 schrieb MRAB:

In simple terms, when you create an immutable object it can contain
only references to pre-existing objects, but in order to create a cycle
you need to make an object refer to another which is created later, so
it's not possible to create a cycle out of immutable objects.

Yes, but if I add a list in-between, I can create a refcycle:

a = []
b = (a,)
a.append(b)

So b is a tuple consisting of one list which in turn contains b.

It is not a direct cycle, but an indirect one.

Or would that be detected via the list?

The quote was:

'''
....The tuple type does not implement a tp_clear function, because it’s
possible to prove that no reference cycle can be composed entirely of
tuples.
'''

Note: "composed entirely of tuples".

Or, in general, composed entirely of immutables.

Lists are not immutable, therefore the proof does not apply.

 

[Aaron Brady]

On Thu, 23 Aug 2012 09:49:41 -0700, Aaron Brady wrote:



[...]

The patch for the above is only 40-60 lines. However it introduces two

new concepts.

The first is a "linked list", a classic dynamic data structure, first

developed in 1955, cf. http://en.wikipedia.org/wiki/Linked_list .

Linked lists are absent in Python

They certainly are not. There's merely no named "linked list" class.



Linked lists are used by collections.ChainMap, tracebacks, xml.dom,

Abstract Syntax Trees, and probably many other places. (Well, technically

some of these are trees rather than lists.) You can trivially create a

linked list:



x = [a, [b, [c, [d, [e, None]]]]]



is equivalent to a singly-linked list with five nodes. Only less

efficient.
[snip.]

That's not totally true. Your formulation is equivalent to a single-linked list, but a double-linked list can't be represented as an expression because it contains reference cycles.

Single and double-linked lists have the same requirements for inserting a new node. For instance:

[a, [b, [c, [d, [e, None]]]]]
[a, [a2, [b, [c, [d, [e, None]]]]]]

However, to remove a node, the single-linked list requires iterating over the entire list to find the predecessor of the target, whereas the double-linked list already contains that information.

[a, [b, [c, [d, [e, None]]]]]
[a, [b, [c, [e, None]]]]

The difference might be moot in some applications, such as if we only remove nodes when we're already iterating.

Memory constraints were more severe 50 years ago when the structure was developed. The difference between one pointer and two in a structure could have a big impact in repetition. The single-linked list admits more easily of recursive algorithms as well.

 

[88888 Dihedral]

Paul Rubinæ–¼ 2012å¹´8月17日星期五UTC+8上åˆ9時01分39秒寫é“：

One possible approach is to freeze the dictionary against modification

while any iterator is open on it. You could keep a count of active

iterators in the dict structure, adjusting it whenever an iterator is

created or closed/destroyed.

If there is only one iterator of a frozen dictionary,
then nothing is saved.

But if there are manny iterators based on the same frozen dictionary,
this approach saves a lot.