Início / coding / Perguntas / 79352669
Accepted
Stefan Pochmann
Asked: 2025-01-13 23:24:07 +0800 CST

Como/por que {2,3,10} e {x,3,10} com x=2 são ordenados de forma diferente?

  • 772

Os conjuntos não são ordenados, ou melhor, sua ordem é um detalhe de implementação. Estou interessado nesse detalhe. E vi um caso que me surpreendeu:

print({2, 3, 10})
x = 2
print({x, 3, 10})

Saída ( tente fazer isso online! ):

{3, 10, 2}
{10, 2, 3}

Apesar de elementos idênticos escritos em ordem idêntica, eles são ordenados de forma diferente. Como isso acontece, e isso é feito intencionalmente por algum motivo, por exemplo, para otimizar a velocidade de pesquisa?

Meu sys.versione sys.implementation:

3.13.0 (main, Nov  9 2024, 10:04:25) [GCC 14.2.1 20240910]
namespace(name='cpython', cache_tag='cpython-313', version=sys.version_info(major=3, minor=13, micro=0, releaselevel='final', serial=0), hexversion=51183856, _multiarch='x86_64-linux-gnu')
python

1 respostas

  1. Best Answer

    É uma função de algumas coisas:

    1. Colisões de hash bucket - Para o menor settamanho, 8(detalhe de implementação do CPython), 2e 10colidem em seus códigos hash de corte (que, novamente detalhe de implementação, são 2e 10; mod 8, ambos são 2). Qualquer um que for inserido primeiro "ganha" e obtém o índice de bucket 2, o outro é movido pela operação de sondagem. A operação de sondagem (novamente, detalhe de implementação do CPython) verifica inicialmente os buckets adjacentes linearmente para um bucket vazio (porque geralmente encontra um, e uma melhor localidade de memória melhora o desempenho do cache), e somente se não encontrar um, ele inicia o algoritmo de salto aleatório para encontrar um bucket vazio (ele não pode fazer sondagem linear pura, porque isso tornaria muito fácil disparar casos patológicos que alteram setas operações de caso médio amortizado O(1)para O(n)).

    2. Otimizações em tempo de compilação: No CPython moderno, sets e lists de literais constantes que têm pelo menos três elementos de comprimento são construídos em tempo de compilação como um contêiner imutável ( frozensete tuplerespectivamente). Em tempo de execução, ele constrói um set/ vazio list, então updates/ extends com o contêiner imutável, em vez de executar cargas individuais e adds/ appends para cada elemento. Isso significa que quando você constrói com s = {2, 3, 10}, você está na verdade fazendo s = set(), s.update(frozenset({2, 3, 10}))(com o frozensetpuxado do cache), enquanto s = {x, 3, 10}está construindo carregando x, 3e 10na pilha, então construindo o setcomo uma única operação.

    Os dois significam que você está realmente construindo de forma diferente; {x, 3, 10}está inserindo 2, então 3, então 10, então os buckets 2e 3são preenchidos, e 10são realocados (a estratégia de sondagem claramente o coloca em bucket 0ou 1, antes de bucket 2). Quando você faz {2, 3, 10}, em tempo de compilação ele está criando um frozenset({3, 10, 2}), então em tempo de execução, ele está criando o vazio set, então atualizando-o iterando que frozenset, que já reordenou os elementos , então agora eles não estão mais sendo adicionados em 2, 3, 10ordem, e a corrida por buckets "preferidos" é vencida por elementos diferentes.

    Em resumo, o comportamento de {x, 3, 10}é equivalente a:

    s = set()
s.add(x)
s.add(3)
s.add(10)

    o que previsivelmente dá aos baldes 2 e 3 2e 3eles mesmos, 10sendo deslocados para o balde 0 ou 1.

    Por outro lado, {2, 3, 10}constrói um frozenset({3, 10, 2})(nota: está nessa ordem após a conversão para frozenset; se você tentasse executar essa linha exata e printele, você veria uma ordem diferente), então updates um vazio setcom ele. Há um caminho de código otimizado para preencher um vazio setde outro set/ frozensetque apenas copia o conteúdo diretamente (em vez de iterar e inserir aos poucos), então a {3, 10, 2}ordem no cached frozenseté preservada em cada setcriado a partir dele, o mesmo que se você executasse:

    s = set()
s.update(frozenset({2, 3, 10}))

    mas com melhor desempenho (porque frozenseté criado uma vez em tempo de compilação e carregado de forma barata para cada novo seta ser inicializado).

    • 19

relate perguntas