Renditja e një liste

Pse ka rëndësi rendi

Renditja do të thotë t'i vësh njësitë e një liste në një rend të përcaktuar, nga më e vogla te më e madhja për numrat, nga A te Zh për fjalët. Duket punë e mërzitshme, por është një nga gjërat më të dobishme që mund t'u bësh të dhënave, sepse rendi hap derën e shpejtësisë. Një listë emrash e renditur kërkohet shumë më shpejt, një listë pikësh e renditur i bën të dukshme maja dhe fundi, dhe bashkimi i dy listave të renditura është i lehtë, ndërsa bashkimi i dy të përziera nuk është.

Meqë renditja është kaq e shpeshtë, ia vlen ta kuptosh një metodë nga brenda para se t'ia lësh punën Python. Të shohësh si i lëviz njësitë vërtet një renditje ia heq misterin veglës së gatshme dhe, po aq me rëndësi, të tregon pse vegla e gatshme është ajo që duhet përdorur.

Një renditje e thjeshtë, hap pas hapi

Ja një nga renditjet më të lehta për ta përfytyruar, që shpesh quhet renditje me përzgjedhje. Ideja është e qartë: gjej njësinë më të vogël, vëre në krye, pastaj përsërit me pjesën tjetër të listës.

Merr një listë të shkurtër pikësh provimi, [70, 45, 88, 60].

• Shiko tërë listën dhe gjej më të voglën, 45. Këmbeje në krye: [45, 70, 88, 60].
• Tani mos e prek 45. Shiko pjesën tjetër dhe gjej më të voglën, 60. Këmbeje në vendin e dytë: [45, 60, 88, 70].
• Mos i prek dy të parat. Më e vogla e asaj që mbetet është 70. Këmbeje në vendin e tretë: [45, 60, 70, 88].
• Mbetet një njësi, ndaj është tashmë aty ku i takon. Mbaroi.

Në kod, dy hapat e "shikimit" bëhen një cikël brenda një cikli.

def renditje_me_perzgjedhje(pike):
    numra = list(pike)              # puno mbi një kopje, lëre origjinalin të qetë
    for fillim in range(len(numra)):
        me_e_vogla = fillim
        for i in range(fillim + 1, len(numra)):
            if numra[i] < numra[me_e_vogla]:
                me_e_vogla = i
        numra[fillim], numra[me_e_vogla] = numra[me_e_vogla], numra[fillim]
    return numra

print(renditje_me_perzgjedhje([70, 45, 88, 60]))   # [45, 60, 70, 88]

Cikli i jashtëm zgjedh çdo pozicion me radhë; cikli i brendshëm gjuan për vlerën më të vogël të mbetur për ta vënë në atë pozicion. Ajo ndërthurje është shenja që takove te Big-O: një cikël brenda një cikli mbi të dhënat.

Lëri Python ta bëjë: sorted()

Thuajse kurrë nuk do ta shkruash atë me dorë në punë të vërtetë, sepse Python të rendit tashmë. Funksioni i gatshëm sorted merr çdo listë dhe kthen një të re të renditur, dhe reverse=True e përmbys rendin.

pike = [70, 45, 88, 60]

print(sorted(pike))                 # [45, 60, 70, 88]
print(sorted(pike, reverse=True))   # [88, 70, 60, 45]
print(pike)                         # [70, 45, 88, 60], e paprekur

Ai i rendit edhe fjalët sipas alfabetit, dhe me opsionin key mund të renditë sipas asaj që zgjedh ti, si gjatësia e çdo fjale. sorted kthen një listë të freskët; metoda e listës pike.sort() bën të njëjtën punë, por e riorganizon origjinalin në vend.

Sa kushton renditja

Tani arsyeto mbi koston, që është krejt qëllimi i vënies së tyre pranë e pranë. Renditja me përzgjedhje ka një cikël brenda një cikli, ndaj puna e saj rritet si O(n²): dyfisho listën dhe puna afërsisht katërfishohet. Renditja e gatshme e Python përdor një algoritëm shumë më të zgjuar dhe rritet si O(n log n), që është dukshëm më e butë.

Mësimi është po ai që Big-O vazhdon të japë. Ta shkruash renditjen vetë ia vlen një herë, për ta parë mekanizmin. Pas kësaj, vegla që të jep gjuha është njëkohësisht më e thjeshtë dhe më e shpejtë, dhe zgjedhja e saj nuk është përtaci, është gjykim i mirë për mënyrën si shkallëzohet puna.

