Тази статия предполага, че имате основни познания за често срещани структури от данни и типове данни в Python като списъци, низове и цели числа. Ние също преминаваме към концепции като Big O нотация и обектно ориентирано програмиране.
Дори и да не разбирате напълно тези концепции, можете да прочетете и да се консултирате с документацията на Python, ако е необходимо.
В по-голямата си част понятията се обясняват в контекста на Python3.
Защо трябва да уча за речниците?
Да приемем, че пишете програма, която следи телефонни номера и имена на контакти. Можете да съхранявате тези двойки информация в списък като този:
numbers_and_people = [(5551212, "lily"), (5551234, "john")]
Дори и да знаете телефонния номер на лицето, което искате, вашата програма ще трябва да премине през всеки елемент в списъка (използвайки някакъв вид цикъл), за да го намери.
И когато вашият списък съдържа само два телефонни номера, това може да е добре.
Но какво ще стане, ако разширите списъка до хиляда числа? Или милион?
Обхождането на списъка индекс по индекс за търсене на контакт може да отнеме много, много време. Това би бил чудесен случай за използване на речник:
numbers_and_people = {5551212: "lily", 5551234: "john}
Речниците на Python са като списъци, тъй като могат да бъдат направени динамичнопо-големи, докато добавяте повече елементи.
Но за разлика от списъците те имат супер бързо време за търсене. Всичко, което трябва да знаете, за да получите стойността (напр. лицето), е ключът (напр. телефонният номер).
Ще говорим повече за това защо речниците са толкова бързи и кога трябва да ги използвате в тази статия.
Какво е речник на Python?
Първо, нека се поразровим в документите, за да разберем какво е речник. Когато търсите речници в документацията на Python, ще ги намерите изброени до списъци, набори и кортежи в „раздела за структури от данни“.
Речникът на Python е известен също като „картографиране“, защото го използвате за картографиране двойки ключ-стойност (като телефонни номера и контакти от първия пример). С други думи, на всяко място в речника имате стойност, която е присвоена на ключ.
Ключовете са начинът, по който търсите елементи в речник. Те трябва да бъдат уникални, така че да намерите правилната стойност, когато ги използвате за търсене. Стойностите могат да бъдат дублирани, както в горния пример, тъй като не ги използвате за търсене.
Нека използваме сценарий, който да ни помогне да разберем защо търсенето с речници е бързо.
Представете си, че работите в голяма офис сграда. Знаете имената на хората, които работят там и като цяло разпознавате всеки човек, когато го видите, но не знаете кой в кой офис работи.
Ако търсите Жозефина, можете да започнете от долния етаж и да почукате на всяка врата, докато я намерите. От гледна точка на нотацията Big O, това би било операция O(n) като‘n’е броят на вратите в сградата.
Може би ще имате късмет и тя е в първия офис. Това би бил най-добрият сценарий с голямо означение O(1). Може би това е най-лошият случай на O(n) ситуация и тя е чак в края на 10-ия етаж.
Въпреки че имате ключа (нейното име) и знаете стойността, която искате (Жозефина, човек) все още се нуждаете от нещо друго, за да ускорите този процес.
Би било чудесно да има номера на офиса й!
Тогава можете просто да вземете асансьора до правилния етаж и да отидете право до нейната врата. Първата врата, която опитате, ще бъде правилната и това отново ще направи сценарий O(1).
Номерът на офиса, който ускорява това, е нашата хеш стойност. Ще говорим повече за това малко по-късно.
Как работят речниците на Python зад кулисите?
Ключовете на речника трябва да бъдат обект, на който може да се присвои хеш стойност. Тези обекти са неизменни,като кортежи или низове. Те не могат да бъдат променени постфактум.
Променливи обекти като списъци, набори и речници не могат да бъдат присвоени като ключ, защото могат да бъдат променени по-късно, без да създават копие на себе си.
Ако можете да зададете списък като ключ, няма да има начин да гарантирате, че той е уникален. Можете да създадете ключа като уникален списък, който не е като всеки друг списък...
..и след това се върнете и го направете точно като друг списък-ключ по-късно.
Ако сте използвали тези списъци, за да намерите конкретна стойност, сега няма да знаете до коя стойност ще стигнете.
Сега, ако използвате [1, 2, 3] като ключ, можете да получите обратно "a_value" или можете да получите "another_value".
Това би било като да имаш куп Хосефини в един и същи офис. Когато получите номера на офиса за една Josefina (ключ), не знаете дали ще получите правилния човек (стойност).
Ето защо изискваме ключовете да бъдат едновременно уникални и неизменни.
Неизменни обекти като цели числа, плаващи числа, низове, кортежи и дори замразени набори не могат да бъдат променени без копиране на целия обект и създаване на нов идентификатор на обект.
Това създава последователност в знанието, че когато използвате този обект като търсене, ще получавате същия резултат всеки път. Поради тази причина тези обекти могат да се използват за създаване на последователна хеш стойност и за намиране на двойката ключ-стойност.
Вече споменах, че ключовете са „хеширани“. Речниците на Python се изпълняват като хеш таблица зад кулисите. Речникът използва хеш функцията на всеки ключ, за да промени част от информацията на ключа в цяло число, известно като хеш стойност.
Хеш-стойността ви казва в коя кофа трябва да бъде поставена тази двойка ключ-стойност. По този начин всеки път, когато трябва да търсите или намерите тази двойка ключ-стойност, вие знаете точно коя кофа да търсите. Ето как ключовете ви спестяват време, когато се опитвате да търсите стойност.
Кога трябва да използвам речник?
Речниците са полезни за бързо търсене и за съхраняване на уникални ключове със съответните им стойности.
И така, кога може да попаднете на речник в истинска кодова база? Ако създавате datastore или база данни във ванилен Python, тогава речникът може да бъде наистина полезен.
В горния пример създаваме хранилище за данни на всички ученици в класната стая и техните вещи. Забележете, че всички стойностиса списъци тук.
Ако разширим нашия речник до цялото училище, все още можем да търсим нещата много бързо.
Можем също да използваме речници като ценности, ако учениците трябва да имат повече категории за своите вещи.
