Improving Python Comparison and Existence Operations

Question

I'm fairly new to Python and was hoping I could get some advice before moving forward. I have a group of integers and I want to check whether or not a given element is contained within that group as fast as possible (speed does matter here).

With Python, should I be looking at custom data structures tailored for these operations (BST, etc), python trickery like wrapping with any(), or are there any well known Python/C libraries that are standard for this sort of thing. I don't want to reinvent the wheel here, so I'm interested to hear the common way to approach this in Python.

A little more background, elements are all inserted into the group up front, and none occur thereafter, so insertion time doesn't matter. This seems to imply that maintaining a sorted group and doing something like binary search will be the best approach, but I'm sure this has already been implemented much more efficiently than I could implement and is available in a Python/C lib. Interested to hear what you guys think.

Thanks!

Answer 1

As DMS says in the comment, there's a built-in set (and the immutable variant, frozenset, which is very useful you don't need to mutate and can fit the generation of the values into a single generator expression). It's hash-based and therefore sacrifices order for amortized O(1) membership testing. It's written in C and more time went into making it fast than you could reasonably spend at all on it. If memory serves right, it's based on the dictionary implementation, which is propably among the fastet hash tables (for common usage) in existence.

Note that the "hash" part will be O(1) too, as integers hash to themselves. The algorithms are tailored to handling "non-random" (e.g. somewhat consecutive) hashes very well.