Tipat abstraktë të të dhënave

Çfarë bën dhe si e bën

Kur përdor një listë në Python, tashmë e mendon në dy mënyra të veçanta pa e vënë re. Ka atë që të lejon të bësh: shto një njësi, lexo njësinë në një pozicion, kërko gjatësinë. Dhe ka si e menaxhon atë prapa skene: ku ulen vlerat në memorie, si rritet kur mbushet. Shumicën e ditëve të intereson vetëm e para. Thërret .append() dhe i beson se punon; nuk e inspekton kurrë mekanizmin.

Kjo ndarje ka një emër. Një tip abstrakt i të dhënave (abstract data type, ose ADT) është një përshkrim i një tipi të dhënash thjesht në terma të çfarë veprimesh ofron dhe si sillen ato, pa përmendur si janë ndërtuar ato veprime. Është një kontratë. Thotë "mund t'i bësh këto gjëra, dhe ja çfarë premton secila", dhe hesht për të brendshmet.

Kontrata dhe implementimi

Ndihmon të mbash dy fjalë të ndara:

• Tipi abstrakt i të dhënave është kontrata: lista e veprimeve dhe rregullat që ndjekin. Për një numërues të thjeshtë, kontrata mund të jetë "nis nga zeroja, rrit shton një, vlera raporton totalin aktual".
• Implementimi është kodi i vërtetë që e mban kontratën. Mund të kishte disa implementime të ndryshme të së njëjtës kontratë, secili me kompromiset e veta (çfarë fiton dhe çfarë humbet). Kodi që përdor vetëm veprimet e premtuara nuk e dallon dot cilin mori. Kodi që shkon përtej tyre, ose që i intereson sa zgjat një veprim, e dallon fare mirë.

Mendo një çelës drite. Kontrata është "shtyj lart për ndezje, shtyj poshtë për fikje". Nëse instalimi pas murit është i vjetër apo i ri, prej bakri apo diçka tjetër, nuk e ndryshon si e përdor çelësin. Çelësi është tipi abstrakt; instalimi është implementimi.

Pse e vlen ndarja

Të mbash kontratën ndaras nga implementimi të blen dy përparësi të vërteta.

Së pari, mund ta përdorësh një tip të dhënash duke mësuar vetëm kontratën e tij. S'të duhet të lexosh burimin e listës së Python-it për të ruajtur notat e tua në një. Veprimet e premtuara mjaftojnë.

Së dyti, kushdo që ndërton tipin mund ta ndryshojë implementimin lirisht, për sa kohë kontrata prapë qëndron. Nëse gjejnë një mënyrë më të shpejtë për të ruajtur të dhënat, kodi yt vazhdon të punojë pa u prekur, sepse u mbështet vetëm te premtimet, kurrë te mekanizmi. Kodi që mbështetet te kontrata mbijeton; kodi që fut duart te mekanizmi prishet në çastin që mekanizmi ndryshon.

Një shembull i punuar: një tabelë pikësh si kontratë

Le të themi se një lojë ka nevojë për një tabelë pikësh. Para se të shkruash një rresht kodi ruajtjeje, përshkruaj kontratën: çfarë duhet të bëjë një tabelë pikësh?

• regjistro(ekipi): jep një pikë një ekipi.
• pikat(ekipi): raporton sa pikë ka një ekip.

Ky është i gjithë tipi abstrakt. Vetëm tani zgjedh një implementim, dhe një fjalor nga mësimi i mëparshëm përshtatet pastër:

def tabele_e_re():
    return {}

def regjistro(tabela, ekipi):
    tabela[ekipi] = tabela.get(ekipi, 0) + 1

def pikat(tabela, ekipi):
    return tabela.get(ekipi, 0)

loja = tabele_e_re()
regjistro(loja, "kuq")
regjistro(loja, "kuq")
regjistro(loja, "blu")
print(pikat(loja, "kuq"))    # 2
print(pikat(loja, "gjelber"))  # 0

Pjesa tjetër e programit tënd thërret regjistro dhe pikat dhe s'e prek kurrë fjalorin drejtpërdrejt. Kjo është disiplina që të jep tipi abstrakt: nëse më vonë e ndërroje fjalorin me një ruajtje tjetër, secila prej atyre thirrjeve do të vazhdonte të punonte pa ndryshim, sepse u mbështetën vetëm te kontrata. Dy mësimet e ardhshme, për stack-et dhe radhët, janë dy kontrata të tjera pikërisht të këtij lloji.

Vëri të dyja njësitë në punë

Pohimi më sipër ia vlen të provohet e jo të besohet: se ndërrimi i ruajtjes poshtë do t'i linte të gjitha thirrjet duke punuar. Ja ndërrimi.

record(board, team)   ->  give one point to a team
points(board, team)   ->  report how many points a team has

print(points(game, "red"))

for team in game:
    print(team)

print(len(game))

record(game, "blue")

Provo veten

1. Me fjalët e tua, cili është ndryshimi mes një tipi abstrakt të të dhënave dhe implementimit të tij? Përdor idenë e çelësit të dritës ose një shembull tëndin.
2. Pse mund autori i një tipi të dhënash ta ndryshojë si i ruan të dhënat pa i prishur programet që e përdorin, për sa kohë një gjë mbetet e njëjtë? Cila është ajo gjë?
3. Në shembullin e tabelës së pikëve, pjesa tjetër e programit thërret vetëm regjistro dhe pikat. Pse ka rëndësi kjo nëse më vonë vendos t'i ruash pikët në një mënyrë krejt tjetër?