CODEWITHSUNDEEP
pythonlist
Bastian
Bastian

Reputation: 5855

python lowest cost of checking various equalities at once

I start with a list full of False elements.
Then those elements are switched to True independently over the course of iterations.
I need to know when the list is fully True.

Let's say I have 3 elements, they start as

[False, False, False]

then I check them over the iterations like:

elements == [True, True, True]

The list of elements is fixed and should not grow (or shrink). You can think of these elements as switches, the input determines how many there are and they start all switched off. The only thing that can happen over time is that individual switches are turned on (True) by events happening in the iteration.

How does python do the checking and what is the cost?
What is the best way in terms of cost to check that?
Is there a way with bit operations or anything that checks all the elements at once?

Upvotes: 7

Views: 238

Answers (3)

Dan D.
Dan D.

Reputation: 74655

You could use bit operations to use a number as an array of flag bits. To get this to work we must encode your True as a cleared bit but False as a set bit. This way the number only becomes zero if all the bits are cleared.

This works nicely because the number of flags is fixed. By starting out with an array of set bits you only have to clear them until the number becomes zero.

This trades far faster condition checking for slight bit more complexity and cost in clearing the bits. Testing if a number is zero is far cheaper than applying all to any list of Booleans.

The comments on the question suggested keeping a count and the list. When one of the values becomes true the count either goes up to a final value of the length of the list or goes down from the length of the list to zero. That would work but it is redundant as the same fact is encoded twice once as the count and once as the number of Trues.

This combines the count and the list. It contains no redundancy.

Start out with 5 set bits:

>>> bin((1<<5)-1)
'0b11111'

Then clear them. This clears the 4th bit:

>>> bin(((1<<5)-1) & ~(1 << 3))
'0b10111'

This would allow your loop to have a condition like the following loop:

flags = (1<<5)-1
n = 0
while flags:
   flags &= ~(1<<n)
   print bin(flags)
   n += 1

This loop starts with 5 set bits and clears them one at a time.

>>> flags = (1<<5)-1
>>> n = 0
>>> while flags:
...    flags &= ~(1<<n)
...    print bin(flags)
...    n += 1
... 
0b11110
0b11100
0b11000
0b10000
0b0

Upvotes: 2

John Coleman
John Coleman

Reputation: 51998

You could create your own flag class, one which implements the idea of @StefanPochmann and keeps track of how many flags have been set.

Proof of concept:

class flags:
    def __init__(self,n):
        self.__flags = [False]*n
        self.__ntrue = 0

    def flags(self):
        return self.__flags[:] #so read only

    def __len__(self):
        return len(self.__flags)

    def check(self,i):
        return self.__flags[i]

    def on(self,i):
        if not self.check(i):
            self.__ntrue +=1
            self.__flags[i] = True

    def off(self,i):
        if self.check(i):
            self.__ntrue -=1
            self.__flags[i] = False

    def toggle(self,i):
        if self.check(i):
            self.off(i)
        else:
            self.on(i)

    def ntrue(self):
        return self.__ntrue

Tested like: 

import random

i = 0
f = flags(5)
while f.ntrue() != len(f):
    i +=1
    f.toggle(random.randint(0,4))

print(i,f.flags())

Typical output:

19 [True, True, True, True, True]

Upvotes: 3

SparkAndShine
SparkAndShine

Reputation: 18017

Use all,

>>> l = [True, True, True]
>>> all(l)
True

Notice that if the iterable is empty, it will return True as well.

>>> all([])
True

Upvotes: 4

Related Questions