10 Питхон структуре података [Explained With Examples]

Да ли желите да додате структуре података у ваш програмски алат? Предузмите прве кораке већ данас тако што ћете научити о структурама података у Питхон-у.

Када учите нови програмски језик, важно је да разумете основне типове података и уграђене структуре података које језик подржава. У овом водичу о структурама података у Питхон-у ћемо покрити следеће:

• предности структура података
• уграђене структуре података у Питхон-у, као што су листе, тупле, речници и скупови
• имплементације апстрактних типова података као што су стекови и редови.

Почнимо!

Зашто су структуре података корисне?

Пре него што пређемо на различите структуре података, да видимо како коришћење структура података може бити од помоћи:

• Ефикасна обрада података: Одабир праве структуре података помаже у ефикаснијој обради података. На пример, ако треба да складиштите колекцију ставки истог типа података—са ​​константним временима тражења и чврстом спрегом—можете да изаберете низ.
• Боље управљање меморијом: У већим пројектима, за складиштење истих података, једна структура података може бити меморијски ефикаснија од друге. На пример, у Питхон-у се и листе и торке могу користити за чување колекција података истог или различитих типова података. Међутим, ако знате да не морате да мењате колекцију, можете изабрати тупле који заузима релативно мање меморије од листе.
• Организованији код: Коришћење праве структуре података за одређену функционалност чини ваш код организованијим. Други програмери који читају ваш код ће очекивати да користите специфичне структуре података у зависности од жељеног понашања. На пример: ако вам је потребно мапирање кључ/вредност са константним временима тражења и уметања, можете да ускладиштите податке у речнику.

Листе

Када треба да креирамо динамичке низове у Питхон-у — од интервјуа за кодирање до уобичајених случајева употребе — листе су структуре података које треба да одете.

Питхон листе су типови података контејнера који су променљиви и динамички, тако да можете да додајете и уклањате елементе са листе на месту – без потребе да правите копију.

Када користите Питхон листе:

• Индексирање у листу и приступање елементу на одређеном индексу је операција константног времена.
• Додавање елемента на крај листе је операција константног времена.
• Уметање елемента на одређеном индексу је операција линеарног времена.

Постоји скуп метода листе које нам помажу да ефикасно обављамо уобичајене задатке. Исечак кода у наставку показује како да извршите ове операције на листи примера:

>>> nums = [5,4,3,2]

>>> nums.append(7)
>>> nums
[5, 4, 3, 2, 7]

>>> nums.pop()
7
>>> nums
[5, 4, 3, 2]

>>> nums.insert(0,9)
>>> nums
[9, 5, 4, 3, 2]

Питхон листе такође подржавају сечење и тестирање чланства користећи ин Оператор:

>>> nums[1:4]
[5, 4, 3]

>>> 3 in nums
True

Структура података листе није само флексибилна и једноставна, већ нам омогућава и складиштење елемената различитих типова података. Питхон такође има наменску структуру података низа за ефикасне елементе складиштења истог типа података. О томе ћемо сазнати касније у овом водичу.

Туплес

У Питхон-у, тупле су још једна популарна уграђена структура података. Оне су као Питхон листе по томе што их можете индексирати у сталном времену и исецкати их. Али они су непроменљиви, тако да их не можете мењати на месту. Следећи исечак кода објашњава горе наведено са примером нумс тупле:

>>> nums = (5,4,3,2)

>>> nums[0]
5

>>> nums[0:2]
(5, 4)

>>> 5 in nums
True

>>> nums[0] = 7 # not a valid operation!
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Дакле, када желите да креирате непроменљиву колекцију и да будете у могућности да је ефикасно обрађујете, требало би да размислите о коришћењу тупле. Ако желите да колекција буде променљива, радије користите листу.

📋 Сазнајте више о сличностима и разликама између Питхон листа и торки.

Низови

Низови су мање познате структуре података у Питхон-у. Оне су сличне Питхон листама у смислу операција које подржавају, као што је индексирање у константном времену и уметање елемента у одређени индекс у линеарном времену.

Међутим, кључна разлика између листа и низова је у томе што низови чувају елементе једног типа података. Због тога су тесно повезани и ефикаснији за меморију.

Да бисмо креирали низ, можемо користити конструктор арраи() из уграђеног модула низа. Конструктор низа() узима стринг који специфицира тип података елемената и елемената. Овде креирамо нумс_ф, низ бројева са плутајућим зарезом:

>>> from array import array
>>> nums_f = array('f',[1.5,4.5,7.5,2.5])
>>> nums_f
array('f', [1.5, 4.5, 7.5, 2.5])

Можете индексирати у низ (слично Питхон листама):

>>> nums_f[0]
1.5

Низови су променљиви, тако да можете да их мењате:

>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])

Али не можете да измените елемент да буде другог типа података:

>>> nums_f[0]='zero'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: must be real number, not str

Стрингс

У Питхон стрингови су непроменљиве колекције Уницоде знакова. За разлику од програмских језика као што је Ц, Питхон нема наменски тип података карактера. Дакле, карактер је такође низ дужине један.