Vëre në punë gjithë njësinë

Ke pas vetes tri mësime arsyetimi: si ndryshojnë format e rritjes, si krahasohen dy qasje që të dyja punojnë, dhe sa kushton renditja. Praktika më poshtë është i vetmi vend në këtë njësi ku zgjedh vetë dhe pastaj e mbron zgjedhjen kur puna ndryshon nën ty.

Arsyetimi yt mbetet në këtë shfletues. Asgjë nuk ngarkohet, nuk vlerësohet dhe nuk ruhet.

Praktikë e njësisë · 15 deri në 20 min

Zgjidh një qasje, pastaj mbroje kur ndryshon puna

Ke lexuar si ndryshojnë format e rritjes. Këtu zgjedh vërtet një. Puna jote mbetet në këtë shfletues: asgjë nuk ngarkohet, nuk vlerësohet dhe nuk ruhet.

1 · Zgjidh, për punën si është tani

Një aktivitet i komunitetit ka një listë të ftuarish me rreth 200 emra. Njerëzit mbërrijnë te dera një nga një, rreth 200 mbërritje gjatë mbrëmjes. Për çdo mbërritje të duhet një përgjigje e shpejtë: a është ky person në listë?

Cilën qasje do të shkruaje?

Mbaje listën e të ftuarve si listë dhe kontrollo çdo mbërritje me `in`if person in guests:Ndërto një bashkësi nga lista, pastaj kontrollo çdo mbërritje në bashkësiguest_set = set(guests)

Me një rresht, pse? Trego çfarë po optimizon.Ruaj këtë zgjedhje

Nëse arsyetimi bllokohet, numëro ciklet

Merr kodin që ke përpara dhe numëro vetëm ciklet që kalojnë mbi të dhënat. Asnjë cikël zakonisht do të thotë O(1). Një cikël zakonisht O(n). Një cikël brenda një cikli zakonisht O(n në katror).

Kurthi është se disa cikle janë të fshehura. person in guests duket si një hap i vetëm në një rresht, por mbi një listë është cikël: Python i kalon emrat derisa gjen përputhjen. Vendose atë cikël të fshehur brenda ciklit tënd mbi mbërritjet dhe ke një cikël brenda një cikli.

Pra pyet për çdo rresht: a e prek ky rresht, në vetvete, çdo element? Nëse po, është cikël edhe kur nuk duket i tillë.

Nëse kjo t'u duk e lehtë

Kur do ta zgjidhje me qëllim formën më të ngadaltë? Përgjigjja e sinqertë është: më shpesh nga sa sugjeron një tabelë Big-O.

Ndërtimi i bashkësisë kushton një kalim mbi të dhënat dhe memorie reale. Nëse lista ka dymbëdhjetë emra, ose kontrolli bëhet një herë e kurrë më, skanimi lexohet më lehtë dhe dallimi nuk matet dot. Thjeshtësia është vlerë e vërtetë inxhinierike, jo çmim ngushëllimi.

Big-O fsheh edhe konstantet. Një qasje O(n) me një hap të shtrenjtë mund të humbasë kundër një qasjeje O(n në katror) me hap të lirë, derisa n të bëhet i madh. Shënimi të thotë cila fiton në fund, jo cila fiton sot.

Radha jote: përshkruaj një situatë nga puna ose studimi yt ku do ta mbaje me qëllim versionin më të thjeshtë e më të ngadaltë, dhe çfarë do të vëzhgoje që do të ta ndryshonte mendjen.

Rinis këtë praktikëKjo pajisje mban mend vetëm fazën ku arrite dhe opsionet që zgjodhe.

Gjete diçka të paqartë, të vjetruar ose që mund të përmirësohet? Sugjero një përmirësim

Provo veten

1. Ndiq me fjalë renditjen me përzgjedhje mbi listën [3, 1, 2]. Cila njësi lëviz e para në krye, dhe si duket lista pas çdo kalimi?
2. Renditja me përzgjedhje është O(n²) dhe sorted i Python është O(n log n). Në një listë që papritur rritet nga 100 në 1.000 njësi, pse ka shumë më tepër rëndësi ai ndryshim forme sesa te 100?
3. sorted(pike) kthen një listë të re, ndërsa pike.sort() e ndryshon origjinalin. Përshkruaj një situatë ku do të doje pikërisht ta mbaje origjinalin të pandryshuar.