Por que [] é mais rápido que list ()?

I recentemente comparou as velocidades de processamento de []e list()e ficou surpreso ao descobrir que []corre mais de três vezes mais rápido do que list(). Corri o mesmo teste com {}e dict(), e os resultados foram praticamente idênticos: []e {}tanto levou cerca 0.128sec / milhão de ciclos, enquanto que list()e dict()levou cerca de 0.428sec / milhão de ciclos cada.

Por que é isso? Fazer []e {}(e, provavelmente, ()e '', também) imediatamente passar para trás cópias de alguns literal estoque vazio enquanto os seus homólogos explicitamente nomeados ( list(), dict(), tuple(), str()) ir totalmente sobre a criação de um objeto, ou não eles realmente têm elementos?

Não tenho idéia de como esses dois métodos diferem, mas eu adoraria descobrir. Não consegui encontrar uma resposta nos documentos ou no SO, e procurar colchetes vazios acabou sendo mais problemático do que eu esperava.

Obtive meus resultados de tempo ligando timeit.timeit("[]")e timeit.timeit("list()"), e timeit.timeit("{}")e timeit.timeit("dict()"), para comparar listas e dicionários, respectivamente. Estou executando o Python 2.7.9.

Eu descobri recentemente " Porque é que se True mais lento do que se 1? ", Que compara o desempenho de if Truepara if 1e parece tocar em um semelhante literal versus global de cenário; talvez valha a pena considerar também.

Porque []e {}são sintaxe literal . O Python pode criar bytecode apenas para criar os objetos de lista ou dicionário:

>>> import dis
>>> dis.dis(compile('[]', '', 'eval'))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile('{}', '', 'eval'))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE        

list()e dict()são objetos separados. Seus nomes precisam ser resolvidos, a pilha precisa estar envolvida para enviar os argumentos, o quadro precisa ser armazenado para recuperar mais tarde e uma chamada deve ser feita. Tudo isso leva mais tempo.

Para o caso vazio, isso significa que você tem pelo menos um LOAD_NAME(que precisa pesquisar no espaço de nomes global e no __builtin__módulo ) seguido de um CALL_FUNCTION, que deve preservar o quadro atual:

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile('dict()', '', 'eval'))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        

Você pode cronometrar a pesquisa de nome separadamente com timeit:

>>> import timeit
>>> timeit.timeit('list', number=10**7)
0.30749011039733887
>>> timeit.timeit('dict', number=10**7)
0.4215109348297119

A discrepância de tempo provavelmente existe uma colisão de hash do dicionário. Subtraia esses horários dos horários para chamar esses objetos e compare o resultado com os horários para o uso de literais:

>>> timeit.timeit('[]', number=10**7)
0.30478692054748535
>>> timeit.timeit('{}', number=10**7)
0.31482696533203125
>>> timeit.timeit('list()', number=10**7)
0.9991960525512695
>>> timeit.timeit('dict()', number=10**7)
1.0200958251953125

Portanto, ter que chamar o objeto leva um 1.00 - 0.31 - 0.30 == 0.39segundo adicional a cada 10 milhões de chamadas.

Você pode evitar o custo da pesquisa global usando o alias dos nomes globais como locais (usando uma timeitconfiguração, tudo que você vincula a um nome é local):

>>> timeit.timeit('_list', '_list = list', number=10**7)
0.1866450309753418
>>> timeit.timeit('_dict', '_dict = dict', number=10**7)
0.19016098976135254
>>> timeit.timeit('_list()', '_list = list', number=10**7)
0.841480016708374
>>> timeit.timeit('_dict()', '_dict = dict', number=10**7)
0.7233691215515137

mas você nunca pode superar esse CALL_FUNCTIONcusto.

list()requer uma pesquisa global e uma chamada de função, mas é []compilada em uma única instrução. Vejo:

Python 2.7.3
>>> import dis
>>> print dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
None
>>> print dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
None

Porque listé uma função para converter digamos uma string em um objeto de lista, enquanto []é usada para criar uma lista fora do bastão. Tente isto (pode fazer mais sentido para você):

x = "wham bam"
a = list(x)
>>> a
["w", "h", "a", "m", ...]

Enquanto

y = ["wham bam"]
>>> y
["wham bam"]

Fornece uma lista real com o que você coloca nela.

As respostas aqui são ótimas, objetivas e cobrem totalmente essa questão. Vou dar um passo adiante no código de bytes para os interessados. Estou usando o repo mais recente do CPython; versões mais antigas se comportam de maneira semelhante a esse respeito, mas pequenas alterações podem estar em vigor.

Aqui está um detalhamento da execução de cada um deles, BUILD_LISTpara []e CALL_FUNCTIONpara list().

A BUILD_LISTinstrução:

Você deve apenas ver o horror:

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

Terrivelmente complicado, eu sei. É assim que é simples:

• Crie uma nova lista com PyList_New(isso aloca principalmente a memória para um novo objeto de lista),oparg sinalizando o número de argumentos na pilha. Direto ao ponto.
• Verifique se nada deu errado if (list==NULL).
• Adicione quaisquer argumentos (no nosso caso, isso não é executado) localizados na pilha com PyList_SET_ITEM(uma macro).

Não é à toa que é rápido! É feito sob medida para criar novas listas, nada mais :-)

A CALL_FUNCTIONinstrução:

Aqui está a primeira coisa que você vê quando espreita a manipulação de código CALL_FUNCTION:

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

Parece bastante inofensivo, certo? Bem, infelizmente não, não call_functioné um cara direto que chamará a função imediatamente, não pode. Em vez disso, ele pega o objeto da pilha, pega todos os argumentos da pilha e depois alterna com base no tipo do objeto; é um:

