0

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

Improve this question
3
  • 1
    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. Commented Nov 11, 2016 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. Commented Nov 11, 2016 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. Commented Nov 11, 2016 at 14:28

3 Answers 3

Reset to default
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)
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

".. because set in is way faster due to order." What?
@Javier my hands wrote something my head was thinking otherwise :) fixed. thx
let's settle on "an operator eventually implemented by a C function". fixed.
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.

Improve this answer

5 Comments

if it's comparable, you can use bisect, which is in the standard library.
That's useful for searching but if you insert in the middle of a list, it's an O(n) operation.
you are right about that. Given the key name, our only hope is to assume that it is hashable :)
apparently search trees aren't going to happen anytime soon ... stackoverflow.com/questions/17857496/…. But such packages exist: stackoverflow.com/questions/2298165/…
That's fine. Not everything needs to be in the standard lib.
1

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))
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.