Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Línuleg leit]
[Patrick Schmid, Harvard University]
[Þetta er CS50.] [CS50.TV]
Searching er eitthvað sem þú gerir sennilega oftar en þú heldur.
Vitanlega, í hvert skipti sem þú opnar vafrann
og leita að vefsíðu -
eða leita að vini þínum á uppáhalds félagslegur net staður -
þú ert að leita.
En það er bara lítill hluti af rannsakandi sem þú gerir á hverjum degi.
Þegar þú vilt finna að einn blár bolur í skápnum,
eða að fullkomin rauður blússa fyrir tilefnið,
þú ert að leita.
Þegar þú ferð í verslun sem þú hefur aldrei verið til áður,
og þú ert að leita að spergilkál í framleiða gang
þú ert að leita.
Það sem þú gætir hafa byrjað að taka eftir
er að ráðast á það sem þú ert að leita að
eða hvernig hlutir eru skipulögð þegar þú ert að leita að þeim
það hefur áhrif á hvernig þú leitar.
Til dæmis, ef skyrtur eru að hanga í skápnum,
getur þú sennilega bara tekið það út án þess að mikið að leita.
Ef þú ert hrokafullur þú ert að ganga niður á fullu
að fá brokkolí, hefur þú líklega að líta á alla aðra grænmeti
áður en þú kemst að því að spergilkál.
Línuleg Leit er dæmi um einn slíkan að leita aðferð - eða reiknirit.
Eins og nafnið gefur til kynna,
þessi aðferð leitar fyrir hlut í línulega tísku, hver á eftir öðrum.
Svo, þegar þú ert að leita á niðurstöðum uppáhalds leitarvélina þína
og lesa niður listann á árangri,
þú ert að nota línulega leit.
Allt í lagi. Við skulum líta á dæmi.
Segjum að við höfum lista yfir númer - 2, 4, 0, 5, 3, 7, 8, og 1 -
og við erum að leita að númer 0.
Vitanlega getur þú bara sjá að 0 er í þriðja sæti.
En, tölvuforrit er ekki heppinn.
Það getur aðeins "séð" eitt númer í einu.
Svo byrja í upphafi á listanum,
það aðeins "sér" The 2.
Forritið athugar þá - er 2 jöfn 0?
Vitanlega ekki. Svo fer það í næstu tölu, 4.
Er 4 jöfn 0? Nope.
Næsta einn, 0. Ah! Zero er jafn 0.
Þar höfum við það! Það er í þriðja sæti.
Allt í lagi. Við skulum líta á sumir sauðakóðanum.
Það er eini a par af línum langur, en við skulum líta á það eina línu í einu.
Í fyrsta lagi skulum við skilgreina aðgerðina - og við erum að fara að kalla það línuleg leit -
og það tekur tvær rök - takkann og fylkisins.
Lykillinn er að gildi sem við erum að leita að,
svo í fyrra dæmi, sem var núll.
An array er listi af númerum
sem hefur öll þau gildi sem við erum að fara að leita.
Svo, það sem við viljum gera er að við viljum líta á -
frá öllum stöðum, svo að byrja í upphafi í fylkinu
Til mjög enda fylkisins - svo lengd fylkisins -
líta á hvert einasta stað og athuga hvert og eitt.
Svo það er það sem "fyrir" lykkja er að gera.
Og á hverjum stað, við erum að fara að segja
"Er að gildi á þeim núverandi stöðu jafn takkann sem við erum að leita að?"
Svo - í fyrra dæmi aftur, lykill var 0 -
þannig að við erum að segja "Er array á stöðu i jöfn núlli"
Ef það er, við erum að fara að fara aftur 'ég' vegna þess að það er núverandi stöðu sem við erum í.
Svo, í fyrra dæmi,
sem var þriðja sætið.
Ef við höfum farið í gegnum allt array
og við höfum ekki fundið neitt -
þannig að við skulum segja að við vorum að leita að númer 500
sem greinilega var ekki í því dæmi -
við verðum að fara aftur eitthvað,
og við erum að fara að fara aftur -1.
Og við erum bara aftur -1 vegna þess að það er staða
það er ekki til í fylki.
Og svo þýðir að þegar þú færð hana til baka úr aðgerð
það segir "Hmm, allt í lagi. Ég held ég hafi ekki fundið neitt.
Svo að 500 var aldrei þar. "
The ágætur hlutur óður í línulega leit er að
það verður að vinna á hvaða lista af hlutum,
óháð því hvernig hlutir eru pöntuð.
Það skiptir ekki máli hvar spergilkál er í framleiða gang.
Svo lengi sem þú gengur niður á fullu frá upphafi til enda,
þú ert á leiðinni til að finna það,
miðað við verslun hefur ekki hlaupa út af spergilkál, auðvitað.
En helsti styrkur það er einnig mesta veikleika þess.
Segjum að þú ert með lista yfir tvö hundruð talna
sem raðað 1-200.
Ef þú ert að leita að númer 198,
þú þarft að leita nánast heilan lista af númerum
áður en þú finnur það sem þú ert að leita að.
Það hlýtur að vera betri leið!
Hvíla sjálfsöruggur er.
En, það er umræða fyrir annan vídeó.
Einnig, ekki kvarta ekki!
Bara vegna þess að línuleg leit er ekki besta lausnin í öllum tilfellum,
það þýðir ekki að það er ekki að koma sér vel.
Annars, hvernig væri að finna að spergilkál í framleiða gang?
Nafn mitt er Patrick Schmid, og þetta er CS50.
[CS50.TV]