В чем разница между тем, как словарные и списочные структуры данных появляются в памяти?

1

Например, если бы я должен был создать следующий код:

a_list = ['this', 'is', 'a', 'sentence']
a_dict = { 0: 'this', 1 : 'is', 2 : 'a', 3 : 'sentence'}

затем введите командную строку

>a_list[0]

дает

>'this'

как и

>a_dict[0]

Выход

>'this'

Есть ли что-то неправильное, говоря, что список - это тип словаря, если он используется строго так, чтобы клавиши были целыми числами, начинающимися с 0? Функционально они кажутся мне одинаковыми на этом уровне абстракции, так что в чем разница в пространстве, что - я предполагаю, что функционально эквивалентные структуры занимают память и скорость, с которой мы можем получить доступ к значениям в python? Словарь представляет собой математическую карту, а карта, которая отображает положительные целые числа в значения, математически эквивалентна списку. Я ошибаюсь, говоря, что с учетом вышеуказанных ограничений они функционально одинаковы на этом уровне абстракции. Итак, какова практическая или вычислительная разница в python?

  • 0
    Вы читали docs.python.org/library/… и docs.python.org/library/stdtypes.html#mapping-types-dict ? Эти два раздела, кажется, охватывают все различия между этими типами. Возможно, вы могли бы обновить свой вопрос конкретными словами или фразами, которые вас смутили.
  • 0
    Спасибо, я обязательно посмотрю.
Теги:

4 ответа

3
Лучший ответ

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

Списки Python можно рассматривать как простые динамические массивы (похожие на С++ std::vector). С другой стороны, dicts реализуются как хэш-таблицы (std::unordered_map в предстоящем стандарте С++ 0x).

Почему бы не всегда использовать dicts вместо списков? Потому что для многих списков операций правильная структура данных для задания - быстрее и меньше, чем dicts. Например, если вам нужен только линейный список элементов, вы должны использовать список, а не dict - список будет потреблять меньше места, он будет быстрее в доступе к индексу и сохранит порядок вставки. Да, если вы не заботитесь о производительности и о порядке, вы, вероятно, можете жить с dicts вместо списков.

P.S. На некоторых языках (Lua IIRC) массивы реализуются в терминах хэш-таблиц с числовыми ключами, поэтому эквивалентность, которую вы пытаетесь определить, существует.

Поделиться
  • 0
    +1. Я думаю, что PHP использует ассоциативные массивы, так как имеет таблицы и массивы.
  • 0
    сравнение с std::unordered_map новое! Благодарю.
1

Список.

Словарь.

Попробуйте не путать их.

Поделиться
0

Что не так, говоря, что список является типом словаря, в котором ключи - это целые числа, начинающиеся с 0?

Потому что это фактически неверно. Словарь может иметь такие ключи, как 0,2,4,6,8,10. Список не может. В списке нет ключей. Он имеет индексы к элементам.

Функционально они должны быть одинаковыми,

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

так в чем разница в пространстве что эквивалентные им структуры в памяти, и скорость, с которой мы можем получить доступ к значениям в python

Объекты совершенно разные. Код, который фактически выполняется внутри интерпретатора при доступе или использовании этих типов, полностью отличается. Они предназначены для разных целей.

Итак, что такое практическое или вычислительная разница в python?

Вы должны прочитать информацию о структурах данных. Массивы и хеш-таблицы имеют разные применения и приложения. Списки Python и словари являются реализациями этих структур и используются для разных целей. Персонажи производительности, абстрактные типы данных и приложения совершенно разные.

Поделиться
  • 0
    Ваш пример 0,2,4,6,8,10 не совсем точен. Разреженные списки часто используются для доступа O (1), если диапазон ключей известен и ограничен.
  • 0
    Это похоже на список, реализованный с использованием хеш-таблицы, не так ли?
Показать ещё 7 комментариев
0

Когда вы ищете сопоставления производительности, в реализации CPython они близки, когда дело доходит до определенных операций, таких как Get item и Set item и т.д. Посмотрите эту страницу, объясняя детали временной сложности.

Но вы должны помнить, что список - это список и dict dict. Вы не можете сортировать dict, это не имеет никакого смысла, и вы можете сделать это в списке. Вы вставляете элемент в список, но для установки пары ключ, значение в dict. Это разные операции.

Поделиться

Ещё вопросы

Сообщество Overcoder
Наверх
Меню