Usando Lisp (ou AutoLisp) quão bom é o associativa desempenho listas?
https://stackoverflow.com/questions/262628
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou fazendo um projeto AutoLisp que usa longas estruturas associativas para fazer o processamento geométrico pesado - por isso estou curioso sobre a lista associativa uso intenso resultados de cronometragem. Como simples / complexa é a implementação? Ele usa alguma estrutura de dados ou uma lista normal dos pares espalhados? O são qualquer extensão de b-tree ou algo assim?
Solução
listas de associação em Common Lisp e Emacs Lisp são listas ligadas, para que eles tenham tempo de pesquisa linear. Assumindo que AutoLisp é o mesmo (e se não for, então o seu uso do termo "Lista Associativa" é enganosa), você pode assumir que todas as operações será linear no comprimento da lista. Por exemplo, um alist com 100 elementos vão, em média, precisa de 50 acessos de encontrar a coisa que você está depois.
Outras dicas
O ponto de viragem para SBCL em hardware x86 recente entre alists e hashtables de identidade com base, assumindo distribuição uniforme de acesso, é de cerca de 30-40 elementos.
É claro, a maioria das implementações Scheme (ou talvez seja nas especificações?) Tem hashtables, que utilizam principalmente o mesmo API; mas não é transparente, quando você pedir uma alist, você tem uma lista de pares, se você quiser um hashtable, pergunte para ele.
que disse, é importante lembrar que os algoritmos lineares não são lentos; eles são 'unscalable'. para um pequeno número de elementos, eles vão superar um algoritmo mais complexo 'inteligente'. quão grande 'n' tem que ser, depende muito do algoritmo, e processadores rápidos com grandes caches, mas RAM lenta, manter empurrando-o. Além disso, os compiladores de otimização pesados ??(como aqueles disponíveis em algum Lisp de) geram muito código linear apertado.
Eu não tenho trabalhado com AutoLisp em cerca de 10 anos, mas eu nunca encontrou quaisquer problemas de desempenho real, com lista de associação de manipulação. E eu escrevi o código que faria uma boa quantidade de lista associação manipulação.
Trabalho em VBA ou ObjectARX pode ter alguns benefícios de desempenho, mas você provavelmente precisa executar alguma comparação testando para ver se ele é realmente melhor.
Não há extensão para b-tree, que eu saiba, mas se você usar Visual LISP você pode usar objetos ActiveX e, assim, acessar a maioria dos tipos de bases de dados.