Као што је поменуто, стринг је непроменљив:

>>> str_1 = 'python'
>>> str_1[0] = 'c'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

Питхон стрингови подржавају сечење стрингова и скуп метода за њихово форматирање. Ево неколико примера:

>>> str_1[1:4]
'yth'
>>> str_1.title()
'Python'
>>> str_1.upper()
'PYTHON'
>>> str_1.swapcase()
'PYTHON'

⚠ Запамтите, све горе наведене операције враћају копију стринга и не мењају оригинални стринг. Ако сте заинтересовани, погледајте водич о Питхон програмима о стринг операцијама.

Сетови

У Питхон-у, скупови су колекције јединствених и хешираних ставки. Можете да извршите уобичајене скупове операције као што су унија, пресек и разлика:

>>> set_1 = {3,4,5,7}
>>> set_2 = {4,6,7}

>>> set_1.union(set_2)
{3, 4, 5, 6, 7}

>>> set_1.intersection(set_2)
{4, 7}

>>> set_1.difference(set_2)
{3, 5}

Скупови су подразумевано променљиви, тако да можете да додајете нове елементе и мењате их:

>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}

📚 Читање скупова у Питхон-у: Комплетан водич са примерима кода

ФрозенСетс

Ако желите непроменљив скуп, можете користити замрзнути скуп. Можете креирати замрзнути скуп од постојећих скупова или других итерабле.

>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})

Пошто је фрозенсет_1 замрзнут скуп, наилазимо на грешке ако покушамо да додамо елементе (или га на други начин изменимо):

>>> frozenset_1.add(15)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

Речници

Питхон речник је функционално сличан хеш мапи. Речници се користе за чување парова кључ-вредност. Кључеви речника треба да буду хеширајући. Што значи да се хеш вредност објекта не мења.

Можете да приступите вредностима помоћу тастера, убаците нове ставке и уклоните постојеће ставке у сталном времену. Постоје методи речника за обављање ових операција.

>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}

>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}

>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}

ОрдередДицт

Иако Питхон речник обезбеђује мапирање кључ-вредност, он је инхерентно неуређена структура података. Од Питхон-а 3.7, редослед уметања елемената је очуван. Али ово можете учинити експлицитнијим коришћењем ОрдередДицт из модула колекција.

Као што је приказано, ОрдередДицт чува редослед кључева:

>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='two'
>>> od['third']='three'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])

Дефаултдицт

Кључне грешке су прилично честе када радите са Питхон речницима. Кад год покушате да приступите кључу који није додат у речник, наићи ћете на КеиЕррор изузетак.

Али користећи дефаултдицт из модула колекција, овај случај можете руковати изворно. Када покушамо да приступимо кључу који није присутан у речнику, кључ се додаје и иницијализује са подразумеваним вредностима наведеним у подразумеваној фабрици.

>>> from collections import defaultdict
>>> prices = defaultdict(int)
>>> prices['carrots']
0

Стацкс

Стацк је структура података „последњи ушао-први изашао“ (ЛИФО). На стеку можемо извршити следеће операције:

• Додајте елементе на врх стека: пусх операција
• Уклоните елементе са врха стека: поп операција

Пример који илуструје како функционишу операције гурања и искакања стека:

Како имплементирати стек користећи листу

У Питхон-у можемо имплементирати структуру података стека користећи Питхон листу.

Операција на листи СтацкЕкуивалент ОператионПусх да стек топДодајте на крај листе помоћу методе аппенд()Одбаците стек топУклоните и вратите последњи елемент користећи метод поп()

Исечак кода у наставку показује како можемо да емулирамо понашање стека користећи Питхон листу:

>>> l_stk = []
>>> l_stk.append(4)
>>> l_stk.append(3)
>>> l_stk.append(7)
>>> l_stk.append(2)
>>> l_stk.append(9)
>>> l_stk
[4, 3, 7, 2, 9]
>>> l_stk.pop()
9

Како имплементирати стек користећи Декуе

Други метод за имплементацију стека је коришћење декуе из модула колекције. Декуе означава двострани ред и подржава додавање и уклањање елемената са оба краја.

Да бисмо емулирали стек, можемо:

• додај на крај низа помоћу аппенд(), и
• искочи последњи додат елемент помоћу поп().

>>> from collections import deque
>>> stk = deque()
>>> stk.append(4)
>>> stk.append(3)
>>> stk.append(7)
>>> stk.append(2)
>>> stk.append(9)
>>> stk
deque([4, 3, 7, 2,9])
>>> stk.pop()
9

Редови

Ред је структура података први ушао-први изашао (ФИФО). Елементи се додају на крај реда и уклањају се са почетка реда (главни крај реда) као што је приказано:

Можемо да имплементирамо структуру података реда користећи декуе:

• додајте елементе на крај реда користећи аппенд()
• користите метод поплефт() да уклоните елемент са почетка реда

