Comparing sequences with range objects
2QdxY4RzWzUUiLuE at potatochowder.com
2QdxY4RzWzUUiLuE at potatochowder.com
Sun Apr 10 20:44:44 EDT 2022
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.
More information about the Python-list
mailing list