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

Question

Suppose I have profiled my program, and most of the runtime is spent on the remove method from the list objects. The program manages the collection of collections, and collections do not need to be ordered. What would be the easiest way to implement these collections in python (preferably using standard python collections), so collection.remove (item) is inexpensive when the collection is an external collection and the item is an internal collection, and when the collection is an internal collection and an element is just an immutable object.

The problem with using sets here is that sets cannot contain mutable collections, so there should be freezets for internal sets, but then deleting items is no longer so cheap.

The best solution I came up with was suggested by someone as an answer here, which apparently was deleted shortly after. They suggested using a dict. This will work, but you will have to generate an arbitrary identifier for each element, so this is a bit inconvenient. Another alternative is to use a linked list, but that would also be inconvenient, since linked lists are not part of the standard library.

Answer 1

If you can live with the equality defined as an identifier, you can create a subtype of the hashed list and use them as set items for quick access / deletion:

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 will work, but you will have to generate an arbitrary identifier for each element, so it is a bit inconvenient.

Do you delete them in an instance? Using the dict approach, can you always use id() as your “custom” ID?

One dict for groups with their id() as a key, internal dict for invidual id() . And one more global dict with people with their id() key.

It is not clear whether a person can be in several groups ... If so, you will need to check whether invidual is in any group before deleting it.

Answer 3

A dictionary is a collection that you want in this case, because it O (1) finds and deletes. The costs that you incur will generate a key for each object if you want to add / remove, but it will be much faster than the O (n) list scan method. In this situation, the correct key creation for your objects. If you have a primary key (were they from the database?), Which will negate the hash function to search for properties, and you will achieve near-perfect performance.

You seem to think that using a dictionary as a data structure is bad in this case - it is not at all. The purpose of the dictionary is to quickly find items in the collection. This is what you need, use it.

Answer 4

If you spend a lot of time remove from elements from a list, perhaps you should consider filtering it? In other words. make a large initial list, and then subsequent generators consuming items in the list.

Answer 5

This may not be exactly what you are asking for, but collections.deque may meet some of your requirements:

Deques supports thread-safe, efficient memory, adds and pops up on both sides of the deck with approximately the same O (1) performance in either direction.

Answer 6

Why not have something like a master list of sets , and then another set containing the indices in the list for the set that you want to track? Of course, this may be a little extra work, but you should be able to abstract it into a class.