Список ассоциаций
| Список ассоциаций | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Тип | ассоциативный массив | |||||||||||||||||||||||
| ||||||||||||||||||||||||
В компьютерном программировании и особенно в Lisp список ассоциаций , часто называемый списком , представляет собой связанный список , в котором каждый элемент списка (или узел ) содержит ключ и значение . Говорят, что список ассоциаций связывает значение с ключом. Чтобы найти значение, связанное с данным ключом, используется последовательный поиск : поиск каждого элемента списка осуществляется по очереди, начиная с головы, до тех пор, пока ключ не будет найден. Ассоциативные списки предоставляют простой способ реализации ассоциативного массива , но эффективны только тогда, когда количество ключей очень мало.
Операция
[ редактировать ]Ассоциативный массив — это абстрактный тип данных , который можно использовать для хранения коллекции пар ключ-значение и поиска значения, связанного с данным ключом. Список ассоциаций обеспечивает простой способ реализации этого типа данных.
Чтобы проверить, связан ли ключ со значением в данном списке ассоциаций, выполните поиск в списке, начиная с его первого узла и продолжая либо до тех пор, пока не будет найден узел, содержащий ключ, либо пока поиск не достигнет конца списка (в этом случае ключа нет).Чтобы добавить новую пару ключ-значение в список ассоциаций, создайте новый узел для этой пары ключ-значение, установите ссылку узла в качестве предыдущего первого элемента списка ассоциаций и замените первый элемент списка ассоциаций на новый узел. [1] Хотя некоторые реализации списков ассоциаций запрещают наличие нескольких узлов с одинаковыми ключами, такое дублирование не является проблемой для этого алгоритма поиска: повторяющиеся ключи, которые появляются позже в списке, игнорируются. [2]
Также возможно удалить ключ из списка ассоциаций, просканировав список, чтобы найти каждое вхождение ключа, и объединить узлы, содержащие ключ, из списка. [1] Сканирование должно продолжаться до конца списка, даже если ключ найден, если один и тот же ключ мог быть вставлен несколько раз.
Производительность
[ редактировать ]Недостатком списков ассоциаций является то, что время поиска составляет O ( n ) , где n — длина списка. [3] Для больших списков это может быть намного медленнее, чем время, которое можно получить, представляя ассоциативный массив в виде двоичного дерева поиска или в виде хеш-таблицы .Кроме того, если список не будет регулярно сокращаться для удаления элементов с повторяющимися ключами, несколько значений, связанных с одним и тем же ключом, будут увеличивать размер списка и, следовательно, время поиска, не предоставляя никаких компенсирующих преимуществ.
Одним из преимуществ списков ассоциаций является то, что новый элемент может быть добавлен за постоянное время. Кроме того, когда количество ключей очень мало, поиск по списку ассоциаций может быть более эффективным, чем поиск по двоичному дереву поиска или хэш-таблице, из-за большей простоты их реализации. [4]
Приложения и библиотеки программного обеспечения
[ редактировать ]На ранних этапах разработки Lisp списки ассоциаций использовались для разрешения ссылок на свободные переменные в процедурах. [5] [6] В этом приложении удобно дополнять списки ассоциаций дополнительной операцией, которая отменяет добавление пары ключ-значение без сканирования списка на наличие других копий того же ключа. Таким образом, список ассоциаций может функционировать как стек , позволяя локальным переменным временно скрывать другие переменные с такими же именами, не разрушая значения этих других переменных. [7]
Многие языки программирования, в том числеЛисп, [5] Схема , [8] ОКамл , [9] и Хаскелл [10] имеют функции для обработки списков ассоциаций в своих стандартных библиотеках .
См. также
[ редактировать ]- Самоорганизующийся список — стратегия изменения порядка ключей в списке ассоциаций для ускорения поиска часто используемых ключей.
- Список свойств или plist, другая структура данных ассоциативного массива, используемая в Lisp. [11] (не путать со списками свойств , форматом файлов, также называемым файлами plist).
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Марриотт, Ким; Стаки, Питер Дж. (1998). Программирование с ограничениями: Введение . МТИ Пресс. стр. 193–195. ISBN 9780262133418 .
- ^ Фрике, Мартин (2012). «2.8.3 Списки ассоциаций» . Логика и организация информации . Спрингер. стр. 44–45. ISBN 9781461430872 .
- ^ Кнут, Дональд . «6.1 Последовательный поиск». Искусство компьютерного программирования , Vol. 3: Сортировка и поиск (2-е изд.). Эддисон Уэсли. стр. 396–405. ISBN 0-201-89685-0 .
- ^ Джейнс, Кэлвин (2011). «Использование списков ассоциаций для ассоциативных массивов» . Руководство разработчика по коллекциям в Microsoft .NET . Пирсон Образование. п. 191. ИСБН 9780735665279 .
- ^ Jump up to: Перейти обратно: а б Маккарти, Джон; Абрахамс, Пол В.; Эдвардс, Дэниел Дж.; Харт, Тимоти П.; Левин, Майкл И. (1985). Руководство программиста LISP 1.5 . МТИ Пресс . ISBN 0-262-13011-4 . См., в частности, стр. 12 для функций, которые ищут список ассоциаций и используют его для замены символов в другом выражении, и стр. 103 для применения списков ассоциаций при поддержании привязок переменных.
- ^ ван де Снепшеут, Ян Л.А. (1993). Что такое вычислительная техника . Монографии по информатике. Спрингер. п. 201. ИСБН 9781461227106 .
- ^ Скотт, Майкл Ли (2000). «3.3.4 Списки ассоциаций и центральные справочные таблицы» . Прагматика языков программирования . Морган Кауфманн. п. 137. ИСБН 9781558604421 .
- ^ Пирс, Джон (2012). Программирование и метапрограммирование в Scheme . Тексты для бакалавриата по информатике. Спрингер. п. 214. ИСБН 9781461216827 .
- ^ Мински, Ярон; Мадхавапедди, Анил; Хикки, Джейсон (2013). Реальный мир OCaml: функциональное программирование для масс . О'Рейли Медиа. п. 253. ИСБН 9781449324766 .
- ^ О'Салливан, Брайан; Герцен, Джон; Стюарт, Дональд Брюс (2008). Реальный мир Haskell: код, в который можно поверить . О'Рейли Медиа. п. 299. ИСБН 9780596554309 .
- ^ «10.1. Список свойств» . Cs.cmu.edu . Проверено 29 сентября 2017 г.