• PyCFunction_Type? Não, é list, listnão é do tipoPyCFunction
• PyMethodType? Não, veja anterior.
• PyFunctionType? Nopee, veja anterior.

Estamos chamando o listtipo, o argumento passado para call_functioné PyList_Type. Agora, o CPython precisa chamar uma função genérica para manipular qualquer objeto que possa ser chamado _PyObject_FastCallKeywords, com mais chamadas de função.

Essa função novamente verifica alguns tipos de função (que não consigo entender por que) e, depois de criar um dict para kwargs, se necessário , continua a chamar _PyObject_FastCallDict.

_PyObject_FastCallDictfinalmente nos leva a algum lugar! Depois de realizar ainda mais verificações que agarra a tp_callfenda dotype do typeque já passou em, ou seja, ele pega type.tp_call. Em seguida, ele cria uma tupla dos argumentos transmitidos _PyStack_AsTuplee, finalmente, uma chamada pode finalmente ser feita !

tp_call, que corresponde ao type.__call__controle e finalmente cria o objeto de lista. Ele chama as listas __new__que correspondem PyType_GenericNewe alocam memória para ele com PyType_GenericAlloc: Esta é realmente a parte em que ele alcança PyList_New, finalmente . Todas as anteriores são necessárias para manipular objetos de maneira genérica.

No final, type_callchama list.__init__e inicializa a lista com todos os argumentos disponíveis e, em seguida, retornamos do jeito que viemos. :-)

Finalmente, lembre-se de LOAD_NAMEque é outro cara que contribui aqui.

É fácil ver que, ao lidar com nossa entrada, o Python geralmente precisa passar por obstáculos para realmente descobrir a Cfunção apropriada para fazer o trabalho. Não tem a cortesia de chamá-lo imediatamente, porque é dinâmico, alguém pode mascarar list( e o garoto faz muitas pessoas ) e outro caminho deve ser tomado.

É aqui que list()perde muito: o Python explorador precisa fazer para descobrir o que diabos ele deve fazer.

A sintaxe literal, por outro lado, significa exatamente uma coisa; não pode ser alterado e sempre se comporta de maneira pré-determinada.

^{Nota de rodapé: Todos os nomes de funções estão sujeitos a alterações de uma versão para outra. O ponto ainda permanece e provavelmente continuará em qualquer versão futura; é a pesquisa dinâmica que atrasa as coisas.}

Por que é []mais rápido que list()?

O maior motivo é que o Python trata list()exatamente como uma função definida pelo usuário, o que significa que você pode interceptá-lo alterando o nome de outra coisa liste fazer algo diferente (como usar sua própria lista subclassificada ou talvez um deque).

Ele cria imediatamente uma nova instância de uma lista interna com [] .

Minha explicação procura dar-lhe a intuição para isso.

Explicação

[] é comumente conhecido como sintaxe literal.

Na gramática, isso é chamado de "exibição de lista". Dos documentos :

Uma exibição de lista é uma série possivelmente vazia de expressões entre colchetes:

list_display ::=  "[" [starred_list | comprehension] "]"

Uma exibição de lista gera um novo objeto de lista, sendo o conteúdo especificado por uma lista de expressões ou uma compreensão. Quando uma lista de expressões separada por vírgula é fornecida, seus elementos são avaliados da esquerda para a direita e colocados no objeto de lista nessa ordem. Quando uma compreensão é fornecida, a lista é construída a partir dos elementos resultantes da compreensão.

Em resumo, isso significa que um objeto interno do tipo list é criado.

Não há como contornar isso - o que significa que o Python pode fazê-lo o mais rápido possível.

Por outro lado, list()pode ser interceptado a partir da criação de um built-in listusando o construtor da lista de built-in.

Por exemplo, digamos que queremos que nossas listas sejam criadas ruidosamente:

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print('List initialized.')

Poderíamos então interceptar o nome listno escopo global no nível do módulo e, quando criamos um list, criamos nossa lista de subtipos:

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class '__main__.List'>

Da mesma forma, poderíamos removê-lo do espaço para nome global

del list

e coloque-o no espaço para nome interno:

import builtins
builtins.list = List

E agora:

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class '__main__.List'>

E observe que a exibição da lista cria uma lista incondicionalmente:

>>> list_1 = []
>>> type(list_1)
<class 'list'>

Provavelmente, apenas fazemos isso temporariamente, então vamos desfazer nossas alterações - primeiro remova o novo Listobjeto dos componentes internos:

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module 'builtins' has no attribute 'list'
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'list' is not defined

Ah, não, perdemos a noção do original.

Não se preocupe, ainda podemos obter list- é o tipo de uma lista literal:

>>> builtins.list = type([])
>>> list()
[]

Assim...

Por que é []mais rápido que list()?

Como vimos - podemos sobrescrever list- mas não podemos interceptar a criação do tipo literal. Quando usamos list, temos que fazer as pesquisas para ver se há algo lá.

Então, temos que ligar para qualquer coisa que possamos chamar. Da gramática:

Uma chamada chama um objeto que pode ser chamado (por exemplo, uma função) com uma série de argumentos possivelmente vazia:

call                 ::=  primary "(" [argument_list [","] | comprehension] ")"

Podemos ver que ele faz a mesma coisa com qualquer nome, não apenas na lista:

>>> import dis
>>> dis.dis('list()')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis('doesnotexist()')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

Pois []não há chamada de função no nível de bytecode do Python:

>>> dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

Ele simplesmente vai direto para a construção da lista sem nenhuma pesquisa ou chamada no nível do bytecode.

Conclusão

Demonstramos que listpode ser interceptado com o código do usuário usando as regras de escopo e quelist() procura um chamador e depois o chama.

Considerando que []é uma exibição de lista, ou literal, e assim evita a pesquisa de nome e a chamada de função.