Как расширить двумерный массив в python
Я делаю игру с бесконечным миром. У меня есть двумерный массив pos_block[x][y]. Каждая ячейка массива соответствует координате в мире. Так как изначально я не могу создать массив нужного размера я хочу его расширять. Как это сделать? Создаю массив с помощью pos_blocks=[[0 for a in range(-501,501)] for b in range(-801,801)] и хочу его увеличивать.
Отслеживать
задан 22 июл 2020 в 13:50
98 10 10 бронзовых знаков
Лучше используйте массивы Numpy , там такие вещи делаются довольно элементарно. И в целом доступ к элементам будет быстрее.
22 июл 2020 в 14:10
@CrazyElf с numpy уже имел дело, создавая ИИ, но с массивами в них никогда не пытался особо разобраться, кроме как с обычным созданием — изъятием и т.д. А как можно именно в обычном python расширить массив?
22 июл 2020 в 15:39
Если ваш список будет постоянно расширяться, то бесконечным мир точно стать не сможет, как минимум закончится память для этого списка 🙂 Думаю, вам скорее надо хранить фиксированного размера список, но который будет меняться в зависимости от положения игрока. Например, всегда хранить 1000 клеток вокруг игрока
22 июл 2020 в 16:15
@dIm0n Спасибо за идею!) А как тогда можно сделать так, что при возвращении игрока обратно мир был таким, как раньше? Ведь при перезаписывании массива будут теряться данные об этом.
22 июл 2020 в 16:21
@Nezerix хранить как-то отдельно только то, что надо хранить. Если что-то надо сохранять, то в любом случае мир будет конечным
22 июл 2020 в 16:23
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Да так то нет ничего проще, если немного подумать:
pos_blocks=[[0 for a in range(-1,1)] for b in range(-2,2)] print(pos_blocks) # добавляем ещё один список в конец основного списка pos_blocks.append([0]*2) print(pos_blocks) # добавляем по одному элементу в каждый список внутри основного списка for l in pos_blocks: l.append(0) print(pos_blocks) Исходный список списков:
[[0, 0], [0, 0], [0, 0], [0, 0]] После добавления в него нового списка:
[[0, 0], [0, 0], [0, 0], [0, 0], [0, 0]] После добавления элемента в каждый вложенный список:
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]] Реализация динамического массива на Python
Мы продолжаем курс по структурам данных. Пришло время посмотреть, как реализуется динамический массив в языках Python и С++. И начнем с языка Python.
Динамический массив в Python
Всем питонистам известна коллекция типа list, которая позволяет создавать список из разных объектов. Например, так:
marks = [2, 2, 3, 4]
lst = [True, "Истина", 1, 1.0]
Можно ли считать такие списки динамическими массивами? Строго говоря, лишь с некоторым приближением, так как в массивах все элементы должны иметь единый тип данных. А во втором списке мы видим и булево значение и строку и целое число, то есть, разные типы. Но если мы посмотрим внутрь этой структуры, то увидим, что на самом деле списки в Python реализованы как динамические массивы ссылок. И эти ссылки могут быть связаны с любым объектом, любого типа.
Отсюда и получается эффект, словно список содержит разные типы. На самом деле в нем хранятся только ссылки, ведущие на те или иные объекты и не более того. То есть, сам динамический массив содержит данные одного типа – ссылки на объекты.
Число хранимых элементов в списке можно определить командой:
n = len(lst)
Если требуется добавить новый элемент в этот список, то используется команда:
lst.append(5)
В результате в конец списка будет добавлена новая ссылка, связанная с целым значением 5. Скорость этой операции с точки зрения О большого составляет O(1). То есть, добавление нового значения в конец списка – это относительно быстрая операция.
Если же мы хотим вставить новое промежуточное значение, например, в середину или начало списка, то это делается с помощью команды:
lst.insert(0, 'First')
Здесь первое значение – это индекс вставляемого элемента, а второй аргумент – значение вставляемого элемента. В итоге получаем список из шести элементов со скоростью выполнения операции O(n), где n – общее число элементов в списке.
Как видите, скорость выполнения операции вставки элементов в список существенно выше, чем операция добавления последнего элемента. Поэтому вставок лучше избегать при использовании списков.
Далее, для доступа к отдельным элементам списков используется оператор квадратные скобки:
el_1 = marks[2] # чтение значения 3-го элемента marks[1] = 3 # запись значения во 2-й элемент
Так как динамический массив в своей основе использует обычный статический массив, то доступ к произвольному его элементу осуществляется мгновенно (за константное время) O(1).
Я напомню, что имя самого массива хранит адрес первой ячейки. Зная этот начальный адрес и размер одного элемента в байтах:
k – число байт для одного элемента
мы легко можем вычислить адрес любого j-го элемента по формуле:
p = marks + (j-1) ∙ k
Поэтому операции чтения/записи отдельного элемента выполняются за время O(1).
Таким образом, если нам нужен список разумной длины, к элементам которого предполагается частое обращение, то динамический массив (список языка Python) будет хорошим выбором. Также мы вполне можем использовать операции добавления последнего элемента в список, увеличивая общее число элементов. Но операций вставки новых элементов и удаления промежуточных лучше избегать, т.к. они требуют линейного времени выполнения. Вот общие рекомендации по использованию списков языка Python.
Объединение списков и срезы
Довольно часто в Python используется операция объединения списков. Например, мы можем соединить два списка в нашем примере следующим образом:
lj = marks + lst
Что происходит в этот момент, какие действия? И какова вычислительная сложность такой операции с точки зрения О большого?
Начнем с первого вопроса, что происходит в момент объединения двух динамических массивов. Создается новый массив, размером достаточным для хранения всех объединяемых элементов, а затем, в него копируется информация из первого и второго массивов:
Если принять число элементов первого массива за n, а во втором – за m, то вычислительная сложность такой операции с точки зрения О большого составляет:
Другая распространенная операция со списками – это взятие срезов. Давайте предположим, что у нас имеется список:
lst = [1, 2, 3, 4, 5, 6, 7, 8]
и мы берем от него срез:
lst2 = lst[1:6]
Что происходит с динамическим массивом в этом случае? Как мы знаем, срез в списках создает новый список с соответствующим набором элементов. В данном случае список lst2 будет состоять из значений:
lst2 = [2, 3, 4, 5, 6]
То есть, при взятии среза создается новый динамический массив и в него копируются данные из первого массива. Сложность этой операции составляет O(n).
Видео по теме
#1. О большое (Big O) — верхняя оценка сложности алгоритмов
#2. О большое (Big O). Случаи логарифмической и факториальной сложности
#3. Статический массив. Структура, его преимущества и недостатки
#4. Примеры реализации статических массивов на C++
#5. Динамический массив. Принцип работы
#6. Реализация динамического массива на Python
#7. Реализация динамического массива на С++ с помощью std::vector
#8. Односвязный список. Структура и основные операции
#9. Делаем односвязный список на С++
#10. Двусвязный список. Структура и основные операции
#11. Делаем двусвязный список на С++
#12. Двусвязный список (list) в STL на С++
#13. Очереди типов FIFO и LIFO
#14. Очередь collections.deque на Python
#15. Очередь deque библиотеки STL языка C++
#16. Стек. Структура и принцип работы
#17. Реализация стека на Python и C++
#18. Бинарные деревья. Начало
#19. Бинарное дерево. Способы обхода и удаления вершин
#20. Реализация бинарного дерева на Python
#21. Множества (set). Операции над множествами
#22. Множества set и multiset в C++
#23. Контейнер map библиотеки STL в C++
#24. Префиксное (нагруженное, Trie) дерево. Ассоциативные массивы
#25. Хэш-таблицы. Что это такое и как работают
#26. Хэш-функции. Универсальное хэширование
#27. Метод открытой адресации. Двойное хэширование
#28. Использование хэш-таблиц в Python и С++
© 2024 Частичное или полное копирование информации с данного сайта для распространения на других ресурсах, в том числе и бумажных, строго запрещено. Все тексты и изображения являются собственностью сайта
Как можно в Python создать динамический массив где каждый элемент будет объектом?
Подскажите как можно в Python создать динамический массив каждый элемент которого будет объектом? Я не сильна в Python, я верстаю, иногда пишу код на PHP и JS поэтому прошу не придираться строго к терминам )))
Требуется создать массив colors (цвета) и в нем объекты (конкретный цвет) У каждого из объектов есть параметры: путь к картинке и заголовок. Если написать на JS то будет массив объектов такого вида:
let colors = [ < src: "/assets/images/colors/Черный-id-457720.jpg", title: "Черный" >, < src: "/assets/images/colors/Бордовый-id-457727.jpg", title: "Бордовый" >]Массив объектов нужен для того чтобы создать JSON строку и записать ее в CSV файл. Массив я формирую на основе парсинга html страницы, использую для этого скрипт на Python библиотеке BeautifulSoup
Код на Python где я читаю html страницу и получаю нужные данные:
# цвета SKU из html блоков colors_html = soup.find(id='colors-modal').find(class_='colbasablbll').find(class_='selectcolorimi').find_all(class_='colorikki') # обхожу html блоки и получаю параметры для объекта (путь к картинке и заголовок) for item_html in colors_html: title = item_html.find('div').find('span').find('img').get('title') src = item_html.find('div').find('span').find('img').get('src')Как создать пустой массив, который я буду в цикле for заполнять объектами?
- Вопрос задан более двух лет назад
- 454 просмотра
Динамический массив
Массив — это набор однотипных переменных, доступ к которым осуществляется по индексу.
Динамический или расширяющийся массив — это массив, который может изменять свой размер в зависимости от количества элементов в нём.
Динамические массивы обычно используют, когда заранее предсказать размер массива сложно или невозможно. В таком контексте у динамических массивов помимо операций доступа и изменения произвольных элементов есть ещё три:
- Добавить в конец массива элемент $x$.
- Удалить последний элемент массива.
- Узнать размер массива.
При этом все операции должны выполняться за $O(1)$ — необязательно в худшем случае, но амортизировано.
#Реализация
Динамические массивы, как и все структуры этого раздела, есть почти во всех языках программирования, однако для полноты понимания очень рекомендуется научиться писать их с нуля, потому что они в дальнейшем будут использоваться для всех остальных структур.
Если обычные массивы — это просто последовательные области в памяти, то динамический массив обычно реализуют как структуру, которая содержит:
- указатель на массив $t$,
- размер этого массива,
- текущее число элементов (меньшее размера массива $t$).
При этом внутренний массив $t$ расширяют (деаллоцируют и заново аллоцируют с большим размером), когда он становится полностью заполненным, и требуется добавить ещё один элемент. Также опционально можно сжимать массив, когда доля заполненных элементов станет малой — это позволит вернуть не использующуюся память.
#Время работы
В худшем случае операции добавления и удаления работают за линейное время, потому что нам нужно пересоздавать весь массив размера $O(n)$. Однако амортизировано все операции будут работать за $O(1)$. Применим метод предоплаты чтобы это показать.
#add
Пусть единицей стоимости операции является одна монетка. Тогда при каждой операции add , при которой нам не требуется копирование, мы будем платить три монетки: одна из них пойдёт на стоимость самой этой операции, а две будут в резерве — если мы добавили $k$-ый элемент, мы будем класть по одной монетке к элементам с номерами $k$ и $(k−\frac)$.
К тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которой мы и сможем оплатить его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add — 3, и среднее время её работы — $O(1)$.
#del
При каждой обычной операции del будем платить две монетки. Одну из них потратим на непосредственно удаление последнего ($k$-того) элемента, другую положим рядом с элементом, стоящим на позиции $(k \bmod \frac)$. Тогда даже в худшем случае — если мы только что расширились, а потом удалили $\frac$ элементов с конца — у каждого элемента из первых $\frac$ будет по монете, которые мы и потратим на их перемещение.
#В языках программирования
#std::vector
В С++ динамический массив реализован в структуре vector из стандартной библиотеки.
При попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера — в 2 раза при компиляции через GCC и в 1.5 при компиляции через MSVC. При удалении элементов уменьшение размера массива не происходит.
Получить capacity у vector можно с помощью одноимённой функции:
Будет выведено:
size: 1, capacity 1 size: 2, capacity 2 size: 3, capacity 4 size: 4, capacity 4 size: 5, capacity 8 size: 6, capacity 8 size: 7, capacity 8 size: 8, capacity 8 size: 9, capacity 16 size: 10, capacity 16 При инициализации vector по-умолчанию начальный размер (который capacity ) равен 0, однако многие использующие его внутри структуры часто резервируют какой-то начальный размер — например, 16 или 32 элементов — чтобы сэкономить время из предположения, что там будет храниться не один элемент.
#Python
В Питоне обычные списки выполняют роль расширяемых массивов.