Как написать оптимизированный код для поиска 2-битовых разреженных чисел?

Question

Есть задача: найти 10**6 двух-битовых чисел в Python, чтобы выполнение кода было разумным по времени.

Если решать в лоб:

from itertools import count

k = 1

for number in count(1):

    if k < (10**3 + 1):

        ones_counter = str(bin(number)).count('1')

        if ones_counter == 2:


            print(f'k: {k}')
            print(f'Число: {number}')
            print(f'Модуль: {number % 35184372089371}')
            print(f'Двоичное: {bin(number)}')

            print(f'---')

            k += 1
    else:
        break

, то на больших дистанциях это нецелесообразно гонять столько пустых переборов.

Есть зависимость:

0b11, 0b101, 0b110, 0b1001, итд,

где слева всегда идет 0b1, а дальше постоянно плавает 1 от правого края до левой 1. и как только она доходит до левой 1, то добавляется сразу в конце еще один символ и 1 начинает передвигаться справа влево, а между ними всегда 0.

Как это сдеалать?

Answer 1

Попробуйте так:

def fun(n):
    high = 1
    while n > 0:
        low = 0
        while low < high:
            yield (1 << high) + (1 << low)
            n -= 1
            if n == 0:
                return
            low += 1
        high += 1

тесты:

In [5]: list(fun(10))
Out[5]: [3, 5, 6, 9, 10, 12, 17, 18, 20, 24]

In [6]: %timeit list(fun(10**6))
536 ms ± 702 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 2

from itertools import count, islice

gen = ((1 << x) | (1 << y) for x in count() for y in range(x))

for x in islice(gen, 0, 10**6):
    print(bin(x))

Answer 3

Перечисляем суммы двух степеней двойки:

def gen():
    a = 1
    while True:
        b = 1
        while b < a:
            yield a + b
            b *= 2
        a *= 2


g = gen()
for _ in range(int(input())):
    print(next(g))

$ echo 10 | python gen.py
3
5
6
9
10
12
17
18
20
24

Две с половиной секунды до миллиона:

$ time echo 1000000 | python gen.py | wc -l
1000000

real  0m2.461s
user  0m2.448s
sys   0m0.188s

БЛОГ НА HUSL

Как написать оптимизированный код для поиска 2-битовых разреженных чисел?

Ответы (3 шт):