>> დინამიკები 1: ყველა უფლება, ასე რომ ეს არის CS50 ეს არის ბოლომდე კვირაში ხუთი.
და გავიხსენოთ, რომ ბოლო დროს ჩვენ დაიწყო ეძებს fancier მონაცემები
სტრუქტურების, რომ დაიწყო გადაჭრა პრობლემა, რომელიც დაიწყო დანერგვა
ახალი პრობლემები, მაგრამ ამ გასაღები იყო ერთგვარი threading, რომ ჩვენ
დავიწყე ეხლა კვანძის კვანძის.
ასე რომ, ეს, რა თქმა უნდა საგნით უკავშირდება სიაში.
და ცალკე უკავშირდება, ვგულისხმობ იქ მხოლოდ ერთი
ძაფი შორის თითოეული იმ კვანძების.
თურმე შეგიძლიათ გააკეთოთ fancier რამ, როგორიცაა ორმაგად უკავშირდება სიები
რომლის დროსაც თქვენ გაქვთ arrow აპირებს ორივე მიმართულებით, რომელიც
დაგეხმარებათ გარკვეული ეფექტურობის.
მაგრამ ეს პრობლემა მოაგვარა?
რას აკეთებდა ეს მოგვარება?
რატომ ჩვენ ვზრუნავთ ორშაბათს?
რატომ, თეორიულად, ჩვენ არ მაინტერესებს ორშაბათს?
რას აკეთებთ?
>> აუდიტორია: ჩვენ შეგვიძლია დინამიურად შეცვლის მას.
>> დინამიკები 1: OK, ასე რომ ჩვენ შეგვიძლია დინამიურად შეცვლის მას.
კარგად გაკეთდეს, როგორც თქვენ.
ასე რომ, შეგიძლიათ დინამიურად ზომის შეცვლა მონაცემთა სტრუქტურა, ხოლო მასივი,
გავიხსენოთ, თქვენ უნდა იცოდეს აპრიორი, თუ რამდენად სივრცეში გსურთ
და თუ საჭიროა ცოტა მეტი სივრცეში, თქვენ სახის out of luck.
თქვენ უნდა შექმნათ მთელი ახალი მასივი.
თქვენ უნდა გადავიდეს ყველა თქვენი მონაცემები ერთი სხვა,
საბოლოოდ გასათავისუფლებლად წლის მასივი თუ შეგიძლია, და შემდეგ გაგრძელება.
რომელი უბრალოდ გრძნობს ძალიან ძვირი და ძალიან არაეფექტური და მართლაც, ეს შეიძლება იყოს.
მაგრამ ეს არ არის ყველა კარგი.
ჩვენ გადაიხადოს ფასი, რა იყო ერთი უფრო აშკარა ფასები ჩვენ
გადახდა გამოყენების უკავშირდება სიაში?
>> აუდიტორია: ჩვენ უნდა გამოვიყენოთ ორმაგი სივრცის თითოეული.
დინამიკები 1: ჰო, ამიტომ ჩვენ უნდა მინიმუმ ორჯერ იმდენი სივრცე.
ფაქტობრივად, მივხვდი, ეს სურათის კიდევ ცოტა დამაბნეველი,
რადგან CS50 IDE ბევრი თანამედროვე კომპიუტერები, მომცეთ ან მისამართი
არ არის ის ფაქტი, ოთხი ბაიტი.
ეს ძალიან ხშირად ეს დღის რვა ბაიტს, რომელიც
იმას ნიშნავს, რომ ბოლოში ყველაზე ოთხკუთხედს იქ რეალობა
სახის ორჯერ დიდი, რაც მე შედგენილი,
რაც იმას ნიშნავს, რომ თქვენ იყენებთ სამჯერ იმდენი სივრცე, როგორც ჩვენ შეიძლება სხვაგვარად.
ახლა, ამავე დროს, ჩვენ ჯერ კიდევ საუბარი bytes, არა?
ჩვენ არ ემთხვეოდეს საუბარი მბ ან გიგაბაიტი,
თუ ეს მონაცემები სტრუქტურების კიდევ დიდი.
>> ასე რომ, დღეს ჩვენ ვიწყებთ განიხილოს როგორ შეიძლება შეისწავლონ მონაცემები
უფრო ეფექტურად, თუ ფაქტი მონაცემები იღებს დიდია.
მაგრამ მოდით ცდილობენ canonicalize ოპერაციების პირველი
რომ შეგიძლიათ გააკეთოთ ეს სახის მონაცემების სტრუქტურები.
ასე რომ, რაღაც კავშირშია სია ზოგადად მხარს უჭერს
ოპერაციების მინდა წაშლა, ჩადეთ და ძიება.
და რას ნიშნავს, რომ?
ეს მხოლოდ იმას ნიშნავს, რომ, როგორც წესი, იმ შემთხვევაში, თუ ადამიანი იყენებს უკავშირდება სია,
ისინი ან ვინმეს აქვს განხორციელებული ფუნქციები, როგორიცაა წაშლის, კულტურა,
და ძებნის, ასე რომ თქვენ შეგიძლიათ რეალურად რაღაც
სასარგებლო მონაცემების სტრუქტურას.
მოდით მიიღოს სწრაფი შევხედოთ როგორ შეიძლება განახორციელოს
ზოგიერთი კოდი უკავშირდება სია ასეთია.
>> ასე რომ, ეს არის რამოდენიმე C კოდი, არა თუნდაც სრული პროგრამა
რომ მე ნამდვილად სწრაფად წააქეზა.
ეს არ არის ამჟამად განაწილების კოდი, იმიტომ, რომ ის რეალურად არ აწარმოებს.
მაგრამ შეამჩნია მე უბრალოდ ერთად კომენტარის განაცხადა,
dot dot dot, რაღაც იქ, dot dot dot, რაღაც არსებობს.
და მოდით შევჩერდეთ რა წვნიანი ნაწილები.
ასე რომ ხაზი სამი, გავიხსენოთ, რომ ეს არის
ჩვენ შევთავაზეთ გამოცხადების კვანძის ბოლო დროს, ერთ-ერთი იმ მართკუთხა ობიექტები.
მას აქვს int, რომ ჩვენ მოვუწოდებთ N, მაგრამ ჩვენ შეგვიძლია ეძახით არაფერი,
და შემდეგ struct კვანძის ვარსკვლავი მოუწოდა შემდეგი.
და უბრალოდ უნდა იყოს მკაფიო, რომ მეორე ხაზი, ხაზი ექვსი, რა არის ეს?
რა არის ეს აკეთებენ?
იმის გამო, რომ, რა თქმა უნდა უფრო cryptic ვიდრე ჩვენი ჩვეულებრივი ცვლადი.
>> აუდიტორია: რაც მას გადაადგილება ერთი.
>> დინამიკები 1: რაც მას გადაადგილება ერთი.
და იყოს უფრო სწორად, ეს იქნება შესანახად მისამართი
კვანძი, რომელიც ნიშნავს, რომ სემანტიკურად შემდეგ იგი, არა?
ასე რომ, ის არ აპირებს აუცილებლად გადავა არაფერი.
ეს უბრალოდ აპირებს შესანახად ღირებულება, რომელიც არის
იქნება მისამართი ზოგიერთი სხვა კვანძის,
და ამიტომაც ჩვენ განაცხადა struct კვანძის ვარსკვლავი, ვარსკვლავი აღმნიშვნელი
მომცეთ ან მისამართი.
OK, ასე რომ, ახლა თუ ვივარაუდოთ, რომ ჩვენ გვაქვს ამ N ჩვენს ხელთ არსებული, და მოდით
ვივარაუდოთ, რომ ვინმეს აქვს ჩასმული მთელი bunch of რიცხვებით
შევიდა უკავშირდება სიაში.
და რომ უკავშირდება სია აღნიშნა, რომ ზოგიერთი წერტილი
ცვლადში სია რომ გადავიდა აქ, როგორც პარამეტრი,
როგორ შემიძლია წასვლა ონლაინ 14 ახორციელებს ძიება?
სხვა სიტყვებით, თუ მე ახორციელებს ფუნქცია, რომლის მიზანი ცხოვრებაში
არის მიიღოს int და შემდეგ დასაწყისი უკავშირდება სია,
რომ არის მაჩვენებელი უკავშირდება სიაში.
პირველი, რომელიც მე ვფიქრობ, დავით იყო ჩვენი მოხალისე ორშაბათს,
იგი მიუთითებს მთელი უკავშირდება სიაში,
ეს თითქოს ჩვენ ავლით დავით, როგორც ჩვენი არგუმენტი აქ.
როგორ უნდა წავიდეს შესახებ გადიოდა ამ სიაში?
ისე, გამოდის, რომ მიუხედავად იმისა, რომ პოინტერები შედარებით ახალი ახლა ჩვენთვის,
ჩვენ შეგვიძლია ამის გაკეთება შედარებით პირდაპირ.
>> მე ვაპირებ წავიდეთ წინ და განაცხადოს დროებითი ცვლადი, რომ
კონვენციის უბრალოდ აპირებს ეწოდოს მაჩვენებელი, ან PTR,
მაგრამ თქვენ ვერ ვუწოდებ არაფერი გსურთ.
და მე ვაპირებ ინიციალიზაცია ის დაწყების სიაში.
ასე რომ თქვენ შეგიძლიათ სახის ვფიქრობ ეს როგორც ჩემთვის მასწავლებელი მეორე დღეს,
სახის მიუთითებს ვინმე მათ შორის ჩვენი ადამიანები, როგორც მოხალისეები.
ასე რომ, მე დროებითი ცვლადი, რომ მხოლოდ მიუთითებს, რომ იგივე
რომ ჩვენი ერთსა დაასახელა მოხალისე დავით ასევე მიუთითებს,.
ახლა, ხოლო მაჩვენებელი არ null, იმიტომ, რომ გავიხსენოთ
რომ null არის რაღაც განსაკუთრებული Sentinel ღირებულება demarcates ბოლოს სიაში,
ასე რომ, როდესაც მე არ მიუთითებს ადგილზე, ისევე როგორც ჩვენი ბოლო მოხალისე
იყო, მოდით წავიდეთ წინ და ამის შემდეგ.
თუ მაჩვენებელი და ახლა მე ასეთი მინდა გავაკეთოთ ის, რაც ჩვენ გავაკეთეთ სტუდენტი
სტრუქტურა თუ მაჩვენებელი dot შემდეგი equals-- უფრო სწორად, თუ მაჩვენებელი dot N უდრის
უდრის ცვლადი N, არგუმენტი, რომ უკვე გავიდა,
მაშინ მინდა წავიდეთ წინ და აცხადებენ, რომ დაბრუნდება ნამდვილი.
მე აღმოვაჩინე ნომერი N შიგნით ერთი კვანძების ჩემი დაკავშირებული სიაში.
მაგრამ dot აღარ მუშაობს ამ კონტექსტში,
იმიტომ, რომ მაჩვენებელი, PTR, არის მართლაც მაჩვენებელი, მისამართი,
ჩვენ რეალურად შეუძლია შესანიშნავად გამოყენება საბოლოოდ ნაჭერი სინტაქსი
რომ სახის მარკა ინტუიციური გრძნობა და რეალურად
გამოიყენოთ arrow, რაც იმას ნიშნავს გადასვლა რომ მიმართვაში რიცხვი იქ.
ასე რომ, ეს ძალიან ჰგავს სული რომ dot ოპერატორი,
არამედ იმიტომ, რომ მაჩვენებელი არ მომცეთ და არა ფაქტობრივი struct თავისთავად,
ჩვენ უბრალოდ გამოიყენოთ arrow.
>> ასე რომ, თუ მიმდინარე კვანძის, რომ მე, დროებითი ცვლადი, ვარ მიუთითებს
არ არის ნ, რა უნდა გავაკეთოთ?
ისე, ჩემი ადამიანის მოხალისეები რომ ჩვენ გვქონდა აქ მეორე დღეს,
თუ ჩემი პირველი ადამიანის არ არის, მე მინდა, და იქნებ მეორე ადამიანის არ
ერთი მინდა, და მესამე, მე უნდა შევინარჩუნოთ ფიზიკურად მოძრაობს.
როგორიცაა როგორ ნაბიჯ მეშვეობით სიაში?
როდესაც ჩვენ გვქონდა მასივი, თქვენ უბრალოდ გააკეთეს, როგორიც მე plus plus.
მაგრამ ამ შემთხვევაში, საკმარისია ამის მაჩვენებელი, იღებს, მაჩვენებელი, მომავალი.
სხვა სიტყვებით, მომდევნო სფეროში როგორც ყველა მარცხენა ხელში
რომ ჩვენი ადამიანის მოხალისეები ორშაბათს ინტენსიურად იყენებდა აღვნიშნო ზოგიერთი სხვა კვანძის.
ეს იყო მათი მომავალი მეზობლები.
>> ასე რომ, თუ მინდა დახევას ამ სიაში, მე არ შემიძლია უბრალოდ მე plus plus აღარ,
მე ნაცვლად უნდა ვთქვა მე, მაჩვენებელი, აპირებს
ერთნაირი რაც მომდევნო ველი, შემდეგი სფეროში, მომდევნო ველი,
შემდეგ ყველა იმ მარცხენა ხელში რომ ჩვენ გვქონდა სცენაზე მიუთითებს
ზოგიერთი შემდგომი ღირებულებებს.
და თუ მივიღებ მეშვეობით რომ მთელი iteration,
და ბოლოს, მე მოხვდა null არ მქონე ი ნ მაინც, მე დააბრუნებს false.
ასე რომ კიდევ ერთხელ, ყველა, რომ ჩვენ ვაკეთებთ აქ, როგორც ერთ სურათზე მომენტში წინ,
იწყება მიერ მიუთითებს დაწყებული სიაში, სავარაუდოდ.
და მერე შეამოწმოს, არის ღირებულება ვეძებ ტოლია ცხრა?
თუ ასეა, მე დაბრუნდეს ჭეშმარიტი და მე გაკეთდეს.
თუ არა, მე ჩემ მხრივ, AKA მაჩვენებელი, უნდა აღვნიშნო,
მომდევნო arrow ადგილმდებარეობა, და მაშინ შემდეგი arrow ადგილმდებარეობა,
და მომავალი.
მე უბრალოდ გავლით ამ მასივი.
>> ასე რომ კიდევ ერთხელ, ვინ ზრუნავს?
Like რა არის ეს ნივთიერება?
ასევე, გავიხსენოთ, რომ ჩვენ გააცნო ცნება დასტის, რომელიც
არის აბსტრაქტული მონაცემები აკრიფოთ იმდენად, რამდენადაც ეს არ არის C ის, რომ ეს არ არის CS50 რამ,
ეს აბსტრაქტული იდეა, ეს იდეა დაწყობა რამ თავზე ერთმანეთს
რომ შეიძლება განხორციელდეს მტევნების სხვადასხვა გზები.
და ერთი გზა შევთავაზეთ იყო მასივი, ან უკავშირდება სიაში.
და აღმოჩნდება, რომ კანონიკური, რომელიც დასტის მხარს უჭერს მინიმუმ ორი ოპერაცია.
და ხმაურს სიტყვები ბიძგი, რათა დააყენებს რაღაც გადატანა დასტის,
როგორც ახალი უჯრა სასადილოს, ან პოპ,
რაც იმას ნიშნავს, რომ ამოიღონ უმაღლეს უჯრა დასტის სასადილო
დარბაზში, მაშინ შესაძლოა, რამდენიმე სხვა ოპერაციები, ასევე.
ასე როგორ შეიძლება ჩვენ განსაზღვრავს სტრუქტურა რომ ჩვენ ახლა მოუწოდებს დასტის?
>> ისე, ჩვენ გვაქვს ყველა საჭირო სინტაქსი ჩვენს განკარგულებაში C. მე ვიტყვი,
მომეცი ტიპის განსაზღვრება არის struct შიგნით დასტის,
მე ვაპირებ ვთქვა მასივი, საქართველოს მთელი bunch of ნომრები და შემდეგ ზომა.
სხვა სიტყვებით, თუ მინდა, განახორციელოს ეს კოდი,
ნება მომეცით წავიდეთ და მხოლოდ სახის მიაპყროს რას გვეუბნება ეს.
ასე რომ, ეს ამბობს, მომეცი სტრუქტურა, რომელიც მიიღო მასივი,
და მე არ ვიცი, რა სიმძლავრე, ეს, სავარაუდოდ, რამდენიმე მუდმივი, რომ მე
განსაზღვრული სხვაგან, და ეს ჯარიმა.
მაგრამ ვფიქრობ, რომ ეს არის მხოლოდ ერთი, ორი, სამი, ოთხი, ხუთი.
ასე რომ, მოცულობა 5.
ამ ელემენტს შიგნით ჩემი სტრუქტურა იქნება მოუწოდა ნომრები.
და მერე უნდა ერთი სხვა ცვლადი, როგორც ჩანს,
მოუწოდა ზომა, რომ თავდაპირველად მე ვაპირებ ითვალისწინებს ინიციალიზაცია ნულოვანი.
თუ არაფერი არ არის დასტის, ზომა არის ნულოვანი,
და ეს არის ნაგვის ღირებულებების ნომრები.
მე არ ვიცი, რა არის იქ უბრალოდ არ არის.
>> ასე რომ, თუ გსურთ დააყენებს რაღაც გადატანა დასტის,
ვფიქრობ, მოვუწოდებთ ფუნქცია ბიძგი და მე ვიტყვი დააყენებს 50, ისევე როგორც ნომერი 50,
სადაც იქნებოდა თქვენ შესთავაზოს მე მიაპყროს იგი ამ მასივი?
არსებობს ხუთი სხვადასხვა შესაძლო პასუხი.
სად გსურთ დააყენებს ნომერი 50?
თუ მიზანი აქ, ისევ, მოვუწოდებთ ფუნქცია ბიძგი, კორიდორი არგუმენტი
50, სად მე ამას?
ხუთი შესაძლებლობის 20% შანსი გამოცნობა სწორად.
დიახ?
>> აუდიტორია: Far უფლება.
>> დინამიკები 1: Far უფლება.
აქ არის 25% შანსი გამოცნობა სწორად.
ასე რომ, ფაქტობრივად, იქნება ჯარიმა.
კონვენციის, მე ვიტყვი მასივი, ჩვენ ჩვეულებრივ იწყება მარცხენა,
მაგრამ ჩვენ ნამდვილად იწყება უფლება.
ასე რომ, სპოილერი აქ იქნება მე ალბათ აპირებს მიაპყროს ის მარცხენა,
უბრალოდ მინდა ნორმალური მასივი, სადაც მე დაიწყოს აპირებს მარცხნიდან მარჯვნივ.
მაგრამ თუ თქვენ შეგიძლიათ Flip არითმეტიკული, ჯარიმა.
ეს უბრალოდ არ არის ჩვეულებრივი.
OK, მე უნდა მიიღოს ერთი მეტი ცვლილება, თუმცა.
ახლა, მე მივიღებთ რაღაც გადატანა დასტის, რა არის შემდეგი?
>> ყველა უფლება მაქვს ნამატი ზომა.
ნება მომეცით წავიდეთ წინ და მხოლოდ განაახლოთ, რომელიც იყო ნულოვანი.
და ნაცვლად ახლა, მე ვაპირებ იმისათვის, რომ ღირებულება ერთი.
ახლა ვფიქრობ, დააყენებს სხვა ნომერი გადატანა დასტის, როგორც 51.
ისე, მე მაქვს კიდევ ერთი ცვლილება, რომელიც მდე ზომის ორი.
და მაშინ ვფიქრობ, დააყენებს კიდევ ერთი ნომერი გადატანა დასტის, როგორიცაა 61,
ახლა მე უნდა განახლდეს, ზომა ერთი დრო, და მიიღოს ღირებულება 3, ზომა.
და ახლა ვარაუდობენ, მოვუწოდებ პოპ.
ახლა პოპ, კონვენციის, არ იღებს არგუმენტი.
დასტის, მთელი წერტილი უჯრა მეტაფორა
არის, რომ თქვენ არ შეხედულებისამებრ წავიდეთ მისაღებად რომ პანელში, ყველა შეგიძლიათ გააკეთოთ
არის პოპ უმაღლეს ერთი დასტის, მხოლოდ იმიტომ.
სწორედ ამ მონაცემების სტრუქტურას აკეთებს.
>> ასე რომ, იმ ლოგიკით, თუ მე ამბობენ, pop, რა მოდის off?
ასე რომ, 61.
ასე რომ, რა არის კომპიუტერი ვაპირებთ მეხსიერება?
რას ჩემი კოდი უნდა გავაკეთოთ?
რას გვთავაზობთ შევცვლით ეკრანზე?
რა უნდა შეიცვალოს?
ბოდიში?
ასე რომ, ჩვენ დავაღწიოთ 61.
ასე რომ, შემიძლია ამის გაკეთება.
და შემიძლია მოშორება 61.
და მერე რა სხვა ცვლილება უნდა მოხდეს?
ზომა, ალბათ, უნდა დაბრუნდეს ორი.
და ისე, რომ ჯარიმა.
მაგრამ დაველოდოთ წუთში, ზომა მომენტში წინ იყო სამი.
მოდით უბრალოდ სწრაფი საღი აზრის ქვითარი.
როგორ მოხდა, რომ ჩვენ ვიცით, რომ სურდა, თავი დაეღწია 61?
იმის გამო, რომ ჩვენ popping.
ასე რომ, მე ამ მეორე ქონება ზომა.
>> ერთი წუთით, მე ფიქრი თავში კვირაში ორი
როდესაც ჩვენ დავიწყეთ ლაპარაკი კოლექტორები, სადაც ეს იყო ადგილმდებარეობა ნულოვანი,
ეს იყო ადგილმდებარეობა ერთი, ეს იყო ადგილმდებარეობა ორი, ეს არის ადგილმდებარეობა სამი, ოთხი,
როგორც ჩანს, შორის ურთიერთობა ზომა
და ელემენტი, რომელიც მინდა ამოიღონ საწყისი მასივი, როგორც ჩანს, უბრალოდ, თუ რა?
ზომა მინუს ერთი.
ასე რომ, ის, თუ როგორ, როგორც ადამიანები ჩვენ ვიცით, 61 მოდის პირველი.
როგორ არის კომპიუტერული აპირებს იცით?
როდესაც თქვენი კოდი, სადაც, სავარაუდოდ, მინდა ამის გაკეთება ზომა მინუს ერთი,
ასე რომ, სამი მინუს ერთი ორი, და რომ ნიშნავს, რომ ჩვენ გვინდა, რომ თავი დაეღწია 61.
და მაშინ ჩვენ შეიძლება მართლაც განახლება ზომა ისე, რომ ზომა ახლა
მიდის სამიდან მხოლოდ ორი.
და უბრალოდ უნდა იყოს pedantic, მე ვაპირებ იმის მტკიცება, რომ მე გაკეთდეს, არა?
თქვენ შემოთავაზებული ინტუიციურად სწორად მე უნდა მოისპოს 61.
მაგრამ არ I ტიპის ერთგვარი მიღებული მოშორება 61?
მე ეფექტურად დავიწყებული ის, რომ ფაქტობრივად არ არსებობს.
და ვფიქრობ, უკან Pset4, თუ თქვენ წაიკითხავთ სტატია ექსპერტიზის, PDF
რომ ჩვენ გვქონდა თქვენ ბიჭები წაიკითხოს, ან თქვენ წაიკითხავს ამ კვირაში Pset4.
შეგახსენებთ, რომ ეს არის რეალურად გერმანე მთელი იდეა კომპიუტერული სასამართლო.
რა კომპიუტერი საერთოდ არის ეს უბრალოდ ავიწყდება სად არის რაღაც,
მაგრამ ეს არ წავიდეს და როგორც ცდილობენ ნულიდან ის ან override
იმ ბიტი zeros და პირობა ან სხვა შემთხვევითი ნიმუში
თუ თქვენ თავს ამის გაკეთება შეგნებულად.
ასე რომ, თქვენი ინტუიცია იყო უფლება, მოდით, თავი დაეღწია 61.
მაგრამ სინამდვილეში, ჩვენ არ უნდა გადაიტვირთოთ.
ჩვენ უბრალოდ უნდა დაგვავიწყდეს, რომ ეს არ იცვლება ჩვენი ზომა.
>> ახლა არის პრობლემა ამ დასტის.
თუ მე შენარჩუნება უბიძგებს რამ გადატანა დასტის, რა არის
აშკარად მოხდება მხოლოდ რამდენიმე მომენტი დროს?
ჩვენ ვაპირებთ, რომ ამოიწურა სივრცეში.
და რა ვქნათ?
ჩვენ სახის ბრალია.
ეს განხორციელებას არ მისცეს ჩვენს შეცვლის მასივი, რადგან გამოყენებით
ეს სინტაქსი, თუ ვფიქრობ, უკან კვირაში ორი
ერთხელ თქვენ განაცხადა, ზომა მასივი,
ჩვენ არ მინახავს მექანიზმი, კიდევ სად თქვენ შეგიძლიათ შეცვალოთ ზომა მასივი.
და მართლაც C არ აქვს, რომ ფუნქცია.
თუ ამბობენ, მომეცი ხუთ Nths, მოვუწოდებთ მათ ნომრები,
რომ ყველა თქვენ აპირებს მიიღოს იგი.
ამიტომ, ჩვენ, ახლა, როგორც ორშაბათს, აქვს უნარი გამოხატოს გამოსავალი
მიუხედავად იმისა, რომ ჩვენ უბრალოდ უნდა tweak განსაზღვრება ჩვენი დასტის
არ უნდა იყოს გარკვეული მყარი კოდირებული მასივი, მაგრამ მხოლოდ შესანახად მისამართზე.
>> ახლა რატომ არის ეს?
ახლა ჩვენ უბრალოდ უნდა იყოს კომფორტული ის ფაქტი, რომ ჩემი პროგრამა გადის,
მე სავარაუდოდ აპირებს უნდა ვთხოვო ადამიანის,
რამდენი ნომრები გინდათ შესანახად?
ასე რომ შეყვანილი უნდა მოდიოდეს სადღაც.
მაგრამ ერთხელ მე ვიცი, რომ ნომერი, მაშინ მე შემიძლია უბრალოდ
გამოყენება რა ფუნქცია მისცეს ჩემთვის ბლოკი მეხსიერება?
მე შეიძლება გამოიყენოს malloc.
და შემიძლია ვთქვა, ნებისმიერი რაოდენობის bytes მინდა უკან ამ Nths.
და ყველა მე უნდა ჩაწეროთ ნომრები ცვლადი აქ, შიგნით ამ struct
უნდა იყოს თუ რა?
რეალურად რა გადადის ციფრები ამ შემთხვევაში?
ჰო, მომცეთ პირველი byte რომ ბლოკი მეხსიერება,
ან უფრო კონკრეტულად, მისამართი პირველი იმ ბაიტი.
არ აქვს მნიშვნელობა, თუ ეს არის ერთ-ერთი byte ან მილიარდი ბაიტი,
მე უბრალოდ უნდა ზრუნავდეს პირველი.
იმის გამო, რომ ის, რაც malloc გარანტიები და ჩემი ოპერაციული სისტემა გარანტიები,
ის არის, რომ ბლოკი მეხსიერება I მისაღებად, ეს იქნება მომიჯნავე.
იქ არ უნდა იყოს ხარვეზები.
ასე რომ, თუ მე ვთხოვე 50 bytes ან 1000 ბაიტი,
ისინი ყველა იქნება თავში დაბრუნება უკან.
ასე რომ, სანამ მე მახსოვს, როგორ დიდი, როგორ ბევრი მოვითხოვე, ყველა მე უნდა იცოდეს
არის პირველი ასეთი მისამართზე.
>> ასე რომ, ახლა ჩვენ გვაქვს შესაძლებლობა, კოდი.
თუმცა, ის აპირებს us მეტი დრო დაწერა ეს ყველაფერი,
ჩვენ შეგვიძლია ახლა გამოდის, რომ მეხსიერების მხოლოდ შენახვის სხვადასხვა მისამართზე იქ
თუ ჩვენ გვინდა, უფრო დიდი ან თუნდაც პატარა ბლოკი მეხსიერება.
ასე რომ, აქ სავაჭრო off.
ახლა ჩვენ დინამიკას.
ჩვენ ჯერ კიდევ გვაქვს contiguousness მე აცხადებდნენ.
იმის გამო, რომ malloc მოგვცემს მომიჯნავე ბლოკი მეხსიერება.
მაგრამ ეს იქნება ტკივილი კისრის ჩვენთვის, პროგრამისტი,
რეალურად კოდი up.
ეს არის მხოლოდ უფრო მეტი მუშაობა.
ჩვენ გვჭირდება კოდი akin, რაც მე ბრახუნი, მხოლოდ ერთი წუთით წინ.
ძალიან doable, მაგრამ ეს დასძენს სირთულის.
ასე რომ, დეველოპერი დროს, პროგრამისტი დრო არის კიდევ ერთი რესურსი
რომ ჩვენ შეიძლება უნდა გაატარონ გარკვეული დრო, რათა მიიღოთ ახალი.
და მაშინ, რა თქმა უნდა, არსებობს რიგი.
ჩვენ არ წასვლას ერთი ბევრი დეტალი.
მაგრამ ეს ძალიან მსგავსი სულისკვეთება.
მე ვერ განახორციელოს რიგი, და შესაბამისი ოპერაციები,
enqueue და dequeue, მოსწონს დამატება ან წაშლა, ეს მხოლოდ fancier გზა რომ,
enqueue და dequeue, ასეთია.
შემიძლია უბრალოდ მივცეთ თავს struct რომ კიდევ ერთხელ აქვს მთელი რიგი მასივი,
რომ კიდევ ერთხელ აქვს ზომა, მაგრამ რატომ მე ახლა უნდა
შენარჩუნება სიმღერა წინაშე მდგომ?
მე არ უნდა იცოდეთ წინ ჩემი Stack.
ისე, თუ მე კიდევ ერთხელ მდგომ მოდით უბრალოდ მძიმე
კოდი იგი, როგორც მოსწონს ხუთ რიცხვებით აქ პოტენციურად.
ასე რომ, ეს არის ნულოვანი, ერთი, ორი, სამი, ოთხი.
ეს იქნება მოუწოდა ნომრები ერთხელ.
და ეს იქნება მოუწოდა ზომა.
>> რატომ არ არის საკმარისი აქვს მხოლოდ ზომა?
ისე, მოდით დააყენებს იმავე ნომრები.
ასე რომ, მე pushed-- მე enqueued, ან მივიღებთ.
ახლა მე enqueue 50, და შემდეგ 51 და შემდეგ 61 და dot dot dot.
ასე რომ, enqueue.
მე enqueued 50, მაშინ 51, მაშინ 61.
და რომ გამოიყურება იდენტურია დასტის დღემდე,
გარდა მე უნდა მიიღოს ერთი ცვლილება.
მე უნდა განახლდეს, ეს ზომა, ასე რომ მე წასვლა ნულიდან ერთი ორი სამი ახლა.
როგორ შემიძლია dequeue?
რა ხდება dequeue?
ვინ უნდა მოვიდეს off ამ სიაში პირველი თუ ეს ხაზი Apple Store?
ასე რომ, 50.
ასე რომ, ეს სახის რთული სიტუაციაა ამ დროს.
ვინაიდან ბოლო დროს ეს იყო სუპერ ადვილი უბრალოდ ზომა მინუს ერთი,
მე კიდევ ბოლომდე ჩემი მასივი ეფექტურად სადაც ნომრები, ის შლის 61.
მაგრამ მე არ მინდა ამოიღონ 61.
მე მინდა, რომ 50, რომელიც იქ იყო 5:00 AM
რომ გამოდიან ახალი iPhone ან whatnot.
ასე რომ, თავი დაეღწია 50, მე არ შეუძლიათ უბრალოდ ამის გაკეთება, არა?
შემიძლია გადაკვეთა 50.
მაგრამ ჩვენ უბრალოდ განაცხადა ჩვენ არ უნდა იყოს ასე anal
როგორც ნულიდან ან დამალვა მონაცემები.
ჩვენ შეგვიძლია მხოლოდ დაგვავიწყდეს, სადაც ის არის.
>> მაგრამ თუ შევცვალო ჩემი ზომა ახლა ორი, ეს საკმარისი ინფორმაცია
ვიცი, რა ხდება ჩემი მდგომ?
ნამდვილად არა.
როგორც ჩემი ზომა არის ორი, მაგრამ სად მდგომ დაიწყოს,
მით უმეტეს, თუ კიდევ მაქვს იმავე ნომრები მეხსიერება.
50, 51, 61.
ასე რომ, მე უნდა გვახსოვდეს ახლა, სადაც წინა.
ასე რომ, მე შევთავაზე up იქ, ჩვენ არ მხოლოდ ე.წ.
Nth წინ, რომლის საწყის მნიშვნელობა უნდა ყოფილიყო, თუ რა?
Zero, მხოლოდ დასაწყისია სიაში.
მაგრამ ახლა გარდა decrementing ზომა, ჩვენ უბრალოდ ნამატი წინ.
ახლა აქ არის კიდევ ერთი პრობლემა.
ასე რომ, კიდევ მე შენარჩუნება აპირებს.
დავუშვათ, რომ ეს არის ნომერი მოსწონს 121, 124, და შემდეგ, dammit,
მე გარეთ სივრცეში.
მაგრამ დაველოდოთ წუთში, მე არ ვარ.
ამრიგად, ამ ეტაპზე იმ ამბავს, ვარაუდობენ, რომ ზომა არის ერთი, ორი,
სამი, ოთხი, ამიტომ ვარაუდობენ, რომ ზომა არის ოთხი, წინა ერთი,
ასე რომ, 51 წინ.
მინდა, რომ მეორე ნომერი აქ, მაგრამ, dammit, მე გარეთ სივრცეში.
მაგრამ მე არ ვარ ნამდვილად, არა?
სად დააყენა რამდენიმე დამატებითი ღირებულების, ისევე როგორც 171?
ჰო, მე შეიძლება მხოლოდ სახის დაბრუნდეს იქ, არა?
და მაშინ გადაკვეთა 50, ან მხოლოდ გადაწერა იგი 171.
და თუ თქვენ გაინტერესებთ, რატომ ჩვენი ნომრები ისე შემთხვევითი,
ეს საყოველთაოდ მიღებული კომპიუტერული მეცნიერებათა კურსები ჰარვარდის შემდეგ CS50.
მაგრამ ეს იყო კარგი ოპტიმიზაცია, რადგან ახლა მე არ გაყვანაა სივრცეში.
მე მაინც უნდა გვახსოვდეს რამდენად დიდი ეს რამ არის საერთო.
ეს ხუთი შეადგენს.
იმიტომ, რომ მე არ მინდა, რომ დავიწყო overwriting 51.
ასე რომ, ახლა მე ჯერ კიდევ გარეთ სივრცეში, ასე რომ, იგივე პრობლემა, როგორც ადრე.
მაგრამ თქვენ ხედავთ, როგორ ახლა თქვენი კოდი, ალბათ,
უნდა დაწეროს ცოტა მეტი სირთულის, რომ მოხდეს.
და სინამდვილეში, რა ოპერატორი in C ალბათ საშუალებას
თქვენ magically ამისათვის circularity?
ჰო modulo ოპერატორი, პროცენტი ნიშანი.
ასე რომ, რა სახის მაგარი მდგომ, მიუხედავად იმისა, რომ ჩვენ შევინარჩუნოთ ხატვის კოლექტორები
როგორც ეს, როგორც სწორი ხაზები, თუ სახის ვიფიქროთ, რომ ეს curving
გარშემო წრე, მაშინ მხოლოდ ინტუიციურად ეს ერთგვარი მუშაობს გონებრივად
მე ვფიქრობ, რომ ცოტა მეტი cleanly.
თქვენ მაინც უნდა განახორციელოს რომ ფსიქიკური მოდელის კოდი.
ასე რომ, არ არის რთული, საბოლოო ჯამში, განხორციელება,
მაგრამ ჩვენ მაინც დაკარგავს ზომა უფრო სწორად, უნარი ზომის შეცვლა, თუ ჩვენ ამის გაკეთება.
>> ჩვენ უნდა დავაღწიოთ მასივი, ჩვენ შეცვალოს იგი ერთი მაჩვენებელი,
და მერე სადღაც ჩემი კოდი მაქვს გამოძახების რა ფუნქცია რეალურად შექმნა
მასივი მოუწოდა ნომრები?
Malloc, ან რაღაც მსგავსი ფუნქცია, ზუსტად.
ნებისმიერი კითხვები stacks და რიგები.
ჰო?
კარგი კითხვაა.
რა modulo თქვენ იყენებთ აქ.
ასე რომ, ზოგადად, როდესაც გამოყენებით mod, თქვენ ამის გაკეთება
ერთად ზომა მთელი მონაცემები სტრუქტურა.
ასე რომ რაღაც ხუთი ან მოცულობა, თუ ეს მუდმივი, ალბათ ჩართული.
მაგრამ მხოლოდ ამით modulo ხუთ ალბათ, არ არის საკმარისი,
იმიტომ, რომ ჩვენ უნდა ვიცოდეთ, რომ ჩვენ გადაიტანოთ გარშემო აქ ან აქ ან აქ.
ასე რომ, თქვენ, ალბათ, ასევე აპირებს მინდა ჩართვა
ზომა რამ, ან წინა ცვლადი ასევე.
ასე რომ, ეს მხოლოდ ამ შედარებით მარტივი არითმეტიკული გამოხატვის,
მაგრამ modulo იქნება ძირითადი ნივთიერება.
>> ასე მოკლე ფილმი თუ გნებავთ.
ანიმაცია, რომ ზოგიერთი ეგ სხვა უნივერსიტეტში
ერთად რომ ჩვენ ადაპტირებული ამ დისკუსიაში.
იგი მოიცავს ჯეკ სასწავლო ფაქტები რიგები და სტატისტიკა.
>> ფილმი: ერთხელ, იყო ბიჭი სახელად ჯეკ.
როდესაც საქმე მიღების მეგობრები, Jack არ აქვს knack.
ასე რომ, ჯეკ წავიდა გაიგო ყველაზე პოპულარული ბიჭი იცოდა.
წავიდა Lou და სთხოვა, რა გავაკეთო?
Lou დაინახა, რომ მის მეგობარს ნამდვილად შეწუხდა.
ისე, მან დაიწყო, უბრალოდ, შევხედოთ, თუ როგორ თქვენ ჩაცმული.
ნუ თქვენ გაქვთ რაიმე ტანსაცმელი სხვადასხვა სახეს?
დიახ, განაცხადა ჯეკ.
მე დარწმუნებული ვარ, ამის გაკეთება.
მოვიდა ჩემს სახლში და მე გაჩვენებთ მათ თქვენ.
ასე რომ, ისინი წავიდნენ ჯეკ.
და ჯეკ აჩვენა Lou ყუთი სადაც იგი ინახება ყველა მისი მაისური,
და მისი შარვალი და მისი წინდები.
Lou განაცხადა, მე ვხედავ, თქვენ უნდა ყველა თქვენი ტანსაცმელი წყობის.
რატომ არ აცვიათ გარკვეული სხვები ერთხელ awhile?
>> ჯეკ განაცხადა, ასევე, როდესაც მე ამოიღონ ტანსაცმელი და წინდები,
მე დაიბანეთ მათ და ამით მათ მოშორებით ყუთში.
შემდეგ მოდის შემდეგი დილით, და მე hop.
მე წასვლა ყუთი და მიიღეთ ჩემი ტანსაცმელი off დაბრუნება.
Lou სწრაფად მიხვდა, პრობლემა ჯეკ.
მან გადაარჩინა ტანსაცმელი, CD- ს, და წიგნები Stack.
როდესაც მან მიაღწია რაღაც იკითხება ან აცვიათ,
ის მინდა აირჩიოს საუკეთესო წიგნი ან საცვლების.
მაშინ, როდესაც ის იყო, მან მისთვის უფლება უკან.
უკან ის წავიდოდა, თავზე Stack.
მე ვიცი გამოსავალი, განაცხადა ტრიუმფალური Loud.
თქვენ უნდა ვისწავლოთ დაიწყოს გამოყენებით რიგი.
Lou მიიღო ჯეკ ტანსაცმელი და ეკიდა მათ კარადა.
და როდესაც მან დაიცალა ყუთი, ის უბრალოდ არ გაიზიარა იგი.
>> ამის შემდეგ მან განაცხადა, ახლა ჯეკ, ბოლოს დღეს, თქვენს ტანსაცმელი მარცხენა
როცა ისინი მოშორებით.
მაშინ ხვალ დილით, როდესაც თქვენ ვხედავ sunshine, თქვენი ტანსაცმელი
მარჯვენა ბოლოს ხაზი.
არ ხედავთ? განაცხადა Lou.
ეს იქნება ასე ლამაზი.
თქვენ აცვიათ ყველაფერი ერთხელ სანამ აცვიათ რაღაც ორჯერ.
და ყველაფერი რიგები მისი კარადა და თარო,
ჯეკ დაიწყო გრძნობს დანამდვილებით თავს.
ყველა წყალობით Lou და მისი მშვენიერი რიგიდან.
დინამიკები 1: ყველა უფლება, ეს adorable.
ასე რომ, რაც უკვე მართლაც აპირებს ქვეშ hood ახლა?
რომ ჩვენ გვაქვს პოინტერები, რომ ჩვენ გვაქვს malloc,
რომ ჩვენ გვაქვს შესაძლებლობა, რომ შევქმნათ მოცულობით მეხსიერება საკუთარ თავს
დინამიურად ვითარდება.
ასე რომ, ეს არის სურათი ჩვენ glimpsed მხოლოდ მეორე დღეს.
ჩვენ ნამდვილად არ არენაზე მასზე, მაგრამ ეს სურათი
უკვე მიმდინარეობს ქვეშ კაპოტის for კვირაა.
ასე რომ, ეს წარმოადგენს, უბრალოდ მართკუთხედი, რომ ჩვენ შედგენილი,
თქვენი კომპიუტერის მეხსიერებაში.
და, შესაძლოა, თქვენს კომპიუტერში, ან CS50 ID, აქვს Gigabyte მეხსიერების ან RAM
ან ორი გიგაბაიტი ან ოთხ.
ეს ნამდვილად არ აქვს.
თქვენი ოპერაციული სისტემა Windows და Mac OS და Linux,
არსებითად საშუალებას თქვენი პროგრამა ვფიქრობ, რომ მას აქვს დაშვება
რომ მთლიანად თქვენი კომპიუტერის მეხსიერების,
მიუხედავად იმისა, რომ თქვენ შეიძლება იყოს გაშვებული სხვადასხვა პროგრამები ერთდროულად.
ასე რომ, რეალურად, რომ ნამდვილად არ იმუშავებს.
მაგრამ ეს ერთგვარი ილუზია, მოცემული ყველა თქვენი პროგრამები.
ასე რომ, თუ თქვენ ორი gigs of RAM, ამ არის, თუ როგორ კომპიუტერი შეიძლება ვიფიქროთ, რომ ეს.
>> ახლა ერთსა, ერთ-ერთი ასეთი რამ, ერთი ამ სეგმენტების მეხსიერება,
ეწოდება Stack.
და მართლაც, ნებისმიერ დროს დღემდე წერილობით კოდი
რომ თქვენ არ მოუწოდა ფუნქცია, მაგალითად მთავარი.
შეგახსენებთ, რომ ნებისმიერ დროს მე შედგენილი კომპიუტერის მეხსიერებაში,
მე ყოველთვის მიაპყროს სახის ნახევარი მართკუთხედი აქ
და არ გადაიტვირთოთ საუბარი რა არის ზემოთ.
იმის გამო, რომ მაშინ, როდესაც მთავარი ჰქვია, მე პრეტენზია რომ თქვენ ამ კუთხეში მეხსიერება
რომ მიდის ქვემოთ აქ.
და თუ მთავარი მოუწოდა ფუნქცია ისევე როგორც swap, ასევე swap მიდის აქ.
და აღმოჩნდება, რომ სადაც ის დამთავრებული.
რაღაც მოუწოდა დასტის შიგნით თქვენი კომპიუტერის მეხსიერებაში.
ახლა დასასრულს დღეს, ეს არის მხოლოდ მიმართავს.
ეს იგივეა, byte ნულოვანი, byte ერთი, byte 2 მლრდ.
მაგრამ თუ ფიქრობთ, რომ ეს როგორც ამ მართკუთხა ობიექტი,
ყველა ვაკეთებთ ყოველ ჩვენ მოვუწოდებთ ფუნქცია
layering ახალი ნაჭერი მეხსიერება.
ჩვენ ვაძლევთ, რომ ფუნქცია ნაჭერი საკუთარი მეხსიერება მუშაობა.
>> და გავიხსენოთ, ახლა, რომ ეს არის მნიშვნელოვანი.
იმიტომ, რომ თუ ჩვენ გვაქვს რაღაც swap
და ორი ადგილობრივი ცვლადები, როგორიც A, B და ჩვენ შეცვლის იმ ღირებულებებს, ერთი და ორი
ორი და ერთი, გავიხსენოთ რომ როდესაც swap ბრუნდება,
ეს თითქოს ამ ნაჭერი მეხსიერების უბრალოდ გაქრა.
სინამდვილეში, ეს ჯერ კიდევ არ forensically.
და რაღაც მაინც რეალურად არსებობს.
მაგრამ კონცეპტუალურად, ეს როგორც მიუხედავად იმისა, რომ ის მთლიანად გაქრა.
ასე რომ, მთავარი არ ვიცი არც ერთი სამუშაო რომ გაკეთდა, რომ swap ფუნქციის,
თუ ეს რეალურად გაიარა იმ არგუმენტები მაჩვენებელი ან მითითებით.
ახლა, ფუნდამენტური გადაწყვეტა რომ პრობლემა swap
გადის რამ by მისამართზე.
მაგრამ აღმოჩნდება, ძალიან, რა არის უკვე მიმდინარეობს, რომ ზემოთ ნაწილი
მართკუთხედის ყველა ამ დროს ჯერ არ არის მეტი მეხსიერების არსებობს.
და როცა დინამიურად გამოყოს მეხსიერება,
არის თუ არა ეს შიგნით GetString, რომელიც ჩვენ ვაკეთებთ თქვენთვის CS50
ბიბლიოთეკა, ან, თუ ბიჭები მოვუწოდებთ malloc და ვთხოვ
ოპერაციული სისტემა ბლოკი მეხსიერება, ეს არ მოდის Stack.
მას გააჩნია სხვა ადგილას თქვენი კომპიუტერის მეხსიერების
რომ მოუწოდა ბევრი.
და ეს არ არის რაიმე განსხვავებული.
ეს იგივეა, რაც მეხსიერება.
უბრალოდ RAM რომ მდე იქ ნაცვლად ქვემოთ აქ.
>> ასე რომ, რას ნიშნავს ეს?
ისე, თუ თქვენი კომპიუტერი სასრული რაოდენობით მეხსიერება
და დასტის იზრდებოდა, ასე რომ ვთქვათ, და ბევრი, შესაბამისად
ამ arrow, იზრდება down.
სხვა სიტყვებით, ყოველ მოვუწოდებთ malloc,
თქვენ უტარდება ნაჭერი მეხსიერების ზემოდან,
მაშინ იქნებ ცოტა დაბალია, მაშინ პატარა ქვედა, ყოველ ჯერზე რეკავთ malloc,
ბევრი, მისი გამოყენება, არის სახის იზრდება,
უფრო და უფრო უახლოვდება, თუ რა?
დასტის.
ასე რომ, ჯერ ეს, როგორც ჩანს, კარგი იდეა?
ვგულისხმობ, სადაც ეს ნამდვილად არ არის ნათელი რა შეგიძლიათ გააკეთოთ, თუ თქვენ მხოლოდ
აქვს სასრული რაოდენობით მეხსიერება.
მაგრამ ეს არ არის აუცილებლად ცუდი.
ეს ორი ისრებით წლის ავარიის რა თქმა უნდა, ერთმანეთს.
>> და აღმოჩნდება, რომ ცუდი ბიჭი, დაკარგულია განსაკუთრებით კარგი პროგრამირების,
და ცდილობენ hack კომპიუტერები, შეიძლება გამოეყენებინათ ეს რეალობა.
ფაქტობრივად, განვიხილოთ პატარა მონაკვეთში.
ასე რომ, ეს არის მაგალითი შეგიძლიათ წაიკითხოთ შესახებ უფრო დეტალურად ვიკიპედიაში.
ჩვენ აღვნიშნო, რომ თქვენ დროს სტატია თუ აინტერესებს.
მაგრამ არსებობს თავდასხმის ზოგადად ცნობილია, როგორც ბუფერული overflow რომ
არსებობდა, რადგან ადამიანები არ ჰქონდა უნარი მანიპულირება
კომპიუტერის მეხსიერებაში, განსაკუთრებით C. ასე რომ, ეს არის ძალიან თვითნებური პროგრამა,
მაგრამ მოდით წაიკითხავს ბოლოში მდე.
მთავარი შევიდა Argc char ვარსკვლავი argv.
ასე რომ, ეს პროგრამა, რომელიც იღებს ბრძანების ხაზი არგუმენტები.
და ყველა ძირითადი -ს, როგორც ჩანს, დარეკეთ ფუნქცია, მას F სიმარტივის.
და ეს გადის რა?
Argv ერთი.
ასე გადის F რასაც სიტყვა, რომელიც მომხმარებლის აკრეფილი
ზოლზე შემდეგ პროგრამის სახელწოდება ყველა.
ასე რომ ჰგავს Caesar ან Vigenere, რომელიც თქვენ ალბათ გახსოვთ აკეთებს argv.
>> რა არის F?
F იღებს სიმებიანი როგორც მისი ერთადერთი არგუმენტი,
AKA char ვარსკვლავი, იგივე რამ, როგორც სიმებიანი.
და ეს ე.წ. თვითნებურად ბარი ამ მაგალითს.
და მაშინ char c 12 მხოლოდ ერისკაცად წარმოგვიდგება მისი თვალსაზრისით,
რა არის char გ bracket 12 აკეთებენ?
რა გავაკეთოთ?
გამოყოფის მეხსიერება, კონკრეტულად 12 ბაიტი, 12 სიმბოლო.
ზუსტად.
და შემდეგ ბოლო ხაზი, აურიეთ და ასლი, თქვენ ალბათ არ მინახავს.
ეს არის ტექსტი ასლი ფუნქცია, რომლის მიზანი ცხოვრებაში
კოპირება მეორე არგუმენტი მისი პირველი არგუმენტი,
მაგრამ მხოლოდ ერთი გარკვეული რაოდენობის ბაიტი.
ასე რომ, მესამე არგუმენტი ამბობს, რამდენი ბაიტი უნდა ასლი?
ხანგრძლივობა ბარი, რასაც მომხმარებლის აკრეფილი.
და შინაარსი ბარი, რომ ტექსტი, არიან
გადაწერა ხსოვნას აღნიშნა ზე C.
>> ასე რომ, ეს, როგორც ჩანს, ასეთი სულელური, და ეს არის.
ეს არის contrived მაგალითად, მაგრამ ის წარმომადგენელი
კლასის თავდასხმის ვექტორები, გზა თავდასხმაში პროგრამა.
ყველა კარგად არის და კარგი, თუ მომხმარებელი სახის სიტყვა, რომელიც არის 11 პერსონაჟი
ან ნაკლები, ასევე წარმატებული ნულოვანი.
რა მოხდება, თუ მომხმარებლის ტიპების მეტი ვიდრე 11 ან 12 ან 20 ან 50 სიმბოლო?
რა არის ამ პროგრამის აპირებს?
პოტენციურად seg ბრალია. ის აპირებს ბრმად კოპირება ყველაფერი ბარი
მისი სიგრძე, რომელიც არის ფაქტიურად ყველაფერი ბარი,
შევიდა მისამართი მიუთითა C. მაგრამ C მხოლოდ წინასწარ მოცემული, როგორც 12 ბაიტი.
მაგრამ არ არსებობს დამატებითი ქვითარი.
იქ არ არის, თუ პირობები.
არ არსებობს შეცდომა შემოწმების აქ.
>> ასე რომ, რა არის, ეს პროგრამა ვაპირებ ამის გაკეთებას, უბრალოდ ბრმად
ასლი ერთი რამ სხვა.
ასე რომ, თუ ჩვენ გავამახვილო ეს როგორც სურათზე, აქ
უბრალოდ კუთხეში მეხსიერების სივრცე.
ასე რომ შეამჩნია ბოლოში, ჩვენ აქვს ადგილობრივი ცვლადი ბარი.
ასე რომ კურსორი, რომელიც აპირებს store-- უფრო სწორად, რომ ადგილობრივი არგუმენტი რომ
აპირებს შესანახად სიმებიანი ბარი.
და მაშინ შეამჩნია მხოლოდ ზემოთ ის დასტის,
რადგან ყოველ ჯერზე თქვენ ვთხოვო მეხსიერების დასტის,
ის მიდის ცოტა ზემოთ ის ილუსტრირებული,
ცნობა, რომ ჩვენ მივიღეთ 12 ბაიტი არსებობს.
ზედა მარცხენა ერთი C bracket ნულოვანი და ქვედა მარჯვენა ერთი არის C bracket 11.
ეს არის ის, თუ რამდენად კომპიუტერები ჩაუყარა ის.
ასე რომ მხოლოდ ინტუიციურად, თუ ბარი აქვს მეტი ვიდრე 12 სიმბოლო სულ, მათ შორის,
წარმატებული ნულოვანი, სადაც არის 12 ან C bracket 12 აპირებს?
უფრო სწორად, სადაც არის 12 ხასიათი და მე -13 ხასიათი,
მეასედ ხასიათი აპირებს უნდა დამთავრდეს ამ სურათზე?
ზემოთ ან ქვემოთ?
>> მარჯვენა, რადგან მიუხედავად იმისა, რომ დასტის თავად იზრდება წლიდან მოყოლებული,
ერთხელ თქვენ დააყენა პერსონალი ის, რომ ეს დიზაინი მიზეზების გამო,
აყენებს მეხსიერების ზემოდან.
ასე რომ, თუ თქვენ მოხვდით მეტი ვიდრე 12 ბაიტი, თქვენ აპირებს დაიწყოს გადაწერა ბარი.
ახლა რომ შეცდომაა, მაგრამ ეს ნამდვილად არ არის დიდი გარიგება.
მაგრამ ეს არის დიდი გარიგება, რადგან იქ უფრო პერსონალის მიმდინარეობს მეხსიერებაში.
ასე რომ, აქ როგორ შეიძლება ბოლო hello, უნდა იყოს ნათელი.
თუ მე აკრეფილი მიესალმები ზოლზე.
H-E-L-L-O წარმატებული ნულოვანი, მთავრდება ფარგლებში იმ 12 ბაიტი, და ჩვენ სუპერ უსაფრთხო.
ყველაფერი კარგად არის.
მაგრამ თუ მე აკრიფოთ რაღაც აღარ, პოტენციურად ეს
აპირებს შემოგეპაროთ შევიდა ბარი სივრცეში.
მაგრამ უარესი არ არის, თურმე ყველა ამ დროს,
მიუხედავად იმისა, რომ ჩვენ არასდროს არ ისაუბრა ის, დასტის გამოიყენება სხვა პერსონალი.
ეს არ არის მხოლოდ ადგილობრივი ცვლადები.
>> C არის ძალიან დაბალი დონე ენაზე.
და ეს ერთგვარი ფარულად იყენებს დასტის ასევე
უნდა გვახსოვდეს, როდესაც ფუნქცია ეწოდება, რა
მისამართი არის წინა ფუნქცია, ასე რომ მას შეუძლია ხტომა უკან რომ ფუნქცია.
ასე რომ, როდესაც მთავარ მოუწოდებს სვოპ, მათ შორის რამ აიძულა გადატანა დასტის
არ არის მხოლოდ სვოპების ადგილობრივი ცვლადები, ან მისი არგუმენტები, ასევე ფარულად მივიღებთ
გადატანა დასტის წარმოდგენილი წითელი ნაჭერი აქ,
არის მისამართი მთავარი ფიზიკურად თქვენს კომპიუტერის მეხსიერებაში,
ასე რომ, როდესაც swap კეთდება, კომპიუტერი იცის, რომ მე უნდა დაბრუნდეს მთავარი
და დასრულდება შესრულებაში მთავარი ფუნქცია.
ასე რომ, ეს საშიშია, ახლა, იმიტომ, რომ თუ მომხმარებლის ტიპის კარგად ზე მეტი hello,
ისეთი, რომ მომხმარებლის შეყვანის clobbers ან overwrites, რომ წითელი განყოფილებიანი,
ლოგიკურად თუ კომპიუტერის მხოლოდ აპირებს ბრმად ვივარაუდოთ,
რომ bytes, რომ წითელი ნაჭერი არის მიმართვაში, რომელიც მას უნდა დაუბრუნდეს,
რა მოხდება, თუ მოწინააღმდეგე არის ჭკვიანი საკმარისი და იღბლიანი საკმარისი იმისათვის, რომ თანმიმდევრობა bytes
იქ რომ ჰგავს მისამართი, მაგრამ ეს მისამართი კოდი
რომ მას სურს კომპიუტერული შეასრულოს ნაცვლად მთავარი?
>> სხვა სიტყვებით, თუ რა მომხმარებლის აკრეფის დროს სწრაფი,
არ არის რაღაც უწყინარი, როგორც hello,
მაგრამ სინამდვილეში კოდი, რომელიც ექვივალენტურია წაშლა ყველა ამ მომხმარებლის ფაილი?
ან ელ მათი დაგავიწყდათ ჩემთვის?
ან დაიწყოს ხე მათი keystrokes, არა?
არის გზა, მოდით ითვალისწინებს, დღეს, რომ მათ შეეძლოთ ჩაწერეთ არა მხოლოდ მიესალმები
მსოფლიოში და მათი სახელი, მათ შეეძლოთ არსებითად
გაივლის კოდი, zeros და პირობა, რომ კომპიუტერი
შეცდომები ორივე კოდი და მისამართი.
ასე რომ, თუმცა გარკვეულწილად აბსტრაქტულად, თუ მომხმარებლის სახის საკმარისი შეჯიბრებითობის კოდი
ის, რომ ჩვენ განზოგადება აქ, ა არის შეტევა და მოწინააღმდეგეებს.
ასე რომ, უბრალოდ ცუდი პერსონალი.
ჩვენ არ აინტერესებს ნომრები ან zeros და პირობა
დღეს, მაგალითად, რომ თქვენ დასრულდება მდე overwriting რომ წითელი განყოფილებიანი,
შეამჩნია, რომ თანმიმდევრობა bytes.
O 835 C ნულოვანი რვა ნულოვანი.
და ახლა, როგორც ვიკიპედიის სტატია აქ აქვს შემოთავაზებული, თუ ახლა რეალურად დაიწყოს
ეტიკეტირების bytes თქვენი კომპიუტერის მეხსიერება, თუ რა Wikipedia article არის
შემოთავაზების არის, რომ, თუ მისამართი რომ ზედა მარცხენა byte 80 C 0 3508.
>> სხვა სიტყვებით, თუ ცუდი ბიჭი არის ჭკვიანი საკმარისი მის კოდი
რეალურად დააყენოს ნომერი აქ შეესაბამება მისამართი კოდი
მას გაუკეთეს კომპიუტერი, თქვენ
შეგიძლიათ შეასრულა კომპიუტერული შევიდა აკეთებს არაფერი.
მოხსნის ფაილი, emailing რამ, შესასუნთქი თქვენი მოძრაობის,
ფაქტიურად არაფერი შეიძლება იყოს გაუკეთეს შევიდა კომპიუტერი.
ასე რომ ბუფერული overflow თავდასხმის დროს მისი ძირითადი
მხოლოდ სულელური, სულელური ძალიან მნიშვნელოვანი მასივი, რომ
არ აქვს საზღვრები გადამოწმებული.
და ეს არის ის, რაც სუპერ სახიფათო და ერთდროულად სუპერ ძლიერი
C არის, რომ ჩვენ მართლაც აქვს ხელმისაწვდომობის სადმე მეხსიერება.
ეს ჩვენთვის, პროგრამისტების, ვინც დაწერა ორიგინალური კოდი
უნდა შეამოწმოს darn სიგრძე ნებისმიერი კოლექტორები, რომ ჩვენ მანიპულირება.
ასე უნდა იყოს მკაფიო, რა გადავწყვიტოთ?
თუ ჩვენ გააფართოვოს უკან ამ კოდი, მე არ უნდა უბრალოდ
შეცვლის სიგრძეზე ბარი, რა სხვა უნდა იყოს შემოწმება?
რა უნდა მე უნდა აკეთებს თავიდან ავიცილოთ ეს თავდასხმა მთლიანად?
მე არ მინდა, რომ უბრალოდ ბრმად ამბობენ რომ თქვენ უნდა დააკოპირეთ როგორც ბევრი bytes
როგორც არის სიგრძეზე ბარი.
მე მინდა ვთქვა, კოპირება ბევრი bytes როგორც არის ბარი
მდე გამოყოფილი მეხსიერება, ან 12 მაქსიმალურად.
ასე რომ, მე უნდა გარკვეული თუ მდგომარეობა რომ არ შეამოწმოს სიგრძეზე ბარი,
მაგრამ თუ იგი აღემატება 12, ჩვენ მხოლოდ მძიმე კოდი 12 მაქსიმალური მანძილი.
წინააღმდეგ შემთხვევაში, ე.წ. ბუფერულ overflow თავდასხმა შეიძლება მოხდეს.
ბოლოში იმ სლაიდები, თუ თქვენ საინტერესო ვრცლად
ფაქტობრივი ორიგინალური სტატია თუ გსურთ შევხედოთ.
>> მაგრამ ახლა, მათ შორის ფასები გადახდილი აქ იყო არაეფექტური.
ასე რომ, სწრაფი დაბალი დონე შევხედოთ რა
პრობლემები შეიძლება წარმოიშვას, რომ ჩვენ გვაქვს წვდომა კომპიუტერის მეხსიერებაში.
მაგრამ კიდევ ერთი პრობლემა, უკვე stumbled on ორშაბათი
იყო მხოლოდ არაეფექტურობა უკავშირდება სიაში.
ჩვენ უკან ხაზოვანი დრო.
ჩვენ უკვე აღარ გვაქვს მომიჯნავე მასივი.
ჩვენ არ გვაქვს წვდომის.
ჩვენ არ შეგვიძლია გამოვიყენოთ კვადრატული ფრჩხილი ნოტაცია.
ჩვენ ფაქტიურად თავიდან უნდა გამოიყენოთ ხოლო მარყუჟის როგორც დავწერე მომენტში წინ.
მაგრამ ორშაბათს, ჩვენ ამტკიცებდა, რომ ჩვენ შეგვიძლია Creep ისევ სფეროში ეფექტურობის
მისაღწევად, რომ რაღაც ლოგარითმული იქნებ, ან საუკეთესო არ არის,
შესაძლოა, რომ რაღაც ე.წ. მუდმივი დრო.
მაშ, როგორ შეგვიძლია გავაკეთოთ, რომ გამოყენებით ამ ახალი იარაღები, ამ მისამართები, ამ მითითებას,
და threading რამ ჩვენი საკუთარი?
ისე, ვფიქრობ, რომ აქ, ეს არის bunch
ციფრები, რომ ჩვენ გვინდა, რომ მაღაზიის მონაცემები სტრუქტურა და ძებნის ეფექტურად.
ჩვენ შეგვიძლია სრულიად გადახვევა კვირაში ორი, იმისათვის, რომ ამ მასივი,
და ძებნის მათი გამოყენებით ორობითი ძებნა.
დაყავი და იბატონე.
და სინამდვილეში, თქვენ დაწერა ბინარული ძებნის pset3,
სადაც თქვენ განხორციელებული იპოვოს პროგრამა.
მაგრამ იცით, რა.
აქ არის ერთგვარი უფრო ჭკვიანი გზა ამით.
ეს ცოტა მეტი დახვეწილი და ეს, ალბათ,
საშუალებას გვაძლევს, თუ რატომ ორობითი ძიება იმდენად სწრაფად.
პირველ რიგში, მოდით გააცნობს ცნება ხე.
რომელი მიუხედავად იმისა, რომ რეალობა ხეები სახის
იზრდება, როგორც ეს, მსოფლიოში კომპიუტერული მეცნიერება ისინი სახის იზრდება ქვევით
მოსწონს ოჯახის ხე, სადაც თქვენ უნდა თქვენი ბებია ან დიდი ბებია და ბაბუა
ან whatnot ზედა, პატრიარქს და matriarch ოჯახის, მხოლოდ ერთი
ე.წ. root, კვანძის, ქვემოთ რომლებიც მისი შვილი,
ქვემოთ რაც არის მისი შვილი, ან მისი შთამომავლები უფრო ზოგადად.
და ყველას ჩამოკიდებული off ბოლოში ოჯახის
ხე, გარდა იმისა, რომ ახალგაზრდა ოჯახში,
ასევე შეგიძლიათ უბრალოდ იყოს generically ეწოდება ფოთლები ხე.
>> ასე რომ, ეს მხოლოდ რამოდენიმე სიტყვა და განმარტებები
რაღაც მოუწოდა ხე კომპიუტერული მეცნიერების, ჰგავს ოჯახის ხე.
მაგრამ არსებობს fancier ინკარნაციაში ხეები, რომელთაგან ერთ-ერთი
ეწოდება ორობითი ძებნა ხე.
და შეგიძლიათ სახის გაღიზიანება გარდა რა ეს რამ აქვს.
ისე, ეს ორობითი რა გაგებით?
სად ორობითი მოდის აქ?
ბოდიში?
ეს არ არის იმდენად ან ან.
ეს უფრო, რომ თითოეული კვანძების ვიზიტორების მეტი ორი შვილი, როგორც ვხედავთ, აქ.
ზოგადად, ხე და თქვენი მშობლები და ბებია
შეგიძლიათ იმდენი ბავშვები ან შვილიშვილებს, რადგან ისინი რეალურად გვინდა,
და ასე მაგალითად, ჩვენ გვაქვს სამი ბავშვებს, რომ მარჯვენა ხელის კვანძი,
მაგრამ ორობითი ხე, კვანძის აქვს ნულოვანი, ერთი, ან ორი შვილი მაქსიმალურად.
და ეს ლამაზი ქონება, იმიტომ, რომ თუ ის capped მიერ ორი,
ჩვენ ვაპირებთ, რომ შეძლებს კიდევ ცოტა ჟურნალი ბაზა ორი
მოქმედება ხდება აქ საბოლოოდ.
ასე რომ, ჩვენ გვაქვს რაღაც ლოგარითმული.
მაგრამ უფრო, რომ ამ მომენტში.
ძებნა ხე იმას ნიშნავს, რომ ნომრები მოწყობილი ასეთი, რომ მარცხენა ბავშვის
მნიშვნელობა მეტია ძირი.
და მისი უფლება ბავშვი უფრო დიდი, ვიდრე root.
სხვა სიტყვებით, თუ თქვენ მიიღოს ნებისმიერი კვანძების, წრეები ამ სურათს,
და უყურებს მისი მარცხენა ბავშვი და მისი უფლება ბავშვს,
პირველი ნაკლები უნდა იყოს, მეორე უნდა იყოს მეტი.
ასე რომ საღი აზრის ქვითარი 55.
ეს მარცხენა ბავშვი არის 33.
ეს არის ნაკლები.
55, მისი სწორი შვილი არის 77.
ეს უფრო მეტია, ვიდრე.
და რომ რეკურსიული განმარტება.
ჩვენ შეიძლება შეამოწმოს ყველა იმ კვანძების და იგივე ნიმუში იქნებოდა გამართავს.
>> ასე რომ, რა ლამაზი წელს ორობითი ძებნა ხე, არის
რომ ერთი, ჩვენ შეიძლება ეს struct, ისევე, როგორც ეს.
და მიუხედავად იმისა, ჩვენ სროლა უამრავი სტრუქტურების თქვენი,
ისინი გარკვეულწილად ინტუიციური იმედია.
სინტაქსი არის კიდევ arcane დარწმუნებული ვარ, მაგრამ შინაარსი კვანძში ამ
კონტექსტში და ჩვენ შევინარჩუნოთ გამოყენებით სიტყვა კვანძის,
არის თუ არა ეს მართკუთხედი ეკრანზე ან წრე,
ეს მხოლოდ რამდენიმე ზოგადი კონტეინერი, ამ შემთხვევაში ხე, როგორც ერთი
ჩვენ ვნახეთ, ჩვენ გვჭირდება რიცხვი თითოეულ კვანძების
და მერე უნდა ორ მითითებას მიუთითებს მარცხენა ბავშვის და უფლება ბავშვი,
შესაბამისად.
ასე რომ, თუ როგორ შეიძლება განახორციელოს, რომ struct.
და როგორ შეიძლება მე განახორციელოს ეს კოდი?
ისე, მოდით მიიღოს სწრაფი შევხედოთ ამ პატარა მაგალითი.
ეს არ არის ფუნქციონალური, მაგრამ მე გადაწერა და გაკრული, რომ სტრუქტურა.
და თუ ჩემი ფუნქცია ორობითი ძებნა ხე ეწოდება ძიება,
და ეს ხდება ორი არგუმენტები, რიცხვი N და მომცეთ
კვანძის, ასე მომცეთ ხე ან მომცეთ ძირი ხე,
როგორ შემიძლია წასვლა ეძებს N?
პირველ რიგში, იმიტომ, რომ მე საქმე მითითებას,
მე ვაპირებ ამის საღი აზრის ქვითარი.
თუ ხე შეადგენს შეადგენს null, არის N ამ ხე თუ არა ამ ხეს?
ეს არ შეიძლება იყოს, არა?
თუ მე ვარ წარსული null, იქ არაფერია.
მე შეიძლება ასევე მხოლოდ ბრმად ამბობენ დაბრუნების ცრუ.
თუ მაძლევს არაფერი, მე ნამდვილად ვერ მოძიების ნებისმიერი რაოდენობის N. ასე რომ, რა შეიძლება მე
შეამოწმეთ ახლა?
მე ვაპირებ ვთქვა ასევე სხვა თუ N არის ნაკლებია, ვიდრე რაც at ხე კვანძის
რომ მე უკვე გადასცა N ღირებულება.
სხვა სიტყვებით, თუ ნომერი ვარ ეძებს, N, ნაკლებია კვანძის
რომ მე ეძებს.
და კვანძის ვეძებ განთავსებულია ეწოდება ხე,
და გავიხსენოთ წინა მაგალითი მისაღებად საათზე ღირებულების მაჩვენებელი,
მე გამოიყენოთ arrow ნოტაცია.
ასე რომ, თუ N ნაკლებია, ვიდრე ხე arrow N, მინდა კონცეპტუალურად წასვლა მარცხენა.
როგორ შემიძლია გამოხატული ძიების დარჩა?
იყოს ნათელი, თუ ეს სურათი კითხვა,
და მე უკვე გავიდა, რომ უმაღლეს arrow, რომელიც მიუთითებს, ქვემოთ.
ეს არის ჩემი ხე მაჩვენებელი.
მე მიუთითებს ძირი ხე.
და ვეძებ ვთქვათ, ნომერი 44, თვითნებურად.
44-ზე ნაკლები და აღემატება 55 აშკარად?
ასე რომ, ეს ნაკლები.
ასე რომ, თუ პირობა ვრცელდება.
ასე რომ, კონცეპტუალურად, რას მინდა ძიება მომდევნო თუ ვეძებ 44?
ჰო?
>> სწორედ, მე მინდა ძიება მარცხენა ბავშვი,
ან მარცხენა sub-tree ამ სურათს.
და ფაქტობრივად, ნება მომეცით მეშვეობით სურათზე ქვემოთ აქ
მხოლოდ ერთი წუთით, მას შემდეგ, რაც მე არ შემიძლია ნულიდან გარეთ.
თუ მე აქ 55 და მე ვიცი, რომ ღირებულება 44
ვეძებ არის მარცხენა, ეს არის სახის
მოსწონს გაწყვეტა სატელეფონო წიგნი ნახევარი ან tearing ხე ნახევარი.
მე აღარ აინტერესებს მთელი ამ ნახევარი ხე.
და მაინც, საინტერესოა იმ თვალსაზრისით, სტრუქტურა, ეს რაღაც აქ, რომ
იწყება 33, რომ თავად არის ორობითი ძებნა ხე.
მე ვთქვი, სიტყვა რეკურსიული ადრე, რადგან მართლაც ეს არის მონაცემთა სტრუქტურა, რომელიც
ზოგადად არის რეკურსიული.
თქვენ შეიძლება ჰქონდეს ხე, რომელიც ამ დიდი, მაგრამ ყველა მისი შვილები
წარმოადგენს ხის უბრალოდ ცოტა პატარა.
იმის ნაცვლად, რომ ის, რომ ბაბუის ან ბებიას, ახლა ეს მხოლოდ დედა
or-- მე ვერ ვთქვა, არ დედა ან მამა, ეს იქნება უცნაური.
იმის ნაცვლად, რომ ორი შვილი იქ იქნება, როგორც ძმა და ძმა.
ახალი თაობის ოჯახის ხე.
მაგრამ სტრუქტურულად, ეს იმავე იდეას.
და აღმოჩნდება, რომ მაქვს ფუნქცია რომელიც მე შეგიძლიათ მოძებნოთ ორობითი ძებნა
ხე.
მას უწოდებენ ძებნა.
ვეძებ N ხე arrow მარცხენა სხვაგან თუ N მეტია მნიშვნელობა
რომ მე გაკეთებული.
55 ამბავი მომენტში წინ.
მაქვს ფუნქცია მოუწოდა ძებნა, რომელიც მე შემიძლია უბრალოდ
გაივლის N და რეკურსიული ძიება ქვე-ხე და მხოლოდ დაბრუნების
რაც არ უნდა, რომ პასუხი.
სხვაგან მოხვდით გარკვეული საბოლოო ბაზის შემთხვევაში აქ.
>> რა არის საბოლოო შემთხვევაში?
ხე ან null.
ღირებულება მე არც ეძებენ ნაკლებია, ვიდრე ან უფრო მეტი, ვიდრე
ან ტოლია იგი.
და მე ვერ ვიტყვი, თანაბარი თანაბარი, მაგრამ ლოგიკურად ეს
ექვივალენტი უბრალოდ ვამბობ, სხვა აქ.
ამიტომ ჭეშმარიტი არის, თუ როგორ მე რაღაც.
ასე რომ, იმედია, ეს არის კიდევ უფრო მყარი მაგალითად
ვიდრე სულელური სიგმა ფუნქცია ჩვენ გავაკეთეთ რამდენიმე ლექციები უკან,
სადაც იგი იყო ისეთივე მარტივი მარყუჟის ითვლიან up ყველა ნომრები ერთი
ნ აქ მონაცემები სტრუქტურა რომ თავად არის რეკურსიული
განსაზღვრული და რეკურსიული შედგენილი, ახლა ჩვენ აქვს უნარი გამოხატოს საკუთარი თავი
ამ კოდი, რომელიც თავად არის რეკურსიული.
ასე რომ, ეს არის ზუსტად იგივე კოდი აქ.
>> ასე რომ, სხვა რა პრობლემები შეიძლება ჩვენ მოგვარება?
ასე სწრაფად ნაბიჯი დაშორებით ხეები მხოლოდ ერთი წუთით.
აქ არის, ვთქვათ, გერმანიის დროშა.
და იქ აშკარად ნიმუში ამ დროშით.
და არსებობს უამრავი დროშები მსოფლიოს, რომ
როგორც მარტივი, როგორც ამ თვალსაზრისით მათი ფერები და შაბლონებს.
მაგრამ ვფიქრობ, რომ ეს ინახება როგორც .GIF, ან JPEG, ან bitmap, ან ping,
ნებისმიერი გრაფიკული ფაილის ფორმატი რომლითაც თქვენ იცნობს,
ზოგიერთი რომელიც ჩვენ სათამაშო in Pset4.
ეს არ ჩანს იმასაც შესანახად შავი pixel, შავი pixel, შავი pixel,
dot, dot, dot, მთელი bunch შავი პიქსელი პირველად scanline,
ან ზედიზედ, შემდეგ მთელი bunch იგივე, მაშინ მთელი bunch
იგივე, და შემდეგ მთელი bunch წითელი პიქსელი,
წითელი პიქსელი, წითელი პიქსელი, შემდეგ მთელი რამოდენიმე ყვითელი პიქსელი, ყვითელი, არა?
>> არსებობს ასეთი არაეფექტურობას აქ.
როგორ დაახასიათებდით ინტუიციურად შეკუმშოს გერმანიის დროშა
თუ ახორციელებს, როგორც ფაილი?
Like რა ინფორმაციას ჩვენ არ გადაიტვირთოთ შენახვა დისკზე, რათა
შემცირება ჩვენი ფაილი ზომა მოსწონს მეგაბაიტი რომ kilobyte, რაღაც
პატარა?
რაში მდგომარეობს redundancy აქ უნდა იყოს ნათელი?
რა შეგიძლიათ გააკეთოთ?
ჰო?
ზუსტად.
რატომ არ ვიდრე მახსოვს ფერი ყოველ darn pixel
ისევე, როგორც თქვენ აკეთებთ Pset4 ერთად bitmap ფორმატში,
რატომ არ მხოლოდ წარმოადგენს leftmost სვეტი პიქსელი, მაგალითად
რამოდენიმე შავი პიქსელი, bunch წითელი და რამოდენიმე ყვითელი,
და შემდეგ უბრალოდ რატომღაც encode იდეა ვიმეორებ ამ 100 ჯერ
ან გაიმეოროს ეს 1000-ჯერ?
სად 100 და 1000 არის უბრალოდ რიცხვი, ასე რომ თქვენ
შეუძლია მიიღოს away მასთან მხოლოდ ერთი ნომერი ნაცვლად ასობით და ათასობით
დამატებითი პიქსელი.
და მართლაც, ის, თუ როგორ შეიძლება შეკუმშოს გერმანიის დროშა.
და
ახლა, რაც შეეხება საფრანგეთის დროშა?
და ცოტა გარკვეული ფსიქიკური განხორციელება, რომელიც დროშა
შეიძლება შეკუმშვას უფრო დისკზე?
გერმანიის დროშა ან ფრანგული დროშა, თუ ავიღებთ, რომ მიდგომა?
გერმანიის დროშა, იმიტომ, რომ იქ უფრო ჰორიზონტალური redundancy.
და დიზაინი, მრავალი გრაფიკული ფაილი ფორმატების მართლაც მუშაობა, როგორც სკანირების ხაზები
ჰორიზონტალურად.
მათ შეეძლოთ მუშაობა ვერტიკალურად, უბრალოდ კაცობრიობის
გადაწყვიტა წლის წინ, რომ ჩვენ ზოგადად ვფიქრობ, რამ row
მიერ ზედიზედ ნაცვლად სვეტი მიერ სვეტი.
ასე რომ, მართლაც, თუ თქვენ შევხედოთ ფაილი
ზომა გერმანიის დროშა და საფრანგეთის დროშა, ასე რომ სანამ რეზოლუცია
იგივე, იგივე სიგანე და სიმაღლე, ამ ერთი
აქ იქნება უფრო დიდი, იმიტომ, რომ თქვენ უნდა გავიმეოროთ თავს სამჯერ.
თქვენ უნდა მიუთითოთ ლურჯი, განმეორებითი თავს, თეთრი, ვიმეორებ თავს, წითელი,
ვიმეორებ თავს.
თქვენ არ შეგიძლიათ უბრალოდ წავიდეთ ყველა გზა მარჯვნივ.
და როგორც განზე, რათა გარკვევა შეკუმშვის
ყველგან არის, თუ ეს ოთხი ფარგლებში საწყისი ვიდეოში თქვენ
ალბათ გახსოვთ, რომ ფილმი ან ვიდეო ზოგადად
ისევე როგორც 29 ან 30 კადრი წამში.
ეს იგივეა, ცოტა flip წიგნი, სადაც თქვენ უბრალოდ ვხედავ სურათი, სურათი, სურათი, სურათი,
სურათი უბრალოდ სუპერ სწრაფი, ასე რომ ჰგავს მსახიობები ეკრანზე მივდივართ.
აი Bumble Bee on თავზე ყვავილების თაიგული.
მიუხედავად იმისა, რომ ეს შეიძლება იყოს სახის იმისთვის, რომ ვხედავ, ერთი შეხედვით,
ერთადერთი, რაც მოძრაობს ეს ფილმი არის bee.
>> რა არის მითუმეტეს შესახებ შენახვის ვიდეო uncompressed?
ეს არის სახის ნარჩენების შესანახად ვიდეო ოთხი თითქმის იდენტური სურათები რომ
განსხვავდება მხოლოდ იმდენად, რამდენადაც, სადაც ფუტკარი.
თქვენ შეგიძლიათ გადაყარეთ ყველაზე ამ ინფორმაციას,
და მახსოვს მხოლოდ, მაგალითად, პირველი ჩარჩო და ბოლო ფარგლებში,
გასაღები ფარგლებში, თუ თქვენ ოდესმე მოისმინა სიტყვა,
და მხოლოდ შესანახად შუა, სადაც ფუტკრის არის.
და თქვენ არ უნდა შესანახად ყველა ვარდისფერი,
და ლურჯი და მწვანე ღირებულებები ისევე.
ასე რომ, ეს არის ის, რომ მხოლოდ იმას, რომ შეკუმშვის არის ყველგან.
ეს ტექნიკა, ჩვენ ხშირად იყენებენ ან თავისთავად ამ დღეებში.
>> მაგრამ, როგორ უნდა შეკუმშოს ტექსტი?
როგორ დადიხართ შესახებ compressing ტექსტი?
ისე, თითოეული პერსონაჟი ASCII არის ერთი ბაიტი, რვა ბიტი.
და ეს არის უსარგებლო, უფლება?
იმის გამო, რომ თქვენ ალბათ ტიპი და E და მე და O და U ბევრი
უფრო ხშირად, ვიდრე, როგორც W ან Q და Z, დამოკიდებულია ენაზე, რომელიც
თქვენ წერა რა თქმა უნდა.
ასე რომ, რატომ ვართ გამოყენებით რვა ბიტი ყველა წერილი,
მათ შორის, სულ ცოტა პოპულარული წერილები, უფლება?
რატომ არ გამოიყენოს ნაკლები ბიტი სუპერ პოპულარული წერილები,
მოსწონს E, რამ იცი, პირველი Wheel of Fortune,
და მეტი ბიტი ნაკლებად პოპულარული წერილები?
რატომ?
იმიტომ, რომ ჩვენ უბრალოდ აპირებს მათი გამოყენება ნაკლებად ხშირად.
>> ისე, გამოდის, რომ იქ იყო მცდელობა გააკეთა ამის გაკეთება.
და თუ გავიხსენებთ კლასის სკოლა და საშუალო სკოლა, Morse კოდი.
Morse კოდი აქვს წერტილები და dashes, რომელიც შეიძლება იყოს
გადამდები გასწვრივ მავთულხლართების როგორც ხმები ან სიგნალები გარკვეული.
მაგრამ Morse კოდი სუპერ სუფთა.
ეს არის სახის ორობითი სისტემა რომ თქვენ გაქვთ წერტილები და dashes.
მაგრამ თუ ხედავთ, მაგალითად, ორი წერტილი.
ან თუ თქვენ ფიქრობთ, რომ ოპერატორი ვინც მიდის, როგორც beep, beep, beep,
beep, დარტყმის ცოტა გამოიწვევს რომ აგზავნის სიგნალს,
თუ თქვენ, მიმღები, იღებს ორ წერტილები, რა გაგზავნა არ მიიღეთ?
სრულიად უკანონო.
>> მე?
მე?
ან რა ამაზე და მე
იქნებ ეს მხოლოდ ორი E უფლება?
ასე რომ, ეს პრობლემა საქართველოს decodability ერთად Morse
კოდი, რომლის დროსაც, თუ პირი გაგზავნის თქვენ გაგზავნა
რეალურად პაუზებით ასე რომ თქვენ შეგიძლიათ დაალაგოთ ვხედავ ან მოისმენს ხარვეზები შორის წერილები,
ეს არ არის საკმარისი მხოლოდ გააგზავნოთ ნაკადი zeros და პირობა,
ან წერტილების და dashes, იმიტომ, რომ იქ გაურკვევლობა.
E არის ერთ dot, ასე რომ, თუ თქვენ იხილეთ ორი წერტილი ან მოისმინოს ორი წერტილი,
შესაძლოა, ეს ორი E ან შესაძლოა ეს ერთი I.
ასე რომ, ჩვენ გვჭირდება სისტემა, რომელიც არის ცოტა უფრო ჭკვიანი, ვიდრე.
ასე რომ, ერთი კაცი, სახელად Huffman წლის წინ გამოვიდა სწორედ ეს არის.
ასე რომ, ჩვენ უბრალოდ აპირებს მიიღოს სწრაფი შეხედვით
თუ როგორ ხეები გერმანე ეს.
ვარაუდობენ, რომ ეს არის რაღაც სულელური გაგზავნა გსურთ გააგზავნოთ,
შედგება მხოლოდ A, B, C-ის D's და E ს, მაგრამ არსებობს ბევრი redundancy აქ.
ეს არ ნიშნავს, რომ ინგლისური.
ეს არ არის დაშიფრული.
ეს უბრალოდ სულელური გაგზავნა უამრავი განმეორება.
ასე რომ, თუ თქვენ ნამდვილად ითვლიან out ყველა ა-ს, B- ს, C- ს, D's და E ს, აქ
სიხშირე.
20% ასო ა-ს, 45% ასო
არიან E, და სამი სხვა სიხშირეზე.
ჩვენ დათვლილი up there ხელით და უბრალოდ გააკეთა მათემატიკის.
>> გამოდის, რომ Huffman, რამდენიმე ხნის წინ,
მიხვდა, რომ, თქვენ იცით, რა, თუ დავიწყებ შენობა
ხე, ან ტყის ხეების, თუ გნებავთ, ასეთია, მე შემიძლია ამის შემდეგ.
მე ვაპირებ, რათა კვანძის ყოველ წერილებს, რომ მე აინტერესებს
და მე ვაპირებ შესანახად შიგნით რომ კვანძის
სიხშირეები როგორც მცურავი წერტილი ღირებულება, ან თქვენ შეიძლება გამოიყენოთ ეს N, ძალიან,
მაგრამ ჩვენ უბრალოდ გამოიყენოთ float აქ.
და ალგორითმი, რომელიც მან შემოგვთავაზა, რომ თქვენ
მიიღოს ამ ტყეში ერთი კვანძის ხეები, ასე სუპერ მოკლე ხეები,
და თქვენ დაიწყოს დამაკავშირებელი მათ ახალი ჯგუფები, ახალი მშობლები, თუ გნებავთ.
და თქვენ ამ არჩევით ორი პატარა სიხშირეზე დროს.
ამიტომ მე მივიღე 10% და 10%.
მე შექმნა ახალი კვანძის.
მე მოვუწოდებ ახალი კვანძის 20%.
>> რომელი ორი კვანძების მე გაერთიანდება შემდეგი?
ეს ცოტა ბუნდოვანია.
ასე რომ, არსებობს რამდენიმე კუთხეში შემთხვევებში განიხილოს, მაგრამ შენარჩუნება რამ საკმაოდ,
მე ვაპირებ აირჩიოს 20% - მე ახლა იგნორირება შვილი.
მე ვაპირებ აირჩიოს 20% და 15% და დავხატოთ ორი ახალი კიდეები.
და ახლა, რომელიც ორ კვანძების შემიძლია ლოგიკურად აერთიანებს?
იგნორირება ყველა ბავშვები, ყველა შვილიშვილი, უბრალოდ შევხედოთ ფესვები
ახლა.
რომელი ორი კვანძების შემიძლია უსიამოვნოა ერთად?
Point ორი და 0.35.
დავხატავ ორი ​​ახალი კიდეები.
და მაშინ მე მხოლოდ ერთი მარცხენა.
ასე რომ, აქ ხე.
და ეს უკვე შედგენილი განზრახ გამოიყურება სახის საკმაოდ,
მაგრამ შეამჩნია, რომ კიდეები აქვს ასევე უკვე შეაფასა, ნულოვანი და ერთი.
ასე რომ, ყველა მარცხენა კიდეები ნულოვანი თვითნებურად, მაგრამ თანმიმდევრულად.
ყველა უფლება კიდეები მიიჩნიეს.
>> ასე რომ, რა Hoffman შემოთავაზებული არის, თუ გვინდა, რომ წარმოადგენს B,
ვიდრე წარმოადგენს რაოდენობა 66, როგორც ASCII რომელიც რვა მთელი ბიტი,
თქვენ იცით, რა, უბრალოდ მაღაზიაში ნიმუში ნულოვანი, ნულოვანი, ნულოვანი,
ნულოვანი, იმიტომ, რომ ის გზას ჩემი ხე, ბატონი Huffman ნაძვის ხე,
ფოთოლი root.
თუ გსურთ შესანახად E განსხვავებით, არ
გაუგზავნე რვა ბიტი, რომ წარმოადგენს E. ამის ნაცვლად, გაგზავნას რა ნიმუში ბიტი?
ერთ-ერთი.
და რა არის ლამაზი ამ არის რომ E არის ყველაზე პოპულარული წერილი,
და თქვენ იყენებთ უმოკლეს კოდი იგი.
შემდეგი ყველაზე პოპულარული წერილი ჰგავს ეს
იყო A. ასე რომ რამდენი ბიტი მას ასევე არ ვთავაზობ, რომ?
ნულოვანი, ერთი.
>> და რადგან იგი განხორციელდა რადგან ეს ხე, ახლა
მიადევნე თვალი ითვალისწინებს იქ გაურკვევლობა როგორც Morse
კოდი, იმიტომ, რომ ყველა წერილები აინტერესებს
დასასრულს ამ კიდეები.
ასე რომ, მხოლოდ ერთი განაცხადის ხე.
ეს is-- და მე ტალღის ჩემი მხრივ ეს, თუ როგორ
შეიძლება განახორციელოს ეს როგორც C სტრუქტურა.
ჩვენ უბრალოდ უნდა დააკავშიროთ სიმბოლო, როგორც char,
და სიხშირე მარცხენა და მარჯვენა.
მაგრამ მოდით შევხედოთ ორი საბოლოო მაგალითები, რომ თქვენ
საკმაოდ იცნობს მას შემდეგ, რაც ვიქტორინა ნულოვანი პრობლემა მითითებული ხუთ.
>> ასე რომ, არსებობს მონაცემები სტრუქტურა ცნობილია, როგორც hash მაგიდა.
და hash მაგიდა არის ერთგვარი გაგრილებას, რომ მას აქვს თაიგულების.
და ვარაუდობენ, რომ იქ ოთხი თაიგულების აქ, მხოლოდ ოთხი ცარიელი ფართები.
აი deck ბარათების, და აქ არის კლუბი, ბარი, კლუბი, ბრილიანტები, კლუბი,
ბრილიანტები, შესვლა, ბრილიანტები, clubs-- ასე რომ ეს არის შემთხვევითი.
გულები, hearts-- ასე რომ მე ვარ bucketizing ყველა საშუალებებით აქ.
და hash მაგიდა საჭიროებების შევხედოთ თქვენი input,
და შემდეგ დააყენოს ის გარკვეული განათავსეთ საფუძველზე რას ვხედავ.
ეს ალგორითმი.
და მე გამოყენებით სუპერ მარტივი ვიზუალური ალგორითმი.
უმძიმესი ნაწილი, რომელიც დამახსოვრების რა სურათები იყო.
და მაშინ იქ ოთხი სულ რამ.
>> ახლა stacks იზრდება, რომელიც არის მიზანმიმართული დიზაინი, რაც აქ.
მაგრამ რა შეიძლება გავაკეთო?
ასე რომ, რეალურად, აქ ჩვენ გვაქვს რამოდენიმე ძველი სკოლა გამოცდა წიგნები.
ვარაუდობენ, რომ bunch of სტუდენტები სახელები აქ.
აი დიდი hash მაგიდა.
იმის ნაცვლად, რომ ოთხი თაიგულების, მე, ვთქვათ, 26.
და ჩვენ არ გვინდა, რომ ვისესხო 26 რამ გარედან [? Annenberg?], ასე
აქ არის ხუთი, რომელიც წარმოადგენს მეშვეობით ზ და თუ მე
იხილეთ სტუდენტი, რომლის სახელი იწყება, მე ვაპირებ დააყენოს მისი ინტელექტუალური არსებობს.
თუ ვინმე იწყება C, იქ, A-- რეალურად, არ სურს ამის გაკეთება.
B მიდის აქ.
ასე რომ, მაქვს A, B და C. და ახლა აქ არის კიდევ ერთი სტუდენტი.
მაგრამ თუ ეს hash მაგიდა განხორციელდეს მასივი,
მე სახის ბრალია ამ ეტაპზე, არა?
მე სახის უნდა დააყენოს ამ სადღაც.
>> ასე რომ, ერთი გზა მე შეუძლია გადაწყვიტოს ეს არის, ყველა მარჯვნივ, დაკავებულია, B არის დაკავებული, C არის დაკავებული.
მე ვაპირებ, რომ მას დ ასე რომ, პირველი, მე შემთხვევითი მყისიერი ხელმისაწვდომობის
თითოეულ თაიგულების სტუდენტებს.
მაგრამ ახლა ეს სახის გადადის რაღაც წრფივი,
იმიტომ, რომ თუ მინდა მოვძებნო ვინმე რომლის სახელი იწყება, მე შეამოწმეთ აქ.
მაგრამ თუ ეს არ არის ა სტუდენტი ვეძებ,
ასეთი უნდა დაიწყოს შემოწმების თაიგულების, რადგან ის, რაც მე
იყო ერთგვარი ხაზოვანი გამოძიების მონაცემების სტრუქტურას.
სულელი გზას ვამბობ, უბრალოდ გამოიყურება პირველად ხელმისაწვდომი გახსნა,
და, როგორც გეგმა B, ასე ვთქვათ, ან გეგმა D ამ შემთხვევაში, ღირებულება
ამ ადგილას ნაცვლად.
ეს არის მხოლოდ იმიტომ, რომ, თუ თქვენ მიიღო 26 ადგილას და სტუდენტებს
სახელით Q და Z, ან რაღაც რომ, მინიმუმ თქვენ იყენებთ სივრცეში.
>> მაგრამ ჩვენ უკვე ჩანს მეტი ჭკვიანი გადაწყვეტილებები აქ, არა?
რას იზამდით, ნაცვლად თუ თქვენ გაქვთ შეჯახება?
თუ ორ ადამიანს აქვს სახელი A, თუ რა
არ ყოფილა მსოფლიოს სასურველი სტუმარი გახდებით და უფრო ინტუიციური გადაწყვეტა, ვიდრე უბრალოდ
აყენებს, სადაც D უნდა იყოს?
რატომ არ მე უბრალოდ წასვლა გარეთ [? Annenberg?],
როგორც malloc, ერთი კვანძის, ამას აქ, და შემდეგ დააყენა, რომ სტუდენტი აქ.
ასე რომ, მე არსებითად გარკვეული სახის მასივი,
ან იქნებ უფრო ელეგანტურად როგორც ჩვენ დაწყებული დაინახოს უკავშირდება სიაში.
>> ასე რომ hash მაგიდა არის სტრუქტურა რომ შეიძლება გამოიყურებოდეს ისევე, როგორც ეს,
მაგრამ უფრო ჭკვიანურად, თქვენ რაღაც მოუწოდა ცალკე chaining, რომლის hash მაგიდა
უბრალოდ მასივი, თითოეული რომლის ელემენტები არ არის ნომერი,
თავისთავად უკავშირდება სიაში.
ასე, რომ თქვენ სუპერ სწრაფი დაშვება გადაწყვეტილების მიღებისას, სადაც hash თქვენი ღირებულების.
ჰგავს ბარათები მაგალითად, მე მივიღე სუპერ სწრაფი გადაწყვეტილებები.
გულები მიდის აქ, ბრილიანტები მიდის აქ.
იგივე აქ, A მიდის აქ, D მიდის აქ, B მიდის აქ.
ასე რომ, სუპერ სწრაფი look-ups, და თუ თქვენ არ გადაეყარონ შემთხვევაში
სადაც თქვენ მოხვდით collisions, ორი ადამიანი, ამავე სახელწოდების, ასევე მაშინ
თქვენ დავიწყო აკავშირებს მათ ერთად.
და იქნებ თქვენ შენარჩუნება მათ დალაგებულია ალფავიტის მიხედვით, შესაძლოა, თქვენ არ.
მაგრამ მაინც, ახლა ჩვენ გვაქვს დინამიკას.
ასე რომ, ერთის მხრივ, ჩვენ გვაქვს სუპერ სწრაფი მუდმივი, და სახის ხაზოვანი დრო
ჩართული, თუ ეს დაკავშირებული სიები დაიწყოს მიიღოს ცოტა ხანი.
>> ასე რომ, ეს სახის სულელური, geeky ხუმრობა წლის წინ.
ამავე CS50 hack-a-thon, როდესაც სტუდენტები შემოწმება,
ზოგიერთი TF ან CA ყოველწლიურად ფიქრობს, რომ ეს სასაცილო დაფასოებული
ნიშანი, როგორც ეს, სადაც იგი მხოლოდ ნიშნავს თუ თქვენი სახელი იწყება A,
წავიდეთ ამ გზით.
თუ თქვენი სახელი იწყება ერთად B, წასვლა ამას OK,
ეს სასაცილოა, შესაძლოა, შემდეგ სემესტრში.
მაგრამ არსებობს კიდევ ერთი გზა ამით, ძალიან.
დავბრუნდებით რომ.
>> ასე რომ ეს სტრუქტურა.
და ეს არის ჩვენი ბოლო სტრუქტურა, დღეს,
რომელიც რაღაც მოუწოდა trie.
T-R-I-E, რომელიც რატომღაც მოკლე კითხვის, მაგრამ ეს ე.წ. trie.
ამიტომ trie არის კიდევ ერთი საინტერესო დარეგულირებაზე ბევრი იდეები.
ეს არის ხე, რომელიც ჩვენ ვნახეთ ადრე.
ეს არ არის ორობითი ძებნა ხე.
ეს ხე ნებისმიერი რაოდენობის შვილი, მაგრამ თითოეული ბავშვების trie
მასივი.
მასივი ზომა, ვთქვათ, 26 ან იქნებ 27 თუ გვინდა, რომ მხარს ვუჭერთ hyphenated სახელები
ან ხაზს ხალხის სახელები.
>> ასე რომ, ეს არის მონაცემები სტრუქტურა.
და თუ გადავხედავთ ზემოდან ქვედა, როგორიცაა, თუ
შეხედეთ ზევით კვანძის იქ, M, არის მიუთითებს leftmost რამ არსებობს,
რომელიც შემდეგ A, X, W, E, L, L. ეს არის უბრალოდ მონაცემები სტრუქტურა, რომელიც თვითნებურად
არის შენახვის ხალხის სახელები.
და მაქსველი ინახება მხოლოდ შემდეგი გზა მასივი მასივი მასივი.
მაგრამ რა არის საოცარი trie არის რომ, მაშინ, როდესაც უკავშირდება სიაში და კიდევ
მასივი, საუკეთესო ჩვენ ოდესმე მიღებული არის ხაზოვანი დროს და ლოგარითმული დრო ეძებს
ვინმე up.
ამ მონაცემების სტრუქტურა trie, თუ ჩემი მონაცემები სტრუქტურა აქვს ერთი სახელი და გვარი
და ვეძებ Maxwell, მე აპირებთ პოულობენ მას საკმაოდ სწრაფად.
მე უბრალოდ ვეძებთ M-A-X-W-E-L-L. თუ ამ მონაცემების სტრუქტურას, პირიქით,
თუ N მილიონი, თუ არ არის მილიონი სახელები ამ მონაცემების სტრუქტურას,
Maxwell მაინც იქნება discoverable შემდეგ მხოლოდ M-A-X-W-E-L-L
ნაბიჯები.
და დავით დ-A-V-I-D ნაბიჯები.
სხვა სიტყვებით, აშენებს მონაცემთა სტრუქტურა, რომელიც არის
მივიღე ყველა ამ მასივები, რაც თავად მხარს ვუჭერთ წვდომის,
შემიძლია დაიწყოს ეძებს ხალხის ასახელებს გამოყენებით დროის, რომ
პროპორციული არ არის რიცხვი რამ მონაცემები სტრუქტურა,
როგორც მილიონი არსებული სახელები.
დროის სჭირდება ჩემთვის იპოვოს M-A-X-W-E-L-L ამ მონაცემების სტრუქტურას
პროპორციული არა ზომა მონაცემთა სტრუქტურა,
მაგრამ სიგრძეზე სახელი.
და რეალურად სახელები ჩვენ ვეძებთ up
არასოდეს იქნება გიჟები ხანგრძლივი.
იქნებ ვინმეს აქვს 10 ხასიათი ასახელებს, 20 ხასიათის სახელი.
ეს, რა თქმა სასრულ, არა?
არ არის ადამიანის დედამიწაზე, რომელიც აქვს გრძელი შესაძლებელია სახელი,
მაგრამ ეს სახელი არის მუდმივი მნიშვნელობა სიგრძე, არა?
იგი არ განსხვავდება ნებისმიერი გაგებით.
ასე რომ, ამ გზით, ჩვენ მიღწეული მონაცემთა სტრუქტურა
რომ არის მუდმივი დრო სახეს-მდე.
ეს არ მიიღოს რიგი ნაბიჯები დამოკიდებულია სიგრძე შეყვანა,
მაგრამ არა რაოდენობის სახელი ამ მონაცემების სტრუქტურას.
ასე რომ, თუ ჩვენ რაოდენობის გაორმაგება სახელები მომავალ წელს მილიარდი შეადგინა,
დასკვნა Maxwell აპირებს ზუსტად იგივე რაოდენობის შვიდი ნაბიჯები
პოულობენ მას.
ასე რომ, ჩვენ, როგორც ჩანს, არ მიაღწია ჩვენი წმინდა გრაალი ქრონომეტრაჟი.
>> ასე რომ, რამდენიმე სწრაფ განცხადებები.
ვიქტორინა ნულოვანი ახლოვდება.
უფრო, რომ, რა თქმა უნდა ვებ- მომდევნო რამდენიმე დღის განმავლობაში.
ორშაბათს ლექცია, რომ ეს დღესასწაული აქ ჰარვარდის ორშაბათს.
ეს არ არის New Haven, ასე რომ, ჩვენ აღების კლასი
-დან New Haven ლექცია ორშაბათს.
ყველაფერი იქნება გადაღებული, და ტრანსლირება, როგორც ყოველთვის,
მაგრამ მოდით, დღეს დასრულდება 30 მეორე კლიპი
სახელწოდებით "ღრმა ფიქრები" მიერ Daven Farnham, რომელიც
იყო ინსპირირებული შარშან შაბათი Night Live ის "ღრმა ფიქრები"
ჯეკ Handy, რომელიც ახლა უნდა აზრი.
>> ფილმი: ახლა, "Deep ფიქრები "მიერ Daven Farnham.
Hash მაგიდასთან.
>> დინამიკები 1: ყველა უფლება, რომ ის ახლა.
ჩვენ დავინახავთ, თქვენ მომავალ კვირას.
>> DOUG: იმისათვის, რომ ნახოთ ეს ქმედება.
მოდით შევხედოთ, რომ ახლა.
ასე რომ, ჩვენ გვაქვს დაუხარისხებელი მასივი.
>> IAN: Doug, შეგიძლიათ წავიდეთ წინ და გადატვირთეთ ეს მხოლოდ ერთი მეორე, გთხოვთ.
ყველა უფლება კამერები მოძრავი, ისე, მოქმედება, როდესაც თქვენ მზად, Doug, OK?
DOUG ყველა უფლება, ასე რომ ჩვენ აქ არის დაუხარისხებელი მასივი.
და მე ფერადი ყველა ელემენტები წითელი მიუთითებს იმაზე, რომ ეს არის, ფაქტობრივად,
დაუხარისხებელი.
ასე რომ გავიხსენოთ, რომ პირველი, რასაც ვაკეთებთ არის ჩვენ დასალაგებლად მარცხენა ნახევარში მასივი.
მაშინ ჩვენ დასალაგებლად მარჯვენა ნახევარში მასივი.
და ya-da, ya-da, ya-da, ჩვენ შერწყმა მათ ერთად.
და ჩვენ გვაქვს სრულიად დახარისხებული მასივი.
ასე რომ, თუ როგორ შერწყმა დალაგების მუშაობს.
>> IAN: Whoa, Whoa, Whoa, დაჭრილი, დაჭრილი, დაჭრილი, დაჭრილი.
Doug, შეგიძლიათ არა მხოლოდ ya-da, ya-da, ya-da, თქვენი გზა მეშვეობით შერწყმა დალაგების.
>> DOUG: მე უბრალოდ გააკეთეს.
ეს ჯარიმა.
ჩვენ კარგი წასვლა.
მოდით უბრალოდ შეინახოს მოძრავი.
ასე რომ, მაინც,
>> IAN თქვენ უნდა ავუხსნათ ეს უფრო სრულად, ვიდრე.
ეს უბრალოდ არ არის საკმარისი.
DOUG: Ian, ჩვენ არ უნდა დაბრუნდეს ერთი.
ეს ჯარიმა.
ასე რომ, მაინც, თუ ჩვენ გავაგრძელებთ merge-- იან, ჩვენ შუა გადაღება.
>> IAN: მე ვიცი.
და ჩვენ არ შეგვიძლია უბრალოდ ya-da, ya-da, ya-da, მთელი პროცესი.
თქვენ უნდა ავუხსნათ, თუ როგორ ორ მხარეს უნდა გაერთიანდა.
>> DOUG: მაგრამ ჩვენ უკვე განმარტა, თუ როგორ ორი sides--
>> IAN: თქვენ უბრალოდ ნაჩვენები მათ შერწყმა მასივი.
DOUG: მათ იციან პროცესში.
ისინი ჯარიმა.
ჩვენ წავიდა მას ათჯერ.
>> IAN თქვენ უბრალოდ გამოტოვებენ უფლება მას.
ჩვენ ვაპირებთ უკან ერთი, თქვენ არ შეგიძლია ya-da, ya-da მას.
ყველა უფლება, უკან ერთი.
>> DOUG: მე უნდა დაბრუნდეს ყველა სლაიდები?
ჩემი ღმერთი.
ეს იგივეა, მეექვსე იან.
ეს ჯარიმა.
>> IAN ყველა უფლება.
თქვენ მზად?
შესანიშნავი.
აქცია.