Usando Lisp (o AutoLisp) quanto sono buone le prestazioni degli elenchi associativi?
https://stackoverflow.com/questions/262628
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto realizzando un progetto AutoLisp che utilizza lunghe strutture associative per eseguire elaborazioni geometriche pesanti, quindi sono curioso di sapere che l'elenco associativo ha intensi risultati sui tempi di utilizzo. Quanto è semplice / complessa l'implementazione? Utilizza una struttura di dati o un normale elenco di coppie punteggiate? Ci sono delle estensioni per b-tree o qualcosa del genere?
Soluzione
In Common Lisp ed Emacs Gli elenchi di associazioni Lisp sono elenchi collegati, quindi hanno un tempo di ricerca lineare. Supponendo che AutoLisp sia lo stesso (e in caso contrario, il loro uso del termine "Elenco associativo" è fuorviante), si può presumere che tutte le operazioni saranno lineari nella lunghezza dell'elenco. Ad esempio, un elenco di 100 elementi avrà, in media, bisogno di 50 accessi per trovare ciò che stai cercando.
Altri suggerimenti
il punto di svolta per SBCL sul recente hardware x86 tra liste e hashtable basate sull'identità, ipotizzando una distribuzione uniforme dell'accesso, è di circa 30-40 elementi.
Naturalmente, la maggior parte delle implementazioni di Scheme (o forse è nelle specifiche?) hanno hashtable, che usano principalmente la stessa API; ma non è trasparente, quando chiedi una lista, ottieni un elenco di coppie, se vuoi una tabella hash, chiedila.
detto ciò, è importante ricordare che gli algoritmi lineari non sono lenti; sono "non scalabili". per un numero limitato di elementi, supereranno un algoritmo "intelligente" più complesso. quanto deve essere grande 'n', dipende molto dall'algoritmo e processori veloci con grandi cache ma RAM lenta, continuano a spingerlo. Inoltre, compilatori con ottimizzazione pesante (come quelli disponibili su alcuni Lisp) generano un codice lineare stretto molto .
Non lavoro con AutoLisp da circa 10 anni, ma non ho mai riscontrato problemi di prestazioni reali con la manipolazione dell'elenco delle associazioni. E ho scritto un codice che farebbe una buona dose di manipolazione dell'elenco delle associazioni.
Lavorare in VBA o ObjectARX potrebbe avere alcuni vantaggi in termini di prestazioni, ma probabilmente dovresti eseguire alcuni test comparativi per vedere se è davvero meglio.
Non esiste un'estensione per b-tree che io conosca, ma se usi Visual LISP puoi usare oggetti ActiveX e quindi accedere alla maggior parte dei tipi di database.
