В чем недостаток списка как универсального представления данных?

Question

Программисты на Лиспе обычно используют списки для представления всех других типов данных.

Однако я слышал, что списки не являются хорошим универсальным представлением для типов данных.

В чем недостаток списков, используемых таким образом, по сравнению с использованием записей?

Answer 1

Вы упоминаете "запись".Под этим я понимаю, что вы имеете в виду структуры / объекты / составные данные с фиксированными элементами.Например, в синтаксисе HtDP:

;; a packet is (make-packet destination source text) where destination is a number, 
;; source is a number, and text is a string.

... и вы спрашиваете о плюсах и минусах представления пакета в виде списка длины три, а не как части составных данных (или«запись»).

В случаях, когда составные данные являются подходящими - значения имеют определенные роли и имена, и их существует фиксированное число - составные данные обычно предпочтительнее;они помогают вам отлавливать ошибки в ваших программах, что является непременным условием программирования.

Answer 2

Недостаток в том, что он не универсален.Иногда это связано с производительностью: вам нужен постоянный поиск по времени (массив, хэш-таблица).Иногда это связано с организацией: вы хотите назвать свои местоположения данных (хэш-таблица, запись ... хотя вы можете использовать имя, пары значений в списке).Со стороны автора требуется немного усердия, чтобы код самодокументировался (более усердно, чем запись).Иногда вы хотите, чтобы система типов распознавала ошибки, допущенные в неправильном месте (записи, типизированные кортежи).

Однако большинство проблем можно решить с помощью OptimizeLater.Список представляет собой универсальную небольшую структуру данных.

Answer 3

Вы говорите о том, что Питер Сейбел обращается к главе 11 Практического Общего Лисп:

[Начало] обсуждение коллекций Лисп со списками. , , часто приводит читателей к ошибочным вывод, что списки - единственный тип коллекции Lisp. Чтобы иметь значение хуже, потому что списки Lisp являются такой гибкой структурой данных, это можно использовать их для многих вещей массивы и хеш-таблицы используется для других языков. Но ошибочно слишком много внимания уделять списки; в то время как они являются важной структурой данных для представления Lisp кодировать как данные Lisp, во многих ситуациях другие структуры данных более необходимо.

Как только вы ознакомитесь со всеми типами данных, которые предлагает Common Lisp, вы также увидите, что списки могут быть полезны для прототипирования данных структуры, которые впоследствии будут заменены чем-то более эффективным когда станет ясно, как именно будут использоваться данные.

Вот некоторые причины, которые я вижу:

• Например, большая хеш-таблица имеет более быстрый доступ, чем эквивалентный список
• Вектор одного типа данных более компактный и, опять же, более быстрый доступ
• Векторы более эффективно и легко доступны по индексу
• Объекты и структуры позволяют получать доступ к данным по имени, а не по положению

Это сводится к использованию правильного типа данных для поставленной задачи. Когда это не очевидно, у вас есть два варианта: угадать и исправить это позже или выяснить это сейчас; иногда это правильный подход.