Por que os conjuntos e dicionários Python não são ordenados por padrão?

A questão não é que a sobrecarga seja particularmente grande, mais do que existe em tudo .

Os recursos de linguagem devem sempre atingir um equilíbrio de custo-benefício. Os dicionários são absolutamente fundamentais para a programação Python, então seria muito ruim para eles serem um pouco mais lentos do que deveriam ser apenas para preservar a ordem de inserção, quando na maioria das vezes você não precisa de pedidos. Foi a decisão correta descartar a ordem de inserção em troca de um acesso um pouco mais rápido e deixar a estrutura de dados que preserva a ordem para classes especiais. Se houvesse outra estrutura de dados que pudesse fazer tudo isso, um dict pode, e o dict fosse um aspecto menos usado da linguagem, coisas pode parecer diferente.

Comentários

• Meu contra-argumento para isso seria: use um tipo de dados dict não ordenado mais eficiente para dicionários internos (como lá ‘ s deque para otimizar o desempenho em alguns outros contextos), mas deixe o tipo de dados dict voltado para o usuário principal preservar a ordem.
• Além disso, estou certo em entender que a implementação do CPython 3.6, de fato, preserva a ordem de inserção para ditos?

Você está correto ao dizer que os itens são armazenados internamente com algum pedido, mas esse pedido interno é determinado pelo código hash da chave, que é o que permite que a recuperação seja tão rápida. Portanto, se um conjunto / dicionário deve ser ordenado, ele precisa manter uma estrutura de dados interna separada (digamos uma lista ordenada de chaves) para isso.

Isso, é claro, aumentaria o tamanho. Mas talvez pior, afetará o desempenho. Por exemplo, remover um item de um conjunto é uma operação O (1), mas se também tiver que remover a chave de uma lista ordenada interna, ela se tornará O (n). Esse custo seria desastroso para algumas aplicações. Dado que é muito raro você precisar de um conjunto ordenado, tal troca não vale a pena para os tipos de conjunto / dicionário padrão.

Sua premissa está incorreta. No Python 3.6, dict s lembram de sua ordem de inserção . Este era um detalhe de implementação e foi promovido a recurso de linguagem completa no 3.7. Em 3.6, para o caso específico de **kwargs, a preservação do pedido é especificamente garantida.

Comentários

• Sim, eu não estava ‘ ciente disso quando fiz a pergunta, já que ‘ ainda não é um recurso de linguagem, apenas uma implementação detalhes em uma implementação. Mas parece que pelo menos os dicionários ficarão ordenados a longo prazo e, com sorte, também os conjuntos.
• @oulenz it ‘ não é mais um detalhe de implementação, é ‘ s exigido no Python 3.7

Um ordenado set só é possível quando os elementos a serem armazenados têm uma ordem (ou seja, um método de comparação) em primeiro lugar – mas isso nem sempre é um dado.

A implementação padrão de set / map na maioria dos ambientes hoje em dia é com base em uma hashtable de redimensionamento automático, que tem as seguintes vantagens:

• mais rápido
• usa menos memória
• não requer os elementos para fornecer uma ordem

os conjuntos devem ser armazenados internamente com algum pedido de qualquer maneira

Mas essa ordem interna não tem necessariamente nenhum significado, nem permanece a mesma. Na verdade, uma propriedade de hashtables que às vezes confunde desenvolvedores inexperientes é que a ordem de iteração, que é baseada na ordem interna, pode mudar completamente quando os elementos são adicionados (ou seja, quando um redimensionamento é acionado) ou entre diferentes corre.

Comentários

• Não ‘ não entendo seu primeiro comentário. Não ‘ não precisamos de um método de comparação, a ordem pode ser apenas herdada, por exemplo, de uma lista ou string literal {3, 5, 4}.
• @oulenz: se você não ‘ se importar com a ordem sem sentido e variando ao longo do tempo, então cada conjunto é ordenado, porque haverá algum tipo de ordem de iteração. Mas ” conjunto ordenado ” implica que a ordem é semântica para os elementos, e isso nem sempre é possível. Eu não ‘ não entendo realmente por que você deseja que todos os conjuntos sejam ordenados.
• ” Conjunto ordenado ” não implica que a ordenação seja semântica, apenas que existe alguma ordenação. É claro que me importo que, uma vez que essa ordem seja estabelecida, ela seja preservada, a menos que seu conteúdo seja modificado.
• Desculpe, eu não estava ‘ ciente de que existia implicação para algumas pessoas. Eu simplesmente tinha em mente um conjunto linearmente ordenado da matemática. en.wikipedia.org/wiki/Total_order
• @jameslarge a relação de pedido não ‘ t tem que ser desconhecido para mim. Se derivar um conjunto ordenado de uma lista, sei exatamente qual é a sua ordem. Se eu quiser garantir uma certa ordem, posso classificar o conjunto. Mas se você não ‘ não precisa do pedido, pode simplesmente ignorá-lo.