On 2022-04-10 at 22:20:33 +0200, Antoon Pardon <antoon.par...@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. -- https://mail.python.org/mailman/listinfo/python-list
