What type of collection of mutable objects will allow me to quickly remove items in python?

Question

Suppose I have profiled my program, and the vast majority of runtime is spent in method 'remove' of 'list' objects. The program manipulates a collection of collections, and the collections do not need to be ordered. What would be the most straightforward way to implement these collections in python (preferably using standard python collections) so that collection.remove(item) is inexpensive both when collection is the outer collection and item is an inner collection and when collection is an inner collection and item is just an immutable object.

The problem with using sets here is that sets cannot contain mutable collections, so the inner sets would have to be frozensets, but then removing items is no longer so cheap.

The best solution I've come upon so far was suggested by someone as an answer here that apparently was deleted shortly after. They suggested using a dict. This would work, but you would have to generate arbitrary id's for each item then, so it's a bit awkward. Another alternative is to used a linked list, but that would be awkward too, since linked lists aren't part of the standard library.

Answer 1

If you can live with equality defined as identity, you can create a hashable list subtype and use these as set members for fast access/removal:

class hlist(list):
"Hashable list"
    def __hash__(self):
        return id(self)
    def __eq__(self, other):
        return self is other
    def __ne__{self, other}:
        return self is not other

in1 = hlist([1,2,3])
in2 = hlist([4,5,6])
outer = set([in1, in2])

Answer 2

They suggested using a dict. This would work, but you would have to generate arbitrary id's for each item then, so it's a bit awkward.

You delete them by instance? Using a dict approach, you can always use id() as their "arbitrary" ID?

One dict for groups with their id() as key, inner dict for invidual's id(). And another global dict with individuals with their id() as key.

It's not clear if an individual can be in multiple groups... If so, you would need to verify if the invidual is in any group before deleting it.