Структуры данных

2. Словари (Dictionaries)

• Определение: Словари в Python – это неупорядоченные коллекции элементов, где каждый элемент состоит из пары "ключ-значение".

• Представление: Словари создаются с помощью фигурных скобок {}, а пары "ключ-значение" разделяются двоеточием :.

  my_dict = {"name": "John", "age": 30, "city": "New York"}

• Особенности:

  • Ключи должны быть уникальными и неизменяемыми (обычно строки или числа), а значения могут быть любого типа.

  • Доступ к значениям осуществляется по ключу.

  • Изменяемые (mutable).

  • Неупорядоченные (порядок может не сохранятся)

• Примеры:

3. Кортежи (Tuples)

• Определение: Кортежи в Python – это упорядоченные, неизменяемые коллекции элементов.

• Представление: Кортежи создаются с помощью круглых скобок (), а элементы разделяются запятыми.

  my_tuple = (1, 2, 3, "apple", "banana", True)

• Особенности:

  • Аналогичны спискам, но являются неизменяемыми (immutable), то есть нельзя изменить элементы после создания кортежа.

  • Могут содержать элементы разных типов данных.

  • Поддерживают индексацию.

  • Используются для представления неизменяемых последовательностей.

• Примеры:

  # Создание кортежа my_tuple = (1, 2, 3, "apple", "banana") print(f"Создание кортежа: {my_tuple}") # Доступ по индексу print(f"Элемент по индексу 2: {my_tuple[2]}") # Нельзя изменить элемент # my_tuple[0] = 0 # Это вызовет ошибку: TypeError: 'tuple' object does not support item assignment # Нельзя добавить элемент # my_tuple.append(4) # Это вызовет ошибку: AttributeError: 'tuple' object has no attribute 'append' # Нельзя удалить элемент # del my_tuple[0] # Это вызовет ошибку: TypeError: 'tuple' object doesn't support item deletion

4. SimpleNamespace

• Определение: SimpleNamespace из модуля types - это простой класс, позволяющий создавать объекты, у которых атрибуты (свойства) можно задавать как при создании, так и потом.

• Представление: Для создания объекта SimpleNamespace нужно импортировать его из types и передать в него именованные аргументы (или не передать их):

  from types import SimpleNamespace my_namespace = SimpleNamespace(name="John", age=30, city="New York")

• Особенности:

  • Позволяет создавать объекты с динамическими атрибутами (похоже на словарь).

  • Удобен для создания простых объектов для хранения данных.

  • Атрибуты доступны через точку, как у обычных объектов: my_namespace.name

  • В отличие от словарей, порядок атрибутов сохраняется.

  • Поля можно менять, но нельзя добавлять новые поля

• Примеры:

  from types import SimpleNamespace # Создание SimpleNamespace my_namespace = SimpleNamespace(name="John", age=30, city="New York") print(f"Создание SimpleNamespace: {my_namespace}") # Доступ к атрибуту print(f"Атрибут 'name': {my_namespace.name}") # Изменение атрибута my_namespace.age = 31 print(f"Изменение атрибута: {my_namespace}") # Нельзя добавить новый атрибут # my_namespace.occupation = "engineer" # Это вызовет ошибку: AttributeError: 'SimpleNamespace' object has no attribute 'occupation' # Нельзя удалить атрибут # del my_namespace.age # Это вызовет ошибку: AttributeError: age # Добавление через setattr setattr(my_namespace, "occupation", "engineer") print(f"Добавление атрибута: {my_namespace}") # Удаление через delattr delattr(my_namespace, "city") print(f"Удаление атрибута: {my_namespace}")

5. Другие структуры данных в Python:

• Множества (Sets):

  • Неупорядоченные коллекции уникальных элементов.

  • Представление: {1, 2, 3, "apple"}

  • Изменяемые.

• Строки (Strings):

  • Последовательность символов.

  • Представление: "hello", 'world'

  • Неизменяемые (immutable).

  • Поддерживают индексацию и многие другие операции.

• Байтовые массивы (Bytearrays):

  • Изменяемая последовательность байтов.

  • Представление: bytearray(b"hello")

  • Используются для работы с двоичными данными.

• Диапазоны (Ranges):

  • Последовательность целых чисел.

  • Представление: range(10), range(1, 10, 2)

  • Неизменяемые.

  • Используются для генерации последовательностей.

• Frozen sets (неизменяемые множества)

  • Неизменяемая версия множеств (sets).

  • Представление frozenset([1, 2, 3])

