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

Question

Я делаю проект AutoLisp, который использует длинные ассоциативные структуры для выполнения тяжелой геометрической обработки - поэтому мне любопытно узнать результаты интенсивного использования ассоциативного списка. Насколько проста / сложна реализация? Использует некоторую структуру данных или обычный список пунктирных пар? Есть какое-нибудь расширение для b-дерева или что-то?

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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