Мне вот интересно какой момент-сложность поставил-автомобиль! и установить-cdr! есть в схеме? Я бы подумал, что это постоянное время, но я могу ошибаться, так как не знаю, как они работают внутри. Кто-нибудь, у кого есть идея?
Время-сложность поставил-автомобиль! / set-cdr! в схеме
30.03.2015
- Это будет зависеть от реализации, потому что не указано, как они работают внутри. Я ожидаю, как и вы, что в большинстве реализаций это будет постоянное время. 30.03.2015
- Я бы счел замечательным, если бы реализация Scheme каким-то образом реализовала их таким образом, что они были не постоянными. 30.03.2015
- @AlexisKing Существует классическая (образовательная) реализация
consс точки зрения замыканий. Если бы лексические замыкания не были реализованы должным образом, то set-cdr и set-car могли бы работать там медленнее. Конечно, я не ожидаю, что реализация предоставит их как фактическую реализацию, но я мог видеть, что это имеет место в примере реализации. 30.03.2015 - @JoshuaTaylor Это может быть медленнее, но это все равно будет постоянное время, хотя и с большим постоянным коэффициентом. 31.03.2015
- @chris, это все равно будет зависеть от того, как были реализованы лексические среды. Если бы они были реализованы в виде списков ассоциаций, то это могло бы быть довольно медленным. 31.03.2015
Ответы:
1
В любой разумной реализации Scheme, поскольку cons-ячейки настолько распространены, они реализуются как своего рода структура из двойных слов. В таких реализациях car, cdr, set-car! и set-cdr! все являются постоянными.
Как прокомментировала Алексис Кинг, у вас должна быть довольно извращенная реализация, чтобы это не было постоянным временем. (например, если cons-ячейки были реализованы как списки.)
30.03.2015
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально
Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение
Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования
Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv)
Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..