Comparing sequences with range objects

[2QdxY4RzWzUUiLuE at potatochowder.com]

On 2022-04-10 at 22:20:33 +0200,
Antoon Pardon <antoon.pardon at vub.be> wrote:

> 
> 
> Op 9/04/2022 om 02:01 schreef duncan smith:
> > On 08/04/2022 22:08, Antoon Pardon wrote:
> > > 
> > > Well my first thought is that a bitset makes it less obvious to calulate
> > > the size of the set or to iterate over its elements. But it is an idea
> > > worth exploring.
> > > 
> > 
> > 
> > 
> > def popcount(n):
> >     """
> >     Returns the number of set bits in n
> >     """
> >     cnt = 0
> >     while n:
> >         n &= n - 1
> >         cnt += 1
> >     return cnt
> > 
> > and not tested,
> > 
> > def iterinds(n):
> >     """
> >     Returns a generator of the indices of the set bits of n
> >     """
> >     i = 0
> >     while n:
> >         if n & 1:
> >             yield i
> >         n = n >> 1
> >         i += 1
> > 
> Sure but these seem rather naive implementation with a time complexity of
> O(n) where n is the maximum number of possible elements. Using these would
> turn my O(n) algorithm in a O(n^2) algorithm.

O(n) where n is the expected number of elements.  The loops iterate once
for each bit actually contained in the set, which is usually [much] less
than the size of the universe.  If you have lots and lots of elements in
your sets, or your universe is large and n is a long integer, then these
may not be as efficient as other methods.  You know your data better
than we do.