DOUG LLOYD: Bel蓹 ki, CS50, biz 蓹hat蓹 etdik m眉xt蓹lif data strukturlar谋 bir 莽ox,
sa臒?
Biz Diziler g枚r眉n眉r v蓹 ba臒l谋 etdik siyah谋lar谋, v蓹 hash masalar,
v蓹 莽al谋艧谋r, bacalar v蓹 s谋ralar谋nda.
Biz d蓹 bir az 枚yr蓹nm蓹k laz谋md谋r a臒ac v蓹 vaxt haqq谋nda
lakin, h蓹qiq蓹t蓹n, bu b眉t眉n yaln谋z son up m枚vzusunda varyasyonlar谋 olan.
H蓹qiq蓹t蓹n var bu d枚rd 蓹sas fikir c眉r
ba艧qa h蓹r 艧ey a艧a臒谋 qaynatmaq bil蓹r.
Diziler, ba臒l谋 siyah谋lar谋, hash masalar v蓹 莽al谋艧谋r.
V蓹 kimi orada ifad蓹 ed蓹r蓹k, onlara varyasyonlar谋,
lakin bu olduqca q蓹d蓹r yekunla艧d谋rmaq niyy蓹tind蓹
h蓹r 艧ey dan谋艧maq olacaq C. bax谋m谋ndan bu sinif haqq谋nda
>> Amma nec蓹 bu do臒ru, b眉t眉n t蓹dbir up edirsiniz?
Biz lehte ve eksiklikleri haqq谋nda s枚hb蓹t etdik onlara ayr谋-ayr谋 video h蓹r,
lakin n枚mr蓹l蓹ri bir 莽ox var 蓹traf谋nda at谋lan almaq.
脺mumi bir 莽ox var fikirl蓹r 蓹traf谋nda at谋lan almaq.
Nin c蓹hd v蓹 birl蓹艧dirm蓹k ed蓹k yaln谋z bir yerd蓹.
Nin qar艧谋 m眉sb蓹t 莽蓹kin ed蓹k eksiklikleri, v蓹 hesab
olan data structure Sa臒 data ola bil蓹r
x眉susi v蓹ziyy蓹t 眉莽眉n strukturu, m蓹lumatlar谋n n蓹 c眉r saxlan谋lmas谋 edirik.
Siz m眉tl蓹q h蓹mi艧蓹 ehtiyac yoxdur , super s眉r蓹tli durub, silinm蓹si istifad蓹
bir trie v蓹 axtar谋艧 蓹g蓹r h蓹qiq蓹t蓹n daxil v蓹 silm蓹 haqq谋nda qay臒谋 yoxdur
h蓹ddind蓹n art谋q 莽ox.
Yaln谋z tez t蓹sad眉fi ehtiyac varsa giri艧, b蓹lk蓹 bir s谋ra daha yax艧谋d谋r.
Bel蓹 ki, 莽蓹km蓹k ed蓹k.
D枚rd h蓹r biri haqq谋nda dan谋艧maq ed蓹k data strukturlar谋 蓹sas n枚v
biz dan谋艧d谋q v蓹 etdik ki, Onlar yax艧谋 ola bil蓹r zaman yaln谋z g枚rm蓹k,
v蓹 onlar bel蓹 yax艧谋 ola bil蓹r.
Bel蓹 ki, Diziler il蓹 ba艧lamaq ed蓹k.
Durub Bel蓹 ki, bu c眉r pis.
>> Bir s谋ra sonunda durub, OK biz getm蓹k kimi biz bir s谋ra tikinti edirsinizs蓹.
Amma biz daxil etm蓹k laz谋md谋r, 蓹g蓹r orta elementl蓹ri,
durub geri edir蓹m sort, bir 莽ox var
orada bir element uy臒un d蓹yi艧ir.
V蓹 biz daxil olacaq 蓹g蓹r h蓹r hans谋 lakin bir s谋ra sonu,
y蓹qin ki, bel蓹 b枚y眉k deyil.
>> Eynil蓹, silinm蓹si, 蓹g蓹r biz ist蓹yirik bir s谋ra sonunda silm蓹,
y蓹qin ki, h蓹m莽inin 蓹g蓹r bel蓹 b枚y眉k deyil biz bo艧 bo艧luqlar谋 t蓹rk etm蓹k ist蓹mir蓹m,
ad蓹t蓹n biz deyil.
Biz bir element aradan qald谋r谋lmas谋 ist蓹yirsinizs蓹, v蓹 sonra sort yenid蓹n rahat edir.
V蓹 bel蓹 elementl蓹ri silm蓹 bir s谋ra da o q蓹d蓹r d蓹 b枚y眉k deyil.
>> Axtar谋艧, baxmayaraq ki, b枚y眉kd眉r.
Biz t蓹sad眉fi imkan谋 var, daimi vaxt Sistemi.
Biz yaln谋z yeddi dem蓹k, v蓹 biz getm蓹k array k枚莽眉r眉lm蓹si yeddi.
Biz yolda il蓹 20 dem蓹k array k枚莽眉r眉lm蓹si 20.
Biz aras谋nda t蓹krarlamaq yoxdur.
Bu olduqca yax艧谋.
>> Diziler d蓹 d眉zm蓹k 眉莽眉n nisb蓹t蓹n asand谋r.
Biz 莽e艧idl蓹nm蓹si haqq谋nda dan谋艧d谋 H蓹r zaman Bel蓹 se莽im sort kimi alqoritm,
durub sort, bubble sort, birl蓹艧m蓹si sort, biz h蓹mi艧蓹 bunu Diziler istifad蓹
Diziler olduqca asand谋r, 莽眉nki data strukturlar谋 nisb蓹t蓹n sort,
Biz bu g眉n蓹 q蓹d蓹r g枚rd眉m.
>> Onlar h蓹m莽inin nisb蓹t蓹n ki莽ik ist蓹yirik.
茝lav蓹 yer bir 莽ox deyil.
Siz yaln谋z tam olaraq 莽ox k蓹nara sizin data ke莽irm蓹k laz谋md谋r ki,
v蓹 bu olduqca 莽ox var.
Bel蓹 ki, onlar olduqca ki莽ik ist蓹yirik, v蓹 o 艧蓹kild蓹 s蓹m蓹r蓹li.
Amma ba艧qa 陌艧in m蓹nfi t蓹r蓹fi odur, baxmayaraq ki, Onlar 枚l莽眉s眉 m眉蓹yy蓹n olunur.
Biz nec蓹 d蓹qiq elan var big biz array olmaq ist蓹yir蓹m
v蓹 biz yaln谋z bir shot almaq.
Biz inki艧af v蓹 shrink bilm蓹z.
>> Biz bunu inki艧af v蓹 ya shrink ehtiyac varsa, biz tamamil蓹 yeni array b蓹yan etm蓹k laz谋md谋r,
elementl蓹rinin b眉t眉n sur蓹ti ikinci s谋ra ilk array.
V蓹 biz miscalculated 蓹g蓹r vaxt, biz yen蓹 bunu etm蓹k laz谋md谋r.
Bel蓹 b枚y眉k deyil.
Bel蓹 ki, seriallarda, biz蓹 rahatl谋q vermir elementl蓹rin d蓹yi艧蓹n n枚mr蓹l蓹ri var.
>> Bir ba臒l谋 siyah谋 il蓹, durub olduqca asand谋r.
Biz yaln谋z qar艧谋s谋nda 眉z蓹rin蓹 tack.
Deletion d蓹 olduqca asand谋r.
Biz elementl蓹ri tapmaq laz谋md谋r.
Ki, bir axtar谋艧 daxildir.
>> Amma element g枚rd眉k Siz n蓹 etm蓹k laz谋md谋r B眉t眉n arad谋臒谋n谋z
bir g枚st蓹rici d蓹yi艧dirm蓹k deyil, b蓹lk蓹 iki varsa
bir ikiqat list-- ba臒l谋d谋r ba臒l谋 siyah谋s谋, rather--
v蓹 sonra yaln谋z node azad ed蓹 bil蓹r.
Siz ke莽m蓹k yoxdur 蓹traf谋nda h蓹r 艧ey.
Siz yaln谋z iki g枚st蓹ricil蓹rin蓹 d蓹yi艧蓹 bel蓹 ki, olduqca s眉r蓹tli var.
>> Axtar谋艧 do臒ru olsa pis?
Biz蓹 bir tapmaq 眉莽眉n 眉莽眉n bir ba臒l谋 siyah谋s谋nda element,
olub story v蓹 ya ikiqat, ba臒l谋 biz axtar谋艧 x蓹tti var.
Biz 蓹vv蓹lind蓹 ba艧lamaq laz谋md谋r v蓹 son h蓹r蓹k蓹t, v蓹 ya son h蓹r蓹k蓹t-da ba艧layacaq
蓹vv蓹lin蓹.
Biz art谋q t蓹sad眉fi 莽谋x谋艧谋 yoxdur.
Biz edirik Bel蓹 ki axtar谋艧 莽ox, b蓹lk蓹
bir ba臒l谋 siyah谋s谋 deyil bizim 眉莽眉n kifay蓹t q蓹d蓹r yax艧谋.
>> Onlar, h蓹qiq蓹t蓹n, d蓹 ist蓹yirik d眉zm蓹k 眉莽眉n 莽蓹tin, sa臒?
yegan蓹 yolu siz h蓹qiq蓹t蓹n ba臒l谋 siyah谋 d眉zm蓹k
Siz onu tikm蓹k kimi d眉zm蓹k 眉莽眉n.
Amma sizin kimi bu sort 蓹g蓹r onu tikintisi, art谋q ist蓹yirik
Art谋q tez insertions edilm蓹si.
Siz yaln谋z tacking deyilik qar艧谋s谋nda 眉z蓹rin蓹 艧eyl蓹r.
Siz tapmaq laz谋md谋r sa臒 spot qoymaq 眉莽眉n,
v蓹 sonra durub yaln谋z pis olur
bir s谋ra daxil daxil kimi.
Bel蓹 ki, ba臒l谋 siyah谋lar谋 deyil m蓹lumat 莽e艧idl蓹nm蓹si 眉莽眉n bel蓹 b枚y眉k.
>> Onlar h蓹m莽inin olduqca ki莽ik, 枚l莽眉s眉-m眉drik ist蓹yirik.
Ikiqat az siyah谋s谋n谋 ba臒l谋d谋r story ba臒l谋 siyah谋lar谋 daha b枚y眉k,
olan q蓹d蓹r b枚y眉k Diziler daha lakin bu deyil
s蓹rf kosmik b枚y眉k m蓹bl蓹臒i.
Bel蓹 ki, 蓹g蓹r yer bir m眉kafat, lakin Biz, h蓹qiq蓹t蓹n s谋x premium,
Bu getm蓹k 眉莽眉n do臒ru yol ola bil蓹r.
>> Hash masalar.
Bir hash masa durub kifay蓹t q蓹d蓹r sad蓹 deyil.
Bu iki add谋m prosesi var.
Birinci biz vasit蓹sil蓹 data run laz谋md谋r bir hash funksiyas谋 hash kodu almaq 眉莽眉n,
v蓹 sonra daxil element daxil ki, hash kodu yerd蓹 hash masa.
>> Ba臒l谋 siyah谋 ox艧ar Deletion, Siz element tapmaq bir d蓹f蓹 asand谋r.
Siz ilk tapmaq laz谋md谋r lakin sonra onu silm蓹k zaman,
Yaln谋z m眉badil蓹si etm蓹k laz谋md谋r g枚st蓹ricil蓹rin蓹 bir ne莽蓹
茝g蓹r ayr谋-ayr谋 chaining istifad蓹 edirik.
Siz probing istifad蓹 edirsinizs蓹, v蓹 ya de臒ilseniz
istifad蓹 ed蓹r蓹k, b眉t眉n chaining Sizin hash masa,
silinm蓹si, h蓹qiq蓹t蓹n, h蓹qiq蓹t蓹n asand谋r.
Siz n蓹 etm蓹k laz谋md谋r B眉t眉n hash edir data, sonra yere gedin.
V蓹 f蓹rz siz deyil H蓹r hans谋 bir toqqu艧ma var
莽ox tez silm蓹k m眉mk眉n olacaq.
>> 陌ndi axtar谋艧 harada 艧eyi edir bir az daha m眉r蓹kk蓹b almaq.
Bu daha yax艧谋 orta hesabla var ba臒l谋 siyah谋lar谋 莽ox.
Siz z蓹ncirl蓹m蓹 istifad蓹 edirsinizs蓹, Siz h蓹l蓹 bir ba臒l谋 siyah谋 var,
siz h蓹l蓹 var dem蓹kdir Axtar谋艧 ba臒l谋 siyah谋 z蓹r蓹rin蓹.
Siz alaraq edirik, 莽眉nki ancaq ba臒l谋d谋r siyah谋s谋 v蓹 100 v蓹 ya 1000-d蓹n art谋q par莽alanmas谋
v蓹 ya n sizin hash c蓹dv蓹ld蓹 elementl蓹ri, etdiyiniz ba臒l谋 siyah谋lar谋 枚l莽眉s眉 nth b眉t眉n biridir.
Onlar b眉t眉n 蓹h蓹miyy蓹tli d蓹r蓹c蓹d蓹 ki莽ik ist蓹yirik.
Siz n 蓹v蓹zin蓹 siyah谋lar谋 ba臒l谋d谋r 枚l莽眉s眉 n biri ba臒l谋 siyah谋.
>> V蓹 bu real-d眉nya daimi 脺mumiyy蓹tl蓹, biz amil,
vaxt m眉r蓹kk蓹bliyi haqq谋nda dan谋艧maq deyil, onu h蓹qiq蓹t蓹n, burada bir f蓹rq yoxdur.
Bel蓹 ki, axtar谋艧 h蓹l蓹 x蓹tti Siz z蓹ncirl蓹m蓹 kullan谋yorsan谋z axtar谋艧
lakin siyah谋s谋 uzunlu臒u Siz vasit蓹sil蓹 axtar谋艧 edirik
M眉qayis蓹 莽ox, 莽ox q谋sa.
Yen蓹 莽e艧idl蓹nm蓹si 蓹g蓹r Burada m蓹qs蓹d, hash table nin
y蓹qin ki, do臒ru yol getm蓹k 眉莽眉n deyil.
脟e艧idl蓹nm蓹si, yaln谋z bir s谋ra istifad蓹 sizin 眉莽眉n h蓹qiq蓹t蓹n vacibdir.
>> Onlar 枚l莽眉s眉 gamut 莽al谋艧t谋rabilirsiniz.
Bu s枚yl蓹m蓹k 莽蓹tindir hash table, ki莽ik v蓹 ya b枚y眉k
bu, h蓹qiq蓹t蓹n as谋l谋d谋r nec蓹 b枚y眉k sizin hash masa.
Yaln谋z saxlan谋lmas谋 olacaq edirsinizs蓹 Sizin hash masa be艧 elementl蓹ri,
v蓹 bir hash masa var bu 10.000 elementl蓹ri il蓹,
Siz y蓹qin ki, yer 莽ox israf edirik.
Kontrast d蓹 bil蓹r olan , 莽ox y谋臒cam hash masalar var
lakin ki莽ik Sizin hash masa olur bu ba臒l谋 siyah谋lar谋 h蓹r art谋q
olur.
V蓹 bel蓹 ki, h蓹qiq蓹t蓹n m眉蓹yy蓹n etm蓹k 眉莽眉n he莽 bir yol var d蓹qiq bir hash masa 枚l莽眉s眉,
lakin y蓹qin ki, g眉venli 眉mumiyy蓹tl蓹 dem蓹k
Bir ba臒l谋 daha b枚y眉k olacaq Eyni data saxlan谋lmas谋 siyah谋s谋
bir trie daha lakin ki莽ik.
>> V蓹 莽al谋艧谋r d枚rd眉nc眉 var bu strukturlar谋n
ki, biz s枚hb蓹t etdik.
Bir trie daxil daxil m眉r蓹kk蓹bdir.
Dinamik bir 莽ox var yadda艧 ayr谋lmas谋,
x眉susil蓹 蓹vv蓹lind蓹, Siz qurmaq 眉莽眉n ba艧lan臒谋c etdiyiniz kimi.
Amma bu, daimi vaxt var.
Bu, yaln谋z insan element var burada 莽蓹tin ki.
Null g枚st蓹rici qar艧谋la艧ma臒a olan malloc space, b蓹lk蓹 malloc yer getm蓹k
oradan yenid蓹n.
qorxudulmas谋 amilinin sort dinamik yadda艧 ayr谋lmas谋 g枚st蓹ricil蓹r
sil mane deyil.
Amma siz bunu tip sonra, durub h蓹qiq蓹t蓹n, olduqca sad蓹 g蓹lir
v蓹 蓹lb蓹tt蓹 ki, daimi vaxt.
>> Deletion asand谋r.
Siz n蓹 etm蓹k laz谋md谋r B眉t眉n a艧a臒谋 gedin bir g枚st蓹ricil蓹r v蓹 node ne莽蓹,
bel蓹 ki, olduqca yax艧谋.
Lookup d蓹 olduqca s眉r蓹tli edir.
Bu, yaln谋z 蓹sas谋nda Sizin data uzunlu臒u.
Sizin data b眉t眉n 蓹g蓹r Bel蓹 ki, Be艧 xarakter strings,
m蓹s蓹l蓹n, be艧 saxlan谋lmas谋 edirik Sizin trie xarakter strings,
yaln谋z be艧 add谋mlar at谋r Arad谋臒谋n谋z n蓹 tapa bil蓹rsiniz.
Be艧, bel蓹 ki, yaln谋z bir sabit amildir yen蓹 durub, silinm蓹si, v蓹 axtar谋艧
burada s蓹m蓹r蓹li, b眉t眉n daimi zaman var.
>> Ba艧qa bir 艧ey sizin trie oldu臒unu h蓹qiq蓹t蓹n c眉r art谋q sa臒, s谋ralan谋r?
Biz ne 蓹sas谋nda daxil elementl蓹ri,
bir m蓹ktub m蓹ktubu ged蓹n 蓹sas pill蓹 蓹sas v蓹 ya r蓹q蓹mli,
ad蓹t蓹n, sizin trie olan q蓹d蓹r ba艧a Siz qurmaq kimi c眉r s谋ralan谋r.
Bu, h蓹qiq蓹t蓹n edir deyil m蓹nada 莽e艧idl蓹nm蓹si haqq谋nda d眉艧眉nm蓹k
eyni 艧蓹kild蓹 biz d眉艧眉nm蓹k Bu seriallar谋n v蓹 ya ba臒l谋 siyah谋lar谋 il蓹,
v蓹 ya hash masalar.
Lakin b蓹zi m蓹nada, sizin Siz getm蓹k kimi trie 莽e艧idl蓹nir.
>> 陌艧in m蓹nfi t蓹r蓹fi odur, 蓹lb蓹tt蓹 ki, bir trie s眉r蓹tl蓹 b枚y眉k olur.
H蓹r qov艧a臒谋nda bax谋mdan, siz bil蓹r 蓹sas r蓹q蓹md蓹n ibar蓹tdir 蓹g蓹r yax艧谋d谋r,
dig蓹r 10 var yerl蓹rd蓹 getm蓹k bil蓹r ki,
h蓹r node o dem蓹kdir ki, m蓹lumat var
m蓹lumatlar谋n saxlamaq ist蓹yir蓹m ki node, plus 10 g枚st蓹ricil蓹r d蓹.
Hans谋 CS50 IDE on 80 bayt edir.
Bel蓹 ki, 蓹n az谋 80 bayt var Yaratmaq h蓹r node,
v蓹 h蓹tta data say谋lmas谋 deyil.
V蓹 qov艧aqlar谋n谋n, 蓹g蓹r 蓹v蓹zin蓹 r蓹q蓹m m蓹ktublar,
indi 26 g枚st蓹ricil蓹rin蓹 var h蓹r yerd蓹n.
V蓹 26 d蓹f蓹 8 y蓹qin ki, 200 bytes, v蓹 ya kimi bir 艧ey.
V蓹 kapital谋 var v蓹 siz lowercase--
M蓹n bu il蓹 gedir蓹m harada sa臒, g枚rm蓹k?
Sizin qov艧aqlar谋n谋n h蓹qiq蓹t蓹n 蓹ld蓹 ed蓹 bil蓹rsiniz b枚y眉k v蓹 bel蓹 trie
枚z眉, 眉mumi, bil蓹rsiniz 莽ox, h蓹qiq蓹t蓹n b枚y眉k almaq.
Space y眉ks蓹k oldu臒u halda bel蓹 sistem m眉kafat,
bir trie do臒ru yol ola bil蓹r h蓹tta dig蓹r faydalar谋 olsa da, getm蓹k
oyun minir.
M蓹n Doug Lloyd edir蓹m.
Bu CS50 edir.