Check if object is already in list (Python)

Question

I have tried searching online for this, but unfortunately have not been able to come up with a solution so far, so I was hoping someone might be able to help me. My basic question is how can I check whether an object is already in a list?

I am currently working on a Rubik's Cube solver, and have created a class called MyCube, where each object has 4 properties:

def __init__(self, cp=None, co=None, ep=None, eo=None):

There are a number of methods for changing the properties, and I have also created methods for __eq__ and __ne__ as follows:

def __eq__(self, other):
    if type(other) is type(self):
        return self.__dict__ == other.__dict__
    return False

def __ne__(self, other):
    return not self.__eq__(other)

I have a list of cubes MyMoveCube = [MyCube() for i in range(18)] and each cube goes through various different transformations. I then have another cube MyNewCube and I want to check whether it is already in MyMoveCube and if not to add it to the list.

I have tried the following, but I find that this gets very slow very quickly as the size of MyMoveCube increases:

for current_move in MyMoveCube:
    if current_move == MyNewCube:
        break
    MyMoveCube.append(MyNewCube)

My question is, is there a better way to do this without looping through it each time?

Why not simply use if MyNewCube in MyMoveCube:...? This will first check the identity and then will call __eq__ if required. — Ashwini Chaudhary
– Ashwini Chaudhary, Commented May 23, 2015 at 1:48
Sets are great for non-repeating data which you check for membership a lot, e.g., if x in y. — Lillian Seabreeze
– Lillian Seabreeze, Commented May 23, 2015 at 1:51

user2357112 · Accepted Answer · 2015-05-23 02:17:59Z

2

If you want to do something if MyNewCube is already in MyMoveCube,

if MyNewCube in MyMoveCube:
    do_whatever()

or if you want to do something if it isn't,

if MyNewCube not in MyMoveCube:
    do_whatever()

(I initially didn't see the part about running into speed problems; this answer just demonstrates in syntax. Testing lists for containment is horribly slow; for efficiency, see the other answer.)

edited May 23, 2015 at 2:17

answered May 23, 2015 at 1:48

user2357112

286k32 gold badges490 silver badges571 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Gemma Down Over a year ago

I have tried using this, but it doesn't appear to work. It doesn't ever seem to think that there is an equality there unfortunately.

user2357112 Over a year ago

@GemmaDown: Then you've done something else wrong. Your __eq__ and __ne__ methods look like they should work.

Gemma Down Over a year ago

Thanks for this - I think there must have been something else happening as this method is now working! Very glad to know that this will work too.

Martin Konecny · Accepted Answer · 2015-05-23 02:15:44Z

1

"but I find that this gets very slow very quickly as the size of MyMoveCube increases"

You will want to look into using a set to store your MyCube instances.

MyMoveCube = set([MyCube() for i in range(18)])

Hashing an object and checking whether it's in a set is a very efficient operation - O(1) in the average case compared to O(n) in the average case for a list.

You can still use the same in operators with a set, with much faster lookup:

if MyNewCube in MyMoveCube:
    # in cube

EDIT:

If you need to keep track of the order of the items in the set, you could possibly use a set AND a list. The list for tracking the order and the set for testing membership.

edited May 23, 2015 at 2:15

answered May 23, 2015 at 1:52

Martin Konecny

59.9k20 gold badges144 silver badges159 bronze badges

4 Comments

Gemma Down Over a year ago

Thank you very much for this as well! Unfortunately I needed to keep the order of the cubes that I had for specific reference, so I wouldn't have been able to use a set in this instance, but this looks really useful, and is something I will certainly use elsewhere.

Martin Konecny Over a year ago

@GemmaDown why not use a list for keeping track of the order, and a set for when you want to test membership? You get the best of both worlds.

user2357112 Over a year ago

@GemmaDown: You can keep a set and a list, using the set to test for containment efficiently and using the list to track order. Alternatively, depending on how much control you need over the element order, collections.OrderedDict might do the job.

Gemma Down Over a year ago

Thanks for the help! I will look into doing that.

Collectives™ on Stack Overflow

Check if object is already in list (Python)

2 Answers 2

3 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related