Источник картинки [https://rozetked.me/articles/1336-yandeks-kotiki-i-schenochk...]

Сегодня я хочу рассказать вам о структурах данных: что это, зачем нужны и почему это одна из самых важных составляющих программирования. Также в этой статье рассмотрим три простые структуры — стек(stack), очередь(queue) и связной список(linked list).

Как я уже говорил ранее, программирование — это правильная манипуляция данными. Даже если вы не делаете вычислений, а пишите логику кнопки или верстаете сайт — вы все равно манипулируете данными. И вам просто необходимо знать, как правильно управлять и организовывать данный, что бы ваши программы работали должным образом.

Что дает знание структур данных?

1) Ваши программы оптимизированы и затрачивают только необходимое количество ресурсов. Многие алгоритмы зависят от правильно подобранных структур данных.(правильно подобранные структуры данных — это только один из методов оптимизации).

2) Вы понимаете, как работает ваш код (или код другого человека)

3) Вы пишете более понятный код, где все разложено по своим местам. В таком коде другому программисту (или вам сами) будет проще ориентироваться.

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

Стек

Стек — это одна из простейших структур. Данные в ней хранятся по принципу FILO - первый зашел, последний вышел. Представим, что ваши данные — это кирпичи. Сначала вы положили один кирпич в стек, на него вы кладете второй (используя стек, вы всегда кладете данные сверху на предыдущие). Теперь, что бы достать первый кирпич, нам нужно для начала снять с него второй. То есть, когда мы захотим доставать данные из стека, нам прийдется начинать с того кирпича (тех данных), который лежит на самом верху.

Где применяется эта хрень? Представьте себе, что вы работаете в программе Microsoft Word (для тех, кто не работал, представьте программу Photoshop) [если не работали и там и там, представьте себе любую программу, в которой нажатия клавиш Ctrl + Z отменяет последнее действие]. Так вот, когда вы совершаете какое-либо действие в программе, она закидывает совершенное действие в стек. Самый верхний кирпич стека — это состояние вашего документа\фотографии\чего-либо другого на текущий момент. Когда вы хотите отменить последнее изменение (вернуться на одно действие назад), программа берет самый верхний кирпич(последнее действие) со стека, выбрасывает его и кирпич, который был под ним — теперь самый верхний (теперь он становится текущим состоянием). Сам по себе стек очень прикольная структура данных (хотя иногда ее лучше заменить чем-то другим).

Сложность базовых операций в стеке:

Добавить элемент в стек O(1)

Удалить элемент со стека O(1)

Проверить, пуст ли стек O(1)

Как мы знаем из предыдущей статьи, меньшей сложности, чем O(1), пока не существует, что делает стек очень быстрой и малозатратной(по памяти) структурой данных.

Очередь

Очередь — структура, очень похожая на стек, но работает немного по другому — по принципу FIFO - первый пришел, первый вышел. То есть очередь работает так же, как и очередь в реальной жизни — люди стают один за другим (тот, кто раньше всех пришел, стоит самый первый). Самые первые данные, которые мы положили, мы и возьмем самыми первыми.

Пример применения очереди приведу из собственной жизни — однажды мне нужно было написать функцию, которая бы разделила предложение на слова. Каждое слово я представлял в виде очереди, и, начиная с первого символа строки, шел по ней, запихивая каждый символ в очередь, пока не натыкался на знак пробела. Из-за того, что я клал один символ в очередь, каждый следующий символ подвигал предыдущий. То есть, начиная с первой буквы слова, я знал, что буквы не перепутаются в структуре и будут в таком же порядке, как они написаны в предложении.

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

Сложность базовых операций:

Добавить элемент O(1)

Удалить элемент O(1)

Связной список

Связной список

Последняя структура данных на сегодня — связной список. Эта штука мало чем отличается от стандартного массива (просто набор данных, которые доступны по индексу). Главная особенность связного списка это то, что каждая ячейка данных в списке имеет связь со следующей ячейкой (таким образом, только ячейка знает, где находиться ее сосед, идущий после нее). С помощью такой структуры данные могут быть физически разбросаны по оперативной памяти, но логически составлять одну структуру данных. Через связной список можно реализовать много других структур. Сама ячейка содержит в себе данные и указатель на соседа.

Сложность базовых операций:

Добавить элемент O(1)

Удалить элемент O(1)

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

[Еще скоро будет перевод статьи про Arch Linux и его установке рядом с Windows 10]

Доступ к элементам осуществляется по его ключу. Основные операции, которые могут выполняться с хеш-таблицей?

- Insert — добавить новый элемент в хеш-таблицу

- Delete — удалить элемент из хеш-таблицы по ключу

- Search — получить значение по ключу

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

Теперь приступим к реализации данной структуры данных. Для простоты будем рассматривать структуру из пары двух строк. Данная реализация является весьма примитивной, но позволяет разобраться в структуре и алгоритме работы данного типа данных.

Класс элемента данных хеш-таблицы

Класс хеш-таблицы

Работа с хеш-таблицей

Результат работы приложения

На платформе .NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System.Collections и называется аналогично Hashtable. Я не претендую на правильность, оптимальность и красоту реализации. Единственная цель, которую я преследую, поделиться полезной информацией о программировании, которая может кому-то пригодиться.

Источник: https://shwan.ru/hashtable/