Início / coding / Perguntas / 79494345
Accepted
Ξένη Γήινος
Asked: 2025-03-08 20:03:28 +0800 CST

Como contar os primeiros N números naturais em binário?

  • 772

Isso pode parecer trivial, mas não encontrei uma boa solução para o problema. Eu até encontrei isso: gere todos os números binários de n bits da maneira mais rápida possível . mas não encontrei uma duplicata exata.

O problema é muito simples: dado um limite N que seja um inteiro positivo, gere a representação binária de cada número natural até N em ordem (excluindo N, o primeiro número natural é 0, então N - 1 é o número máximo a ser representado), na tupleforma, com cada tupla preenchida com zeros à esquerda para que todas as representações tenham o mesmo comprimento.

Por exemplo, se Nfor 4, a saída deverá ser [(0, 0), (0, 1), (1, 0), (1, 1)].

Neste ponto, o problema é de fato trivial, mas há um porém: não são permitidos " bin(n)e f'{n:b}'" e "afins". O algoritmo deve operar inteiramente no domínio binário, porque, pelo que entendi, tudo (texto, fotos, música, vídeos...) em computadores são numerais binários, então converter representações de um lado para o outro está adicionando cálculos desnecessários. Esses cálculos (conversão de base) são completamente redundantes e devem ser eliminados para produzir o programa mais eficiente (trata-se de manter os problemas específicos para o menor número possível de domínios, para que possamos operar apenas nesses domínios).

Eu escrevi um programa simples que faz exatamente o que descrevo:

from typing import Generator, Tuple

def count_in_binary(n: int) -> Generator[Tuple[int, ...], None, None]:
    if not isinstance(n, int) or n < 1:
        raise ValueError("The argument n must be a positive integer")

    l = (n - 1).bit_length() if n > 1 else 1
    numeral = [0] * l
    maxi = l - 1
    for _ in range(n):
        yield tuple(numeral)
        i = maxi
        while True:
            if not (d := numeral[i]):
                numeral[i] = 1
                break
            else:
                numeral[i] = 0
                i -= 1

Mas não tenho certeza se essa é a maneira mais eficiente de fazer isso em Python. Não usei muitas operações de bits e os computadores já representam números como binários, então deve haver maneiras mais rápidas de fazer isso.

A questão é: qual é o caminho mais rápido?

Para efeito de comparação, aqui está uma maneira que usa f'{n:b}' e, portanto, é mais concisa, mas na verdade é muito mais lenta e estúpida:

def count_in_binary1(n: int) -> Generator[Tuple[int, ...], None, None]:
    if not isinstance(n, int) or n < 1:
        raise ValueError("The argument n must be a positive integer")

    l = len(f'{n-1:b}')
    for i in range(n):
        yield tuple(map(int, f'{i:0{l}b}'))

In [50]: %timeit list(count_in_binary(256))
59.9 μs ± 209 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [51]: %timeit list(count_in_binary1(256))
452 μs ± 3.68 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Editar

Não fiz muitos testes com a função original, apenas pensei que funcionaria, agora está corrigido.

E não, o escopo do escopo é limitado ao Python puro, então o NumPy não é permitido.

Editar 2

Agora acho que não há exceções.

Votei positivamente e aceitei a segunda resposta, pois ela responde à pergunta original, embora a pergunta original não inclua todas as informações relevantes, então o problema que eu estava tentando resolver postando uma pergunta continua sem solução.

Publiquei uma nova pergunta sem todas as informações relevantes. Por favor, responda: Qual é a maneira mais rápida de encontrar todas as permutações de 0, 1 de largura n sem itertools em Python puro?

python

2 respostas

  1. Cheguei a essa solução usando inteiramente funções integradas:

    def count_in_binary(n) -> iter[tuple]:
    if not isinstance(n, int) or n < 1:
        raise ValueError('The argument n must be a positive integer.')
    
    o = []
    for t in range((n-1).bit_length()-1, -1, -1):
        block_size = 2**t
        period = [0]*block_size + [1]*block_size
        q, r = divmod(n, 2*block_size)
        o.append( block*q + block[:r] )

    return zip(*o)

    e estes são os resultados da bancada projetada por no comment ):

    Do Colab (tudo parece estável)

    Version      n=50         n=256        n=1000       n=5000      n=7500       n=10000     
------------------------------------------------------------------------------------------
original     7.092        36.695       150.360      836.957      1303.160     1764.156    
no_comment   2.455        11.919        45.721      303.794       482.383      682.284     
Sash_Sinha  40.014       225.721      1006.889     6735.926     10929.236    15004.871   
cards        8.226        32.446       131.652      885.364      1308.538     1930.887

    Do meu PC

    Version      n=50         n=256        n=1000       n=50000      n=7500       n=10000     
------------------------------------------------------------------------------------------
original     19.826       95.492       459.792      2849.338     4399.717     6105.478    
no_comment    8.190       28.310        99.069       873.893     1444.020     2043.485    
Sash_Sinha  145.806      810.397      3568.845     24405.219    37215.727    52120.108   
cards        27.163       77.026       232.923      1683.323     2685.508     4003.884

    Observe que n=1minha implementação retorna simplesmente a []porque não está claro como 0 deve ser representado em uma forma de tupla.

    • 1
  2. Best Answer

    Com itertools:

    def count_in_binary(n: int) -> Iterator[Tuple[int, ...]]:
    if not isinstance(n, int) or n < 1:
        raise ValueError("The argument n must be a positive integer")

    L = (n-1).bit_length() or 1
    return islice(product((0, 1), repeat=L), n)

    Resultados de benchmark e código:

     47 μs  count_in_binary__original
 15 μs  count_in_binary__no_comment
345 μs  count_in_binary__Sash_Sinha

    from typing import Generator, Tuple, Iterator
from itertools import *


def count_in_binary__original(n: int) -> Generator[Tuple[int, ...], None, None]:
    if not isinstance(n, int) or n < 1:
        raise ValueError("The argument n must be a positive integer")

    l = (n - 1).bit_length() if n > 1 else 1
    numeral = [0] * l
    maxi = l - 1
    for _ in range(n):
        yield tuple(numeral)
        i = maxi
        while True:
            if not (d := numeral[i]):
                numeral[i] = 1
                break
            else:
                numeral[i] = 0
                i -= 1


def count_in_binary__no_comment(n: int) -> Iterator[Tuple[int, ...]]:
    if not isinstance(n, int) or n < 1:
        raise ValueError("The argument n must be a positive integer")

    L = (n-1).bit_length() or 1
    return islice(product((0, 1), repeat=L), n)


def count_in_binary__Sash_Sinha(n: int) -> Generator[Tuple[int, ...], None, None]:
    """Yield binary tuples for 0 to n-1 with width = bit-length of n-1."""
    if not isinstance(n, int) or n < 1:
        raise ValueError('The argument n must be a positive integer.')
    bit_length = (n - 1).bit_length() or 1
    for i in range(n):
        yield tuple((i >> j) & 1 for j in range(bit_length - 1, -1, -1))


funcs = [
    count_in_binary__original,
    count_in_binary__no_comment,
    count_in_binary__Sash_Sinha,
]

for n in range(1, 100):
    expect = list(count_in_binary__original(n))
    for f in funcs:
        result = list(f(n))
        if result != expect:
            print(n, f.__name__, result)

import timeit
for f in funcs:
    t = min(timeit.repeat(lambda: list(f(256)), number=10**3)) * 1e3
    print(f'{t:3.0f} μs ', f.__name__)

    Tente isso online!

    • 0

relate perguntas