Используя Lisp (или AutoLisp), насколько хороша производительность ассоциативных списков?

В Common Lisp и Emacs Lisp списки ассоциаций являются связанными списками, поэтому они имеют линейное время поиска. Предполагая, что AutoLisp один и тот же (а если это не так, то использование термина «ассоциативный список» вводит в заблуждение), вы можете предположить, что все операции будут линейными по длине списка. Например, список из 100 элементов в среднем потребует 50 обращений, чтобы найти то, что вам нужно.

поворотным моментом для SBCL на новейшем оборудовании x86 между списками и хеш-таблицами на основе идентификации, при условии равномерного распределения доступа, является около 30-40 элементов.

Конечно, большинство реализаций Scheme (или, может быть, это указано в спецификациях?) имеют хеш-таблицы, которые используют в основном один и тот же API; но это не прозрачно, когда вы запрашиваете алист, вы получаете список пар, если вы хотите хеш-таблицу, просите ее.

при этом важно помнить, что линейные алгоритмы не медленные; они «не масштабируются». для небольшого количества элементов они превзойдут более сложный «умный» алгоритм. просто насколько большим должно быть «n», во многом зависит от алгоритма, и быстрые процессоры с большими кэшами, но медленной оперативной памятью продолжают увеличивать его. Кроме того, сложные оптимизирующие компиляторы (такие, как те, что доступны для некоторых Лиспов) генерируют очень плотный линейный код.

Я не работал с AutoLisp около 10 лет, но никогда не сталкивался с реальными проблемами производительности при манипулировании списками ассоциаций. И я написал код, который достаточно много манипулировал списком ассоциаций.

Работа в VBA или ObjectARX может иметь некоторые преимущества в производительности, но вам, вероятно, потребуется провести сравнительное тестирование, чтобы увидеть, действительно ли это лучше.

Я не знаю расширения для b-tree, но если вы используете Visual LISP, вы можете использовать объекты ActiveX и, таким образом, получать доступ к большинству типов баз данных.