Используя Lisp (или AutoLisp), насколько хороша производительность ассоциативных списков?
https://stackoverflow.com/questions/262628
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я делаю проект AutoLisp, который использует длинные ассоциативные структуры для выполнения сложной геометрической обработки - поэтому мне любопытно, что результаты синхронизации интенсивного использования ассоциативного списка. Насколько проста / сложна реализация? Использует некоторую структуру данных или обычный список пунктирных пар? Есть какое-нибудь расширение для b-дерева или чего-то еще?
Решение
В списках ассоциаций Common Lisp и Emacs Lisp это связанные списки, поэтому они имеют линейное время поиска. Предполагая, что AutoLisp одинаков (а если нет, то использование термина «Ассоциативный список» вводит в заблуждение), можно предположить, что все операции будут линейными по длине списка. Например, для alist с 100 элементами в среднем потребуется 50 обращений, чтобы найти то, что вам нужно.
Другие советы
поворотный момент для SBCL на новейшем оборудовании x86 между списками и хэш-таблицами на основе идентификаторов, при условии равномерного распределения доступа, составляет около 30-40 элементов.
Конечно, большинство реализаций Scheme (или, может быть, в спецификациях?) имеют хеш-таблицы, которые используют в основном один и тот же API; но это непрозрачно, когда вы запрашиваете alist, вы получаете список пар, если вам нужна хеш-таблица, попросите ее.
Тем не менее, важно помнить, что линейные алгоритмы не медленные; они «не масштабируются». для небольшого числа элементов они превзойдут более сложный «умный» алгоритм. насколько большое «n» должно быть, во многом зависит от алгоритма, и быстрые процессоры с большими кэшами, но с медленной оперативной памятью, продолжают настаивать. Кроме того, тяжелые оптимизирующие компиляторы (например, доступные на некоторых Лиспах) генерируют очень жесткий линейный код.
Я не работал с AutoLisp около 10 лет, но я никогда не обнаруживал реальных проблем с производительностью при манипулировании списком ассоциаций. И я написал код, который мог бы изрядно манипулировать списком ассоциаций.
Работа в VBA или ObjectARX может иметь некоторые преимущества в производительности, но вам, вероятно, потребуется выполнить некоторое сравнительное тестирование, чтобы убедиться, что оно действительно лучше.
Я не знаю расширения для b-дерева, но если вы используете Visual LISP, вы можете использовать объекты ActiveX и, таким образом, получать доступ к большинству типов баз данных.