>>> from collections import deque
>>> q = deque()
>>> q.append(4)
>>> q.append(3)
>>> q.append(7)
>>> q.append(2)
>>> q.append(9)
>>> q.popleft()
4

Хрпе

У овом одељку ћемо разговарати о бинарним хрпама. Фокусираћемо се на минималне хрпе.

Мин гомила је потпуно бинарно стабло. Хајде да разложимо шта значи комплетно бинарно стабло:

• Бинарно стабло је структура података стабла у којој сваки чвор има највише два подређена чвора тако да је сваки чвор мањи од свог потомка.
• Термин комплетно значи да је дрво потпуно попуњено, осим, ​​можда, последњег нивоа. Ако је последњи ниво делимично попуњен, попуњава се с лева на десно.

Зато што сваки чвор има највише два подређена чвора. И такође задовољава својство да је мањи од свог детета, корен је минимални елемент у мин хеап-у.

Ево примера минималне гомиле:

У Питхон-у, хеапк модул нам помаже да конструишемо гомиле и извршавамо операције на хрпи. Хајде да увеземо потребне функције из хеапк-а:

>>> from heapq import heapify, heappush, heappop

Ако имате листу или неки други итерабле, можете конструисати хрпу од ње тако што ћете позвати хеапифи():

>>> nums = [11,8,12,3,7,9,10]
>>> heapify(nums)

Можете индексирати први елемент да бисте проверили да ли је то минимални елемент:

>>> nums[0]
3

Сада ако убаците елемент у хрпу, чворови ће бити преуређени тако да задовољавају својство мин хеап-а.

>>> heappush(nums,1)

Како смо убацили 1 (1 < 3), видимо да су бројеви[0] враћа 1 што је сада минимални елемент (и основни чвор).

>>> nums[0]
1

Можете уклонити елементе из мин хеап-а тако што ћете позвати функцију хеаппоп() као што је приказано:

>>> while nums:
...     print(heappop(nums))
...

# Output
1
3
7
8
9
10
11
12

Мак Хеапс у Питхон-у

Сада када знате за минималне хрпе, можете ли погодити како можемо имплементирати максималну хрпу?

Па, можемо конвертовати минималну имплементацију гомиле у максималну гомиле множењем сваког броја са -1. Негирани бројеви распоређени у минималну хрпу су еквивалентни оригиналним бројевима распоређеним у максималној групи.

У Питхон имплементацији, можемо да помножимо елементе са -1 када додајемо елемент у гомилу користећи хеаппусх():

>>> maxHeap = []
>>> heappush(maxHeap,-2)
>>> heappush(maxHeap,-5)
>>> heappush(maxHeap,-7)

Основни чвор — помножен са -1 — биће максимални елемент.

>>> -1*maxHeap[0]
7

Када уклањате елементе из гомиле, користите хеаппоп() и помножите са -1 да бисте вратили првобитну вредност:

>>> while maxHeap:
...     print(-1*heappop(maxHeap))
...

# Output
7
5
2

Приоритетни редови

Хајде да завршимо дискусију учењем о структури података приоритетног реда у Питхон-у.

Знамо: У реду се елементи уклањају истим редоследом којим улазе у ред. Али приоритетни ред опслужује елементе по приоритету – веома корисно за апликације као што је заказивање. Дакле, у било ком тренутку се враћа елемент са највишим приоритетом.

Можемо користити тастере да дефинишемо приоритет. Овде ћемо користити нумеричке тежине за кључеве.

Како имплементирати приоритетне редове користећи Хеапк

Ево имплементације приоритетног реда користећи хеапк и Питхон листу:

>>> from heapq import heappush,heappop
>>> pq = []
>>> heappush(pq,(2,'write'))
>>> heappush(pq,(1,'read'))
>>> heappush(pq,(3,'code'))
>>> while pq:
...     print(heappop(pq))
...

Приликом уклањања елемената, ред прво служи елементу највишег приоритета (1,’читај’), затим (2,’пиши’), а затим (3,’код’).

# Output
(1, 'read')
(2, 'write')
(3, 'code')

Како имплементирати приоритетне редове користећи ПриоритиКуеуе

Да бисмо имплементирали приоритетни ред, можемо користити и класу ПриоритиКуеуе из модула куеуе. Ово такође интерно користи хрпу.

Ево еквивалентне имплементације приоритетног реда користећи ПриоритиКуеуе:

>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>> pq.put((2,'write'))
>>> pq.put((1,'read'))
>>> pq.put((3,'code'))
>>> pq
<queue.PriorityQueue object at 0x00BDE730>
>>> while not pq.empty():
...     print(pq.get())
...

# Output
(1, 'read')
(2, 'write')
(3, 'code')

Сумирајући

У овом водичу сте научили о различитим уграђеним структурама података у Питхон-у. Такође смо прегледали различите операције које подржавају ове структуре података — и уграђене методе за исто.

Затим смо прегледали друге структуре података као што су стекови, редови и приоритетни редови—и њихову Питхон имплементацију користећи функционалност из модула колекција.

Затим погледајте листу Питхон пројеката прилагођених почетницима.