Python, how to check object is in list?

Question

I have an object to store data:

Vertex(key, children)

and a list to store this objects

vertices = []

im using another list

key_vertices = []

to store keys of my vertices, so i can easy access(withot looping every object), each time i need to check vertex with such key exist, like that:

if key not in self.key_vertices:
    # add a new key to the array
    self.key_vertices.append(key)
    # create a vertex object to store dependency information
    self.verteces.append(Vertex(key, children))

i think it a bit complicated, maybe someone now better way, to store multiple Vertices objects with ability easy to check and access them

Thanks

Nope. That's about as simple as your gonna get. Don't fall into the trap of thinking there's always a more cleaver way of doing something. What your doing now is perfectly fine. — Christian Dean, Nov 11 '16 at 14:14
@leaf Wow, you again. I would add that this way is actually pretty clever, since it makes use of magic method `__contains__`. OP did not (need to) take advantage of this, but it allows to implement a better or specific behaviour for the `in` operator. — Right leg, Nov 11 '16 at 14:18
@Rightleg That, and his code is already Pythonic. Now if he wants optimizations, then he will have to change a few things. It seems that Jean-François Fabre's covers this pretty well already. — Christian Dean, Nov 11 '16 at 14:28

Jean-François Fabre · Answer 1 · 2016-11-11T14:32:00.193

4

your example works fine, the only problem you could have is a performance issue with the in operator for list which is O(n).

If you don't care about the order of the keys (which is likely), just do this:

self.key_vertices = set()

then:

if key not in self.key_vertices:
    # add a new key to the array
    self.key_vertices.add(key)
    # create a vertex object to store dependency information
    self.verteces.append(Vertex(key, children))

you'll save a lot of time in the in operator because set in is way faster due to key hashing.

And if you don't care about order in self.verteces, just do a dictionary, and in that case, you probably don't need the first key parameter to your Vertex structure.

self.verteces = dict()

if key not in self.verteces:
    # create a vertex object to store dependency information
    self.verteces[key] = Vertex(children)

edited Nov 11 '16 at 14:32

answered Nov 11 '16 at 14:19

Jean-François Fabre

137,073
23
153
219

".. because set in is way faster due to order." What? – Javier Nov 11 '16 at 14:24
@Javier my hands wrote something my head was thinking otherwise :) fixed. thx – Jean-François Fabre Nov 11 '16 at 14:25
let's settle on "an operator eventually implemented by a C function". fixed. – Jean-François Fabre Nov 11 '16 at 14:32

score 1 · Answer 2 · answered Nov 11 '16 at 14:19

1

When you need to check for membership, a list is not the best choice as every object in the list will be checked.

If key is hashable, use a set. If it's not hashable but is comparable, use a tree (unavailable in the standard library). Try to make it hashable.

answered Nov 11 '16 at 14:19

Javier

2,752
15
30

if it's comparable, you can use `bisect`, which _is_ in the standard library. – Jean-François Fabre Nov 11 '16 at 14:20
That's useful for searching but if you insert in the middle of a list, it's an O(n) operation. – Javier Nov 11 '16 at 14:22
you are right about that. Given the `key` name, our only hope is to assume that it is hashable :) – Jean-François Fabre Nov 11 '16 at 14:24
apparently search trees aren't going to happen anytime soon ... http://stackoverflow.com/questions/17857496/built-in-binary-search-tree-in-python. But such packages exist: http://stackoverflow.com/questions/2298165/pythons-standard-library-is-there-a-module-for-balanced-binary-tree – Jean-François Fabre Nov 11 '16 at 14:34
That's fine. Not everything needs to be in the standard lib. – Javier Nov 11 '16 at 14:59

score 1 · Answer 3 · edited Nov 11 '16 at 14:26

If I understand correctly, you want to check if an element has already been added for O(1) (i.e. that you do not have to check every element in the list).

The easiest way to do that is use a set. A set is an unordered list that allows you to check if an element exists with a constant time O(1). You can think of a set like a dict with keys only but it works just like a list:

for value in mySet:
     print(value)

print("hello" in mySet)

If you need an ordered list (most of the time, you don't), your approach is pretty good but I would use a set instead:

self.vertece_set = set() # Init somewhere else ;)

if key not in self.vertece_set:
    # add a new key to the array
    self.vertece_set.add(key)
    # create a vertex object to store dependency information
    self.verteces.append(Vertex(key, children))

Python, how to check object is in list?

3 Answers3