1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> დინამიკები 1: ყველა უფლება, ასე რომ ეს არის
CS50 ეს არის ბოლომდე კვირაში ხუთი.

3
00:00:15,860 --> 00:00:19,220
და გავიხსენოთ, რომ ბოლო დროს ჩვენ
დაიწყო ეძებს fancier მონაცემები

4
00:00:19,220 --> 00:00:22,310
სტრუქტურების, რომ დაიწყო გადაჭრა
პრობლემა, რომელიც დაიწყო დანერგვა

5
00:00:22,310 --> 00:00:25,640
ახალი პრობლემები, მაგრამ ამ გასაღები
იყო ერთგვარი threading, რომ ჩვენ

6
00:00:25,640 --> 00:00:27,940
დავიწყე ეხლა კვანძის კვანძის.

7
00:00:27,940 --> 00:00:30,085
ასე რომ, ეს, რა თქმა უნდა
საგნით უკავშირდება სიაში.

8
00:00:30,085 --> 00:00:31,960
და ცალკე უკავშირდება,
ვგულისხმობ იქ მხოლოდ ერთი

9
00:00:31,960 --> 00:00:33,380
ძაფი შორის თითოეული იმ კვანძების.

10
00:00:33,380 --> 00:00:35,890
თურმე შეგიძლიათ გააკეთოთ fancier
რამ, როგორიცაა ორმაგად უკავშირდება სიები

11
00:00:35,890 --> 00:00:38,470
რომლის დროსაც თქვენ გაქვთ arrow
აპირებს ორივე მიმართულებით, რომელიც

12
00:00:38,470 --> 00:00:40,320
დაგეხმარებათ გარკვეული ეფექტურობის.

13
00:00:40,320 --> 00:00:42,000
მაგრამ ეს პრობლემა მოაგვარა?

14
00:00:42,000 --> 00:00:43,500
რას აკეთებდა ეს მოგვარება?

15
00:00:43,500 --> 00:00:46,620
რატომ ჩვენ ვზრუნავთ ორშაბათს?

16
00:00:46,620 --> 00:00:49,820
რატომ, თეორიულად, ჩვენ არ მაინტერესებს ორშაბათს?

17
00:00:49,820 --> 00:00:50,630
რას აკეთებთ?

18
00:00:50,630 --> 00:00:51,950
>> აუდიტორია: ჩვენ შეგვიძლია დინამიურად შეცვლის მას.

19
00:00:51,950 --> 00:00:53,740
>> დინამიკები 1: OK, ასე რომ ჩვენ შეგვიძლია
დინამიურად შეცვლის მას.

20
00:00:53,740 --> 00:00:54,710
კარგად გაკეთდეს, როგორც თქვენ.

21
00:00:54,710 --> 00:00:57,560
ასე რომ, შეგიძლიათ დინამიურად ზომის შეცვლა
მონაცემთა სტრუქტურა, ხოლო მასივი,

22
00:00:57,560 --> 00:01:00,760
გავიხსენოთ, თქვენ უნდა იცოდეს
აპრიორი, თუ რამდენად სივრცეში გსურთ

23
00:01:00,760 --> 00:01:03,870
და თუ საჭიროა ცოტა მეტი
სივრცეში, თქვენ სახის out of luck.

24
00:01:03,870 --> 00:01:05,560
თქვენ უნდა შექმნათ მთელი ახალი მასივი.

25
00:01:05,560 --> 00:01:07,893
თქვენ უნდა გადავიდეს ყველა თქვენი
მონაცემები ერთი სხვა,

26
00:01:07,893 --> 00:01:10,600
საბოლოოდ გასათავისუფლებლად წლის მასივი
თუ შეგიძლია, და შემდეგ გაგრძელება.

27
00:01:10,600 --> 00:01:13,891
რომელი უბრალოდ გრძნობს ძალიან ძვირი და ძალიან
არაეფექტური და მართლაც, ეს შეიძლება იყოს.

28
00:01:13,891 --> 00:01:14,890
მაგრამ ეს არ არის ყველა კარგი.

29
00:01:14,890 --> 00:01:18,180
ჩვენ გადაიხადოს ფასი, რა იყო ერთი
უფრო აშკარა ფასები ჩვენ

30
00:01:18,180 --> 00:01:20,550
გადახდა გამოყენების უკავშირდება სიაში?

31
00:01:20,550 --> 00:01:22,825
>> აუდიტორია: ჩვენ უნდა გამოვიყენოთ
ორმაგი სივრცის თითოეული.

32
00:01:22,825 --> 00:01:25,200
დინამიკები 1: ჰო, ამიტომ ჩვენ უნდა
მინიმუმ ორჯერ იმდენი სივრცე.

33
00:01:25,200 --> 00:01:27,700
ფაქტობრივად, მივხვდი, ეს სურათის
კიდევ ცოტა დამაბნეველი,

34
00:01:27,700 --> 00:01:32,200
რადგან CS50 IDE ბევრი თანამედროვე
კომპიუტერები, მომცეთ ან მისამართი

35
00:01:32,200 --> 00:01:33,700
არ არის ის ფაქტი, ოთხი ბაიტი.

36
00:01:33,700 --> 00:01:36,090
ეს ძალიან ხშირად ეს
დღის რვა ბაიტს, რომელიც

37
00:01:36,090 --> 00:01:38,530
იმას ნიშნავს, რომ ბოლოში ყველაზე
ოთხკუთხედს იქ რეალობა

38
00:01:38,530 --> 00:01:40,900
სახის ორჯერ
დიდი, რაც მე შედგენილი,

39
00:01:40,900 --> 00:01:44,409
რაც იმას ნიშნავს, რომ თქვენ იყენებთ სამჯერ
იმდენი სივრცე, როგორც ჩვენ შეიძლება სხვაგვარად.

40
00:01:44,409 --> 00:01:46,700
ახლა, ამავე დროს, ჩვენ
ჯერ კიდევ საუბარი bytes, არა?

41
00:01:46,700 --> 00:01:49,140
ჩვენ არ ემთხვეოდეს საუბარი
მბ ან გიგაბაიტი,

42
00:01:49,140 --> 00:01:51,000
თუ ეს მონაცემები სტრუქტურების კიდევ დიდი.

43
00:01:51,000 --> 00:01:54,510
>> ასე რომ, დღეს ჩვენ ვიწყებთ განიხილოს
როგორ შეიძლება შეისწავლონ მონაცემები

44
00:01:54,510 --> 00:01:57,310
უფრო ეფექტურად, თუ
ფაქტი მონაცემები იღებს დიდია.

45
00:01:57,310 --> 00:02:00,360
მაგრამ მოდით ცდილობენ canonicalize
ოპერაციების პირველი

46
00:02:00,360 --> 00:02:02,460
რომ შეგიძლიათ გააკეთოთ ეს
სახის მონაცემების სტრუქტურები.

47
00:02:02,460 --> 00:02:04,790
ასე რომ, რაღაც კავშირშია
სია ზოგადად მხარს უჭერს

48
00:02:04,790 --> 00:02:07,514
ოპერაციების მინდა წაშლა,
ჩადეთ და ძიება.

49
00:02:07,514 --> 00:02:08,639
და რას ნიშნავს, რომ?

50
00:02:08,639 --> 00:02:11,222
ეს მხოლოდ იმას ნიშნავს, რომ, როგორც წესი,
იმ შემთხვევაში, თუ ადამიანი იყენებს უკავშირდება სია,

51
00:02:11,222 --> 00:02:14,287
ისინი ან ვინმეს აქვს განხორციელებული
ფუნქციები, როგორიცაა წაშლის, კულტურა,

52
00:02:14,287 --> 00:02:16,120
და ძებნის, ასე რომ თქვენ შეგიძლიათ
რეალურად რაღაც

53
00:02:16,120 --> 00:02:18,030
სასარგებლო მონაცემების სტრუქტურას.

54
00:02:18,030 --> 00:02:20,760
მოდით მიიღოს სწრაფი შევხედოთ
როგორ შეიძლება განახორციელოს

55
00:02:20,760 --> 00:02:24,530
ზოგიერთი კოდი უკავშირდება სია ასეთია.

56
00:02:24,530 --> 00:02:27,885
>> ასე რომ, ეს არის რამოდენიმე C კოდი,
არა თუნდაც სრული პროგრამა

57
00:02:27,885 --> 00:02:29,260
რომ მე ნამდვილად სწრაფად წააქეზა.

58
00:02:29,260 --> 00:02:32,300
ეს არ არის ამჟამად განაწილების
კოდი, იმიტომ, რომ ის რეალურად არ აწარმოებს.

59
00:02:32,300 --> 00:02:33,790
მაგრამ შეამჩნია მე უბრალოდ
ერთად კომენტარის განაცხადა,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, რაღაც
იქ, dot dot dot, რაღაც არსებობს.

61
00:02:36,130 --> 00:02:38,410
და მოდით შევჩერდეთ
რა წვნიანი ნაწილები.

62
00:02:38,410 --> 00:02:40,790
ასე რომ ხაზი სამი,
გავიხსენოთ, რომ ეს არის

63
00:02:40,790 --> 00:02:45,960
ჩვენ შევთავაზეთ გამოცხადების კვანძის ბოლო
დროს, ერთ-ერთი იმ მართკუთხა ობიექტები.

64
00:02:45,960 --> 00:02:48,790
მას აქვს int, რომ ჩვენ მოვუწოდებთ N,
მაგრამ ჩვენ შეგვიძლია ეძახით არაფერი,

65
00:02:48,790 --> 00:02:51,920
და შემდეგ struct კვანძის ვარსკვლავი მოუწოდა შემდეგი.

66
00:02:51,920 --> 00:02:55,520
და უბრალოდ უნდა იყოს მკაფიო, რომ მეორე
ხაზი, ხაზი ექვსი, რა არის ეს?

67
00:02:55,520 --> 00:02:57,930
რა არის ეს აკეთებენ?

68
00:02:57,930 --> 00:03:01,044
იმის გამო, რომ, რა თქმა უნდა უფრო
cryptic ვიდრე ჩვენი ჩვეულებრივი ცვლადი.

69
00:03:01,044 --> 00:03:02,740
>> აუდიტორია: რაც მას გადაადგილება ერთი.

70
00:03:02,740 --> 00:03:04,650
>> დინამიკები 1: რაც მას გადაადგილება ერთი.

71
00:03:04,650 --> 00:03:08,580
და იყოს უფრო სწორად,
ეს იქნება შესანახად მისამართი

72
00:03:08,580 --> 00:03:11,582
კვანძი, რომელიც ნიშნავს, რომ
სემანტიკურად შემდეგ იგი, არა?

73
00:03:11,582 --> 00:03:13,540
ასე რომ, ის არ აპირებს
აუცილებლად გადავა არაფერი.

74
00:03:13,540 --> 00:03:15,290
ეს უბრალოდ აპირებს
შესანახად ღირებულება, რომელიც არის

75
00:03:15,290 --> 00:03:17,170
იქნება მისამართი
ზოგიერთი სხვა კვანძის,

76
00:03:17,170 --> 00:03:20,810
და ამიტომაც ჩვენ განაცხადა struct
კვანძის ვარსკვლავი, ვარსკვლავი აღმნიშვნელი

77
00:03:20,810 --> 00:03:22,370
მომცეთ ან მისამართი.

78
00:03:22,370 --> 00:03:26,390
OK, ასე რომ, ახლა თუ ვივარაუდოთ, რომ ჩვენ გვაქვს
ამ N ჩვენს ხელთ არსებული, და მოდით

79
00:03:26,390 --> 00:03:29,490
ვივარაუდოთ, რომ ვინმეს აქვს
ჩასმული მთელი bunch of რიცხვებით

80
00:03:29,490 --> 00:03:30,400
შევიდა უკავშირდება სიაში.

81
00:03:30,400 --> 00:03:35,640
და რომ უკავშირდება სია
აღნიშნა, რომ ზოგიერთი წერტილი

82
00:03:35,640 --> 00:03:39,040
ცვლადში სია რომ
გადავიდა აქ, როგორც პარამეტრი,

83
00:03:39,040 --> 00:03:43,120
როგორ შემიძლია წასვლა ონლაინ
14 ახორციელებს ძიება?

84
00:03:43,120 --> 00:03:45,990
სხვა სიტყვებით, თუ მე ახორციელებს
ფუნქცია, რომლის მიზანი ცხოვრებაში

85
00:03:45,990 --> 00:03:48,889
არის მიიღოს int და შემდეგ
დასაწყისი უკავშირდება სია,

86
00:03:48,889 --> 00:03:50,430
რომ არის მაჩვენებელი უკავშირდება სიაში.

87
00:03:50,430 --> 00:03:52,992
პირველი, რომელიც მე ვფიქრობ, დავით
იყო ჩვენი მოხალისე ორშაბათს,

88
00:03:52,992 --> 00:03:54,700
იგი მიუთითებს
მთელი უკავშირდება სიაში,

89
00:03:54,700 --> 00:03:57,820
ეს თითქოს ჩვენ ავლით
დავით, როგორც ჩვენი არგუმენტი აქ.

90
00:03:57,820 --> 00:03:59,990
როგორ უნდა წავიდეს შესახებ გადიოდა ამ სიაში?

91
00:03:59,990 --> 00:04:04,640
ისე, გამოდის, რომ მიუხედავად იმისა, რომ
პოინტერები შედარებით ახალი ახლა ჩვენთვის,

92
00:04:04,640 --> 00:04:07,010
ჩვენ შეგვიძლია ამის გაკეთება შედარებით
პირდაპირ.

93
00:04:07,010 --> 00:04:09,500
>> მე ვაპირებ წავიდეთ წინ და
განაცხადოს დროებითი ცვლადი, რომ

94
00:04:09,500 --> 00:04:12,364
კონვენციის უბრალოდ აპირებს
ეწოდოს მაჩვენებელი, ან PTR,

95
00:04:12,364 --> 00:04:14,030
მაგრამ თქვენ ვერ ვუწოდებ არაფერი გსურთ.

96
00:04:14,030 --> 00:04:16,470
და მე ვაპირებ ინიციალიზაცია
ის დაწყების სიაში.

97
00:04:16,470 --> 00:04:20,050
ასე რომ თქვენ შეგიძლიათ სახის ვფიქრობ ეს
როგორც ჩემთვის მასწავლებელი მეორე დღეს,

98
00:04:20,050 --> 00:04:23,580
სახის მიუთითებს ვინმე
მათ შორის ჩვენი ადამიანები, როგორც მოხალისეები.

99
00:04:23,580 --> 00:04:26,470
ასე რომ, მე დროებითი ცვლადი, რომ
მხოლოდ მიუთითებს, რომ იგივე

100
00:04:26,470 --> 00:04:31,390
რომ ჩვენი ერთსა დაასახელა
მოხალისე დავით ასევე მიუთითებს,.

101
00:04:31,390 --> 00:04:35,440
ახლა, ხოლო მაჩვენებელი
არ null, იმიტომ, რომ გავიხსენოთ

102
00:04:35,440 --> 00:04:40,350
რომ null არის რაღაც განსაკუთრებული Sentinel ღირებულება
demarcates ბოლოს სიაში,

103
00:04:40,350 --> 00:04:44,280
ასე რომ, როდესაც მე არ მიუთითებს
ადგილზე, ისევე როგორც ჩვენი ბოლო მოხალისე

104
00:04:44,280 --> 00:04:47,190
იყო, მოდით წავიდეთ წინ
და ამის შემდეგ.

105
00:04:47,190 --> 00:04:51,820
თუ მაჩვენებელი და ახლა მე ასეთი მინდა
გავაკეთოთ ის, რაც ჩვენ გავაკეთეთ სტუდენტი

106
00:04:51,820 --> 00:04:57,410
სტრუქტურა თუ მაჩვენებელი dot შემდეგი
equals-- უფრო სწორად, თუ მაჩვენებელი dot N უდრის

107
00:04:57,410 --> 00:05:02,290
უდრის ცვლადი N,
არგუმენტი, რომ უკვე გავიდა,

108
00:05:02,290 --> 00:05:05,370
მაშინ მინდა წავიდეთ წინ
და აცხადებენ, რომ დაბრუნდება ნამდვილი.

109
00:05:05,370 --> 00:05:11,020
მე აღმოვაჩინე ნომერი N შიგნით
ერთი კვანძების ჩემი დაკავშირებული სიაში.

110
00:05:11,020 --> 00:05:13,500
მაგრამ dot აღარ
მუშაობს ამ კონტექსტში,

111
00:05:13,500 --> 00:05:17,260
იმიტომ, რომ მაჩვენებელი, PTR, არის
მართლაც მაჩვენებელი, მისამართი,

112
00:05:17,260 --> 00:05:20,632
ჩვენ რეალურად შეუძლია შესანიშნავად
გამოყენება საბოლოოდ ნაჭერი სინტაქსი

113
00:05:20,632 --> 00:05:22,590
რომ სახის მარკა
ინტუიციური გრძნობა და რეალურად

114
00:05:22,590 --> 00:05:27,870
გამოიყენოთ arrow, რაც იმას ნიშნავს გადასვლა
რომ მიმართვაში რიცხვი იქ.

115
00:05:27,870 --> 00:05:30,160
ასე რომ, ეს ძალიან ჰგავს
სული რომ dot ოპერატორი,

116
00:05:30,160 --> 00:05:33,860
არამედ იმიტომ, რომ მაჩვენებელი არ მომცეთ
და არა ფაქტობრივი struct თავისთავად,

117
00:05:33,860 --> 00:05:35,380
ჩვენ უბრალოდ გამოიყენოთ arrow.

118
00:05:35,380 --> 00:05:40,620
>> ასე რომ, თუ მიმდინარე კვანძის, რომ მე,
დროებითი ცვლადი, ვარ მიუთითებს

119
00:05:40,620 --> 00:05:43,060
არ არის ნ, რა უნდა გავაკეთოთ?

120
00:05:43,060 --> 00:05:45,910
ისე, ჩემი ადამიანის მოხალისეები
რომ ჩვენ გვქონდა აქ მეორე დღეს,

121
00:05:45,910 --> 00:05:49,710
თუ ჩემი პირველი ადამიანის არ არის, მე
მინდა, და იქნებ მეორე ადამიანის არ

122
00:05:49,710 --> 00:05:52,660
ერთი მინდა, და მესამე, მე
უნდა შევინარჩუნოთ ფიზიკურად მოძრაობს.

123
00:05:52,660 --> 00:05:54,690
როგორიცაა როგორ ნაბიჯ მეშვეობით სიაში?

124
00:05:54,690 --> 00:05:57,470
როდესაც ჩვენ გვქონდა მასივი, თქვენ
უბრალოდ გააკეთეს, როგორიც მე plus plus.

125
00:05:57,470 --> 00:06:03,660
მაგრამ ამ შემთხვევაში, საკმარისია
ამის მაჩვენებელი, იღებს, მაჩვენებელი, მომავალი.

126
00:06:03,660 --> 00:06:07,580
სხვა სიტყვებით, მომდევნო სფეროში
როგორც ყველა მარცხენა ხელში

127
00:06:07,580 --> 00:06:10,880
რომ ჩვენი ადამიანის მოხალისეები ორშაბათს
ინტენსიურად იყენებდა აღვნიშნო ზოგიერთი სხვა კვანძის.

128
00:06:10,880 --> 00:06:12,890
ეს იყო მათი მომავალი მეზობლები.

129
00:06:12,890 --> 00:06:17,060
>> ასე რომ, თუ მინდა დახევას ამ სიაში,
მე არ შემიძლია უბრალოდ მე plus plus აღარ,

130
00:06:17,060 --> 00:06:20,120
მე ნაცვლად უნდა ვთქვა
მე, მაჩვენებელი, აპირებს

131
00:06:20,120 --> 00:06:24,650
ერთნაირი რაც მომდევნო ველი,
შემდეგი სფეროში, მომდევნო ველი,

132
00:06:24,650 --> 00:06:28,350
შემდეგ ყველა იმ მარცხენა ხელში
რომ ჩვენ გვქონდა სცენაზე მიუთითებს

133
00:06:28,350 --> 00:06:30,000
ზოგიერთი შემდგომი ღირებულებებს.

134
00:06:30,000 --> 00:06:32,590
და თუ მივიღებ მეშვეობით
რომ მთელი iteration,

135
00:06:32,590 --> 00:06:39,330
და ბოლოს, მე მოხვდა null არ მქონე
ი ნ მაინც, მე დააბრუნებს false.

136
00:06:39,330 --> 00:06:44,100
ასე რომ კიდევ ერთხელ, ყველა, რომ ჩვენ ვაკეთებთ აქ,
როგორც ერთ სურათზე მომენტში წინ,

137
00:06:44,100 --> 00:06:47,840
იწყება მიერ მიუთითებს
დაწყებული სიაში, სავარაუდოდ.

138
00:06:47,840 --> 00:06:50,970
და მერე შეამოწმოს, არის ღირებულება
ვეძებ ტოლია ცხრა?

139
00:06:50,970 --> 00:06:52,650
თუ ასეა, მე დაბრუნდეს ჭეშმარიტი და მე გაკეთდეს.

140
00:06:52,650 --> 00:06:56,450
თუ არა, მე ჩემ მხრივ,
AKA მაჩვენებელი, უნდა აღვნიშნო,

141
00:06:56,450 --> 00:06:59,540
მომდევნო arrow ადგილმდებარეობა, და
მაშინ შემდეგი arrow ადგილმდებარეობა,

142
00:06:59,540 --> 00:07:00,480
და მომავალი.

143
00:07:00,480 --> 00:07:03,770
მე უბრალოდ გავლით ამ მასივი.

144
00:07:03,770 --> 00:07:06,010
>> ასე რომ კიდევ ერთხელ, ვინ ზრუნავს?

145
00:07:06,010 --> 00:07:07,861
Like რა არის ეს ნივთიერება?

146
00:07:07,861 --> 00:07:10,360
ასევე, გავიხსენოთ, რომ ჩვენ გააცნო
ცნება დასტის, რომელიც

147
00:07:10,360 --> 00:07:15,400
არის აბსტრაქტული მონაცემები აკრიფოთ იმდენად, რამდენადაც ეს
არ არის C ის, რომ ეს არ არის CS50 რამ,

148
00:07:15,400 --> 00:07:19,430
ეს აბსტრაქტული იდეა, ეს იდეა
დაწყობა რამ თავზე ერთმანეთს

149
00:07:19,430 --> 00:07:21,820
რომ შეიძლება განხორციელდეს
მტევნების სხვადასხვა გზები.

150
00:07:21,820 --> 00:07:25,600
და ერთი გზა შევთავაზეთ იყო
მასივი, ან უკავშირდება სიაში.

151
00:07:25,600 --> 00:07:29,570
და აღმოჩნდება, რომ კანონიკური, რომელიც
დასტის მხარს უჭერს მინიმუმ ორი ოპერაცია.

152
00:07:29,570 --> 00:07:32,320
და ხმაურს სიტყვები ბიძგი, რათა
დააყენებს რაღაც გადატანა დასტის,

153
00:07:32,320 --> 00:07:34,770
როგორც ახალი უჯრა
სასადილოს, ან პოპ,

154
00:07:34,770 --> 00:07:39,000
რაც იმას ნიშნავს, რომ ამოიღონ უმაღლეს
უჯრა დასტის სასადილო

155
00:07:39,000 --> 00:07:41,500
დარბაზში, მაშინ შესაძლოა, რამდენიმე
სხვა ოპერაციები, ასევე.

156
00:07:41,500 --> 00:07:45,770
ასე როგორ შეიძლება ჩვენ განსაზღვრავს სტრუქტურა
რომ ჩვენ ახლა მოუწოდებს დასტის?

157
00:07:45,770 --> 00:07:50,020
>> ისე, ჩვენ გვაქვს ყველა საჭირო
სინტაქსი ჩვენს განკარგულებაში C. მე ვიტყვი,

158
00:07:50,020 --> 00:07:53,830
მომეცი ტიპის განსაზღვრება
არის struct შიგნით დასტის,

159
00:07:53,830 --> 00:07:58,030
მე ვაპირებ ვთქვა მასივი, საქართველოს
მთელი bunch of ნომრები და შემდეგ ზომა.

160
00:07:58,030 --> 00:08:00,930
სხვა სიტყვებით, თუ მინდა,
განახორციელოს ეს კოდი,

161
00:08:00,930 --> 00:08:03,830
ნება მომეცით წავიდეთ და მხოლოდ სახის
მიაპყროს რას გვეუბნება ეს.

162
00:08:03,830 --> 00:08:06,317
ასე რომ, ეს ამბობს, მომეცი
სტრუქტურა, რომელიც მიიღო მასივი,

163
00:08:06,317 --> 00:08:09,400
და მე არ ვიცი, რა სიმძლავრე,
ეს, სავარაუდოდ, რამდენიმე მუდმივი, რომ მე

164
00:08:09,400 --> 00:08:10,858
განსაზღვრული სხვაგან, და ეს ჯარიმა.

165
00:08:10,858 --> 00:08:15,260
მაგრამ ვფიქრობ, რომ ეს არის მხოლოდ ერთი,
ორი, სამი, ოთხი, ხუთი.

166
00:08:15,260 --> 00:08:16,700
ასე რომ, მოცულობა 5.

167
00:08:16,700 --> 00:08:21,730
ამ ელემენტს შიგნით ჩემი
სტრუქტურა იქნება მოუწოდა ნომრები.

168
00:08:21,730 --> 00:08:24,020
და მერე უნდა ერთი
სხვა ცვლადი, როგორც ჩანს,

169
00:08:24,020 --> 00:08:27,814
მოუწოდა ზომა, რომ თავდაპირველად მე ვაპირებ
ითვალისწინებს ინიციალიზაცია ნულოვანი.

170
00:08:27,814 --> 00:08:29,730
თუ არაფერი არ არის
დასტის, ზომა არის ნულოვანი,

171
00:08:29,730 --> 00:08:31,420
და ეს არის ნაგვის ღირებულებების ნომრები.

172
00:08:31,420 --> 00:08:33,450
მე არ ვიცი, რა არის იქ უბრალოდ არ არის.

173
00:08:33,450 --> 00:08:36,059
>> ასე რომ, თუ გსურთ დააყენებს
რაღაც გადატანა დასტის,

174
00:08:36,059 --> 00:08:40,780
ვფიქრობ, მოვუწოდებთ ფუნქცია ბიძგი და
მე ვიტყვი დააყენებს 50, ისევე როგორც ნომერი 50,

175
00:08:40,780 --> 00:08:44,090
სადაც იქნებოდა თქვენ შესთავაზოს
მე მიაპყროს იგი ამ მასივი?

176
00:08:44,090 --> 00:08:47,124
არსებობს ხუთი სხვადასხვა შესაძლო პასუხი.

177
00:08:47,124 --> 00:08:48,790
სად გსურთ დააყენებს ნომერი 50?

178
00:08:48,790 --> 00:08:51,899
თუ მიზანი აქ, ისევ, მოვუწოდებთ
ფუნქცია ბიძგი, კორიდორი არგუმენტი

179
00:08:51,899 --> 00:08:52,940
50, სად მე ამას?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
ხუთი შესაძლებლობის 20% შანსი
გამოცნობა სწორად.

182
00:08:59,052 --> 00:08:59,896
დიახ?

183
00:08:59,896 --> 00:09:00,740
>> აუდიტორია: Far უფლება.

184
00:09:00,740 --> 00:09:01,990
>> დინამიკები 1: Far უფლება.

185
00:09:01,990 --> 00:09:08,359
აქ არის 25% შანსი
გამოცნობა სწორად.

186
00:09:08,359 --> 00:09:09,650
ასე რომ, ფაქტობრივად, იქნება ჯარიმა.

187
00:09:09,650 --> 00:09:12,770
კონვენციის, მე ვიტყვი მასივი,
ჩვენ ჩვეულებრივ იწყება მარცხენა,

188
00:09:12,770 --> 00:09:14,519
მაგრამ ჩვენ ნამდვილად
იწყება უფლება.

189
00:09:14,519 --> 00:09:17,478
ასე რომ, სპოილერი აქ იქნება მე
ალბათ აპირებს მიაპყროს ის მარცხენა,

190
00:09:17,478 --> 00:09:20,060
უბრალოდ მინდა ნორმალური მასივი, სადაც
მე დაიწყოს აპირებს მარცხნიდან მარჯვნივ.

191
00:09:20,060 --> 00:09:21,780
მაგრამ თუ თქვენ შეგიძლიათ Flip
არითმეტიკული, ჯარიმა.

192
00:09:21,780 --> 00:09:23,060
ეს უბრალოდ არ არის ჩვეულებრივი.

193
00:09:23,060 --> 00:09:24,880
OK, მე უნდა მიიღოს ერთი
მეტი ცვლილება, თუმცა.

194
00:09:24,880 --> 00:09:27,710
ახლა, მე მივიღებთ რაღაც
გადატანა დასტის, რა არის შემდეგი?

195
00:09:27,710 --> 00:09:29,400
>> ყველა უფლება მაქვს ნამატი ზომა.

196
00:09:29,400 --> 00:09:32,600
ნება მომეცით წავიდეთ წინ და მხოლოდ
განაახლოთ, რომელიც იყო ნულოვანი.

197
00:09:32,600 --> 00:09:35,950
და ნაცვლად ახლა, მე ვაპირებ
იმისათვის, რომ ღირებულება ერთი.

198
00:09:35,950 --> 00:09:39,460
ახლა ვფიქრობ, დააყენებს სხვა
ნომერი გადატანა დასტის, როგორც 51.

199
00:09:39,460 --> 00:09:42,680
ისე, მე მაქვს კიდევ ერთი
ცვლილება, რომელიც მდე ზომის ორი.

200
00:09:42,680 --> 00:09:46,100
და მაშინ ვფიქრობ, დააყენებს კიდევ ერთი
ნომერი გადატანა დასტის, როგორიცაა 61,

201
00:09:46,100 --> 00:09:52,530
ახლა მე უნდა განახლდეს, ზომა ერთი
დრო, და მიიღოს ღირებულება 3, ზომა.

202
00:09:52,530 --> 00:09:54,690
და ახლა ვარაუდობენ, მოვუწოდებ პოპ.

203
00:09:54,690 --> 00:09:57,250
ახლა პოპ, კონვენციის,
არ იღებს არგუმენტი.

204
00:09:57,250 --> 00:10:00,430
დასტის, მთელი
წერტილი უჯრა მეტაფორა

205
00:10:00,430 --> 00:10:03,450
არის, რომ თქვენ არ შეხედულებისამებრ
წავიდეთ მისაღებად რომ პანელში, ყველა შეგიძლიათ გააკეთოთ

206
00:10:03,450 --> 00:10:06,330
არის პოპ უმაღლეს ერთი
დასტის, მხოლოდ იმიტომ.

207
00:10:06,330 --> 00:10:08,010
სწორედ ამ მონაცემების სტრუქტურას აკეთებს.

208
00:10:08,010 --> 00:10:12,250
>> ასე რომ, იმ ლოგიკით, თუ მე
ამბობენ, pop, რა მოდის off?

209
00:10:12,250 --> 00:10:13,080
ასე რომ, 61.

210
00:10:13,080 --> 00:10:15,402
ასე რომ, რა არის კომპიუტერი
ვაპირებთ მეხსიერება?

211
00:10:15,402 --> 00:10:16,610
რას ჩემი კოდი უნდა გავაკეთოთ?

212
00:10:16,610 --> 00:10:20,330
რას გვთავაზობთ
შევცვლით ეკრანზე?

213
00:10:20,330 --> 00:10:23,410
რა უნდა შეიცვალოს?

214
00:10:23,410 --> 00:10:24,960
ბოდიში?

215
00:10:24,960 --> 00:10:26,334
ასე რომ, ჩვენ დავაღწიოთ 61.

216
00:10:26,334 --> 00:10:27,500
ასე რომ, შემიძლია ამის გაკეთება.

217
00:10:27,500 --> 00:10:28,640
და შემიძლია მოშორება 61.

218
00:10:28,640 --> 00:10:30,980
და მერე რა სხვა
ცვლილება უნდა მოხდეს?

219
00:10:30,980 --> 00:10:33,160
ზომა, ალბათ, უნდა დაბრუნდეს ორი.

220
00:10:33,160 --> 00:10:34,210
და ისე, რომ ჯარიმა.

221
00:10:34,210 --> 00:10:36,690
მაგრამ დაველოდოთ წუთში, ზომა
მომენტში წინ იყო სამი.

222
00:10:36,690 --> 00:10:38,240
მოდით უბრალოდ სწრაფი საღი აზრის ქვითარი.

223
00:10:38,240 --> 00:10:41,810
როგორ მოხდა, რომ ჩვენ ვიცით, რომ
სურდა, თავი დაეღწია 61?

224
00:10:41,810 --> 00:10:42,760
იმის გამო, რომ ჩვენ popping.

225
00:10:42,760 --> 00:10:46,450
ასე რომ, მე ამ მეორე ქონება ზომა.

226
00:10:46,450 --> 00:10:48,470
>> ერთი წუთით, მე
ფიქრი თავში კვირაში ორი

227
00:10:48,470 --> 00:10:51,660
როდესაც ჩვენ დავიწყეთ ლაპარაკი
კოლექტორები, სადაც ეს იყო ადგილმდებარეობა ნულოვანი,

228
00:10:51,660 --> 00:10:55,920
ეს იყო ადგილმდებარეობა ერთი, ეს იყო ადგილმდებარეობა
ორი, ეს არის ადგილმდებარეობა სამი, ოთხი,

229
00:10:55,920 --> 00:10:58,460
როგორც ჩანს,
შორის ურთიერთობა ზომა

230
00:10:58,460 --> 00:11:02,780
და ელემენტი, რომელიც მინდა ამოიღონ
საწყისი მასივი, როგორც ჩანს, უბრალოდ, თუ რა?

231
00:11:02,780 --> 00:11:05,120
ზომა მინუს ერთი.

232
00:11:05,120 --> 00:11:07,786
ასე რომ, ის, თუ როგორ, როგორც ადამიანები
ჩვენ ვიცით, 61 მოდის პირველი.

233
00:11:07,786 --> 00:11:09,160
როგორ არის კომპიუტერული აპირებს იცით?

234
00:11:09,160 --> 00:11:11,701
როდესაც თქვენი კოდი, სადაც, სავარაუდოდ,
მინდა ამის გაკეთება ზომა მინუს ერთი,

235
00:11:11,701 --> 00:11:14,950
ასე რომ, სამი მინუს ერთი ორი, და რომ
ნიშნავს, რომ ჩვენ გვინდა, რომ თავი დაეღწია 61.

236
00:11:14,950 --> 00:11:18,000
და მაშინ ჩვენ შეიძლება მართლაც განახლება
ზომა ისე, რომ ზომა ახლა

237
00:11:18,000 --> 00:11:20,300
მიდის სამიდან მხოლოდ ორი.

238
00:11:20,300 --> 00:11:24,520
და უბრალოდ უნდა იყოს pedantic, მე ვაპირებ
იმის მტკიცება, რომ მე გაკეთდეს, არა?

239
00:11:24,520 --> 00:11:27,660
თქვენ შემოთავაზებული ინტუიციურად
სწორად მე უნდა მოისპოს 61.

240
00:11:27,660 --> 00:11:30,700
მაგრამ არ I ტიპის
ერთგვარი მიღებული მოშორება 61?

241
00:11:30,700 --> 00:11:33,790
მე ეფექტურად დავიწყებული
ის, რომ ფაქტობრივად არ არსებობს.

242
00:11:33,790 --> 00:11:37,680
და ვფიქრობ, უკან Pset4, თუ თქვენ წაიკითხავთ
სტატია ექსპერტიზის, PDF

243
00:11:37,680 --> 00:11:40,780
რომ ჩვენ გვქონდა თქვენ ბიჭები წაიკითხოს, ან თქვენ
წაიკითხავს ამ კვირაში Pset4.

244
00:11:40,780 --> 00:11:44,300
შეგახსენებთ, რომ ეს არის რეალურად გერმანე
მთელი იდეა კომპიუტერული სასამართლო.

245
00:11:44,300 --> 00:11:47,820
რა კომპიუტერი საერთოდ არის
ეს უბრალოდ ავიწყდება სად არის რაღაც,

246
00:11:47,820 --> 00:11:51,300
მაგრამ ეს არ წავიდეს და როგორც
ცდილობენ ნულიდან ის ან override

247
00:11:51,300 --> 00:11:54,560
იმ ბიტი zeros და პირობა
ან სხვა შემთხვევითი ნიმუში

248
00:11:54,560 --> 00:11:56,690
თუ თქვენ თავს ამის გაკეთება შეგნებულად.

249
00:11:56,690 --> 00:11:58,930
ასე რომ, თქვენი ინტუიცია იყო
უფლება, მოდით, თავი დაეღწია 61.

250
00:11:58,930 --> 00:12:00,650
მაგრამ სინამდვილეში, ჩვენ არ უნდა გადაიტვირთოთ.

251
00:12:00,650 --> 00:12:04,040
ჩვენ უბრალოდ უნდა დაგვავიწყდეს, რომ
ეს არ იცვლება ჩვენი ზომა.

252
00:12:04,040 --> 00:12:05,662
>> ახლა არის პრობლემა ამ დასტის.

253
00:12:05,662 --> 00:12:07,620
თუ მე შენარჩუნება უბიძგებს რამ
გადატანა დასტის, რა არის

254
00:12:07,620 --> 00:12:11,167
აშკარად მოხდება
მხოლოდ რამდენიმე მომენტი დროს?

255
00:12:11,167 --> 00:12:12,500
ჩვენ ვაპირებთ, რომ ამოიწურა სივრცეში.

256
00:12:12,500 --> 00:12:13,580
და რა ვქნათ?

257
00:12:13,580 --> 00:12:14,680
ჩვენ სახის ბრალია.

258
00:12:14,680 --> 00:12:19,000
ეს განხორციელებას არ მისცეს
ჩვენს შეცვლის მასივი, რადგან გამოყენებით

259
00:12:19,000 --> 00:12:21,240
ეს სინტაქსი, თუ
ვფიქრობ, უკან კვირაში ორი

260
00:12:21,240 --> 00:12:23,520
ერთხელ თქვენ განაცხადა,
ზომა მასივი,

261
00:12:23,520 --> 00:12:26,780
ჩვენ არ მინახავს მექანიზმი, კიდევ სად
თქვენ შეგიძლიათ შეცვალოთ ზომა მასივი.

262
00:12:26,780 --> 00:12:29,020
და მართლაც C არ აქვს, რომ ფუნქცია.

263
00:12:29,020 --> 00:12:32,524
თუ ამბობენ, მომეცი ხუთ
Nths, მოვუწოდებთ მათ ნომრები,

264
00:12:32,524 --> 00:12:33,940
რომ ყველა თქვენ აპირებს მიიღოს იგი.

265
00:12:33,940 --> 00:12:38,790
ამიტომ, ჩვენ, ახლა, როგორც ორშაბათს, აქვს
უნარი გამოხატოს გამოსავალი

266
00:12:38,790 --> 00:12:42,480
მიუხედავად იმისა, რომ ჩვენ უბრალოდ უნდა tweak
განსაზღვრება ჩვენი დასტის

267
00:12:42,480 --> 00:12:46,840
არ უნდა იყოს გარკვეული მყარი კოდირებული მასივი,
მაგრამ მხოლოდ შესანახად მისამართზე.

268
00:12:46,840 --> 00:12:47,890
>> ახლა რატომ არის ეს?

269
00:12:47,890 --> 00:12:51,690
ახლა ჩვენ უბრალოდ უნდა იყოს კომფორტული
ის ფაქტი, რომ ჩემი პროგრამა გადის,

270
00:12:51,690 --> 00:12:53,730
მე სავარაუდოდ აპირებს
უნდა ვთხოვო ადამიანის,

271
00:12:53,730 --> 00:12:55,110
რამდენი ნომრები გინდათ შესანახად?

272
00:12:55,110 --> 00:12:56,776
ასე რომ შეყვანილი უნდა მოდიოდეს სადღაც.

273
00:12:56,776 --> 00:12:59,140
მაგრამ ერთხელ მე ვიცი, რომ
ნომერი, მაშინ მე შემიძლია უბრალოდ

274
00:12:59,140 --> 00:13:02,470
გამოყენება რა ფუნქცია მისცეს
ჩემთვის ბლოკი მეხსიერება?

275
00:13:02,470 --> 00:13:03,580
მე შეიძლება გამოიყენოს malloc.

276
00:13:03,580 --> 00:13:06,710
და შემიძლია ვთქვა, ნებისმიერი რაოდენობის
bytes მინდა უკან ამ Nths.

277
00:13:06,710 --> 00:13:10,910
და ყველა მე უნდა ჩაწეროთ ნომრები
ცვლადი აქ, შიგნით ამ struct

278
00:13:10,910 --> 00:13:13,480
უნდა იყოს თუ რა?

279
00:13:13,480 --> 00:13:18,440
რეალურად რა გადადის
ციფრები ამ შემთხვევაში?

280
00:13:18,440 --> 00:13:21,300
ჰო, მომცეთ პირველი
byte რომ ბლოკი მეხსიერება,

281
00:13:21,300 --> 00:13:24,940
ან უფრო კონკრეტულად, მისამართი
პირველი იმ ბაიტი.

282
00:13:24,940 --> 00:13:27,300
არ აქვს მნიშვნელობა, თუ ეს არის ერთ-ერთი
byte ან მილიარდი ბაიტი,

283
00:13:27,300 --> 00:13:28,890
მე უბრალოდ უნდა ზრუნავდეს პირველი.

284
00:13:28,890 --> 00:13:31,530
იმის გამო, რომ ის, რაც malloc გარანტიები და
ჩემი ოპერაციული სისტემა გარანტიები,

285
00:13:31,530 --> 00:13:34,170
ის არის, რომ ბლოკი მეხსიერება I
მისაღებად, ეს იქნება მომიჯნავე.

286
00:13:34,170 --> 00:13:35,378
იქ არ უნდა იყოს ხარვეზები.

287
00:13:35,378 --> 00:13:38,576
ასე რომ, თუ მე ვთხოვე 50
bytes ან 1000 ბაიტი,

288
00:13:38,576 --> 00:13:40,450
ისინი ყველა იქნება
თავში დაბრუნება უკან.

289
00:13:40,450 --> 00:13:44,500
ასე რომ, სანამ მე მახსოვს, როგორ დიდი, როგორ
ბევრი მოვითხოვე, ყველა მე უნდა იცოდეს

290
00:13:44,500 --> 00:13:46,230
არის პირველი ასეთი მისამართზე.

291
00:13:46,230 --> 00:13:48,660
>> ასე რომ, ახლა ჩვენ გვაქვს შესაძლებლობა, კოდი.

292
00:13:48,660 --> 00:13:51,280
თუმცა, ის აპირებს us
მეტი დრო დაწერა ეს ყველაფერი,

293
00:13:51,280 --> 00:13:55,900
ჩვენ შეგვიძლია ახლა გამოდის, რომ მეხსიერების
მხოლოდ შენახვის სხვადასხვა მისამართზე იქ

294
00:13:55,900 --> 00:13:59,060
თუ ჩვენ გვინდა, უფრო დიდი ან თუნდაც
პატარა ბლოკი მეხსიერება.

295
00:13:59,060 --> 00:14:00,170
ასე რომ, აქ სავაჭრო off.

296
00:14:00,170 --> 00:14:01,360
ახლა ჩვენ დინამიკას.

297
00:14:01,360 --> 00:14:03,350
ჩვენ ჯერ კიდევ გვაქვს
contiguousness მე აცხადებდნენ.

298
00:14:03,350 --> 00:14:05,881
იმის გამო, რომ malloc მოგვცემს
მომიჯნავე ბლოკი მეხსიერება.

299
00:14:05,881 --> 00:14:08,630
მაგრამ ეს იქნება ტკივილი
კისრის ჩვენთვის, პროგრამისტი,

300
00:14:08,630 --> 00:14:09,770
რეალურად კოდი up.

301
00:14:09,770 --> 00:14:10,730
ეს არის მხოლოდ უფრო მეტი მუშაობა.

302
00:14:10,730 --> 00:14:13,930
ჩვენ გვჭირდება კოდი akin, რაც მე
ბრახუნი, მხოლოდ ერთი წუთით წინ.

303
00:14:13,930 --> 00:14:16,120
ძალიან doable, მაგრამ ეს დასძენს სირთულის.

304
00:14:16,120 --> 00:14:19,520
ასე რომ, დეველოპერი დროს, პროგრამისტი
დრო არის კიდევ ერთი რესურსი

305
00:14:19,520 --> 00:14:22,520
რომ ჩვენ შეიძლება უნდა გაატარონ
გარკვეული დრო, რათა მიიღოთ ახალი.

306
00:14:22,520 --> 00:14:24,020
და მაშინ, რა თქმა უნდა, არსებობს რიგი.

307
00:14:24,020 --> 00:14:26,227
ჩვენ არ წასვლას
ერთი ბევრი დეტალი.

308
00:14:26,227 --> 00:14:27,560
მაგრამ ეს ძალიან მსგავსი სულისკვეთება.

309
00:14:27,560 --> 00:14:31,220
მე ვერ განახორციელოს რიგი, და
შესაბამისი ოპერაციები,

310
00:14:31,220 --> 00:14:35,660
enqueue და dequeue, მოსწონს დამატება ან წაშლა,
ეს მხოლოდ fancier გზა რომ,

311
00:14:35,660 --> 00:14:38,100
enqueue და dequeue, ასეთია.

312
00:14:38,100 --> 00:14:41,170
შემიძლია უბრალოდ მივცეთ თავს struct
რომ კიდევ ერთხელ აქვს მთელი რიგი მასივი,

313
00:14:41,170 --> 00:14:44,000
რომ კიდევ ერთხელ აქვს ზომა,
მაგრამ რატომ მე ახლა უნდა

314
00:14:44,000 --> 00:14:46,940
შენარჩუნება სიმღერა წინაშე მდგომ?

315
00:14:46,940 --> 00:14:50,630
მე არ უნდა იცოდეთ
წინ ჩემი Stack.

316
00:14:50,630 --> 00:14:53,570
ისე, თუ მე კიდევ ერთხელ
მდგომ მოდით უბრალოდ მძიმე

317
00:14:53,570 --> 00:14:57,870
კოდი იგი, როგორც მოსწონს ხუთ
რიცხვებით აქ პოტენციურად.

318
00:14:57,870 --> 00:15:00,940
ასე რომ, ეს არის ნულოვანი, ერთი, ორი, სამი, ოთხი.

319
00:15:00,940 --> 00:15:03,430
ეს იქნება
მოუწოდა ნომრები ერთხელ.

320
00:15:03,430 --> 00:15:06,940
და ეს იქნება მოუწოდა ზომა.

321
00:15:06,940 --> 00:15:10,056
>> რატომ არ არის საკმარისი
აქვს მხოლოდ ზომა?

322
00:15:10,056 --> 00:15:11,680
ისე, მოდით დააყენებს იმავე ნომრები.

323
00:15:11,680 --> 00:15:14,220
ასე რომ, მე pushed-- მე enqueued, ან მივიღებთ.

324
00:15:14,220 --> 00:15:20,150
ახლა მე enqueue 50, და შემდეგ
51 და შემდეგ 61 და dot dot dot.

325
00:15:20,150 --> 00:15:21,070
ასე რომ, enqueue.

326
00:15:21,070 --> 00:15:23,176
მე enqueued 50, მაშინ 51, მაშინ 61.

327
00:15:23,176 --> 00:15:25,050
და რომ გამოიყურება იდენტურია
დასტის დღემდე,

328
00:15:25,050 --> 00:15:27,190
გარდა მე უნდა მიიღოს ერთი ცვლილება.

329
00:15:27,190 --> 00:15:33,680
მე უნდა განახლდეს, ეს ზომა, ასე რომ მე წასვლა
ნულიდან ერთი ორი სამი ახლა.

330
00:15:33,680 --> 00:15:35,760
როგორ შემიძლია dequeue?

331
00:15:35,760 --> 00:15:36,890
რა ხდება dequeue?

332
00:15:36,890 --> 00:15:41,950
ვინ უნდა მოვიდეს off ამ სიაში პირველი
თუ ეს ხაზი Apple Store?

333
00:15:41,950 --> 00:15:42,780
ასე რომ, 50.

334
00:15:42,780 --> 00:15:44,700
ასე რომ, ეს სახის რთული სიტუაციაა ამ დროს.

335
00:15:44,700 --> 00:15:47,880
ვინაიდან ბოლო დროს ეს იყო სუპერ
ადვილი უბრალოდ ზომა მინუს ერთი,

336
00:15:47,880 --> 00:15:51,440
მე კიდევ ბოლომდე ჩემი მასივი ეფექტურად
სადაც ნომრები, ის შლის 61.

337
00:15:51,440 --> 00:15:52,920
მაგრამ მე არ მინდა ამოიღონ 61.

338
00:15:52,920 --> 00:15:55,030
მე მინდა, რომ 50, რომელიც
იქ იყო 5:00 AM

339
00:15:55,030 --> 00:15:56,790
რომ გამოდიან
ახალი iPhone ან whatnot.

340
00:15:56,790 --> 00:16:01,200
ასე რომ, თავი დაეღწია 50, მე
არ შეუძლიათ უბრალოდ ამის გაკეთება, არა?

341
00:16:01,200 --> 00:16:02,547
შემიძლია გადაკვეთა 50.

342
00:16:02,547 --> 00:16:04,380
მაგრამ ჩვენ უბრალოდ განაცხადა ჩვენ
არ უნდა იყოს ასე anal

343
00:16:04,380 --> 00:16:06,330
როგორც ნულიდან ან დამალვა მონაცემები.

344
00:16:06,330 --> 00:16:08,090
ჩვენ შეგვიძლია მხოლოდ დაგვავიწყდეს, სადაც ის არის.

345
00:16:08,090 --> 00:16:12,330
>> მაგრამ თუ შევცვალო ჩემი ზომა ახლა
ორი, ეს საკმარისი ინფორმაცია

346
00:16:12,330 --> 00:16:15,711
ვიცი, რა ხდება ჩემი მდგომ?

347
00:16:15,711 --> 00:16:16,680
ნამდვილად არა.

348
00:16:16,680 --> 00:16:19,830
როგორც ჩემი ზომა არის ორი, მაგრამ
სად მდგომ დაიწყოს,

349
00:16:19,830 --> 00:16:22,980
მით უმეტეს, თუ კიდევ მაქვს
იმავე ნომრები მეხსიერება.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
ასე რომ, მე უნდა გვახსოვდეს
ახლა, სადაც წინა.

352
00:16:27,090 --> 00:16:29,630
ასე რომ, მე შევთავაზე up
იქ, ჩვენ არ მხოლოდ ე.წ.

353
00:16:29,630 --> 00:16:33,729
Nth წინ, რომლის საწყის
მნიშვნელობა უნდა ყოფილიყო, თუ რა?

354
00:16:33,729 --> 00:16:35,270
Zero, მხოლოდ დასაწყისია სიაში.

355
00:16:35,270 --> 00:16:40,876
მაგრამ ახლა გარდა decrementing
ზომა, ჩვენ უბრალოდ ნამატი წინ.

356
00:16:40,876 --> 00:16:42,000
ახლა აქ არის კიდევ ერთი პრობლემა.

357
00:16:42,000 --> 00:16:43,030
ასე რომ, კიდევ მე შენარჩუნება აპირებს.

358
00:16:43,030 --> 00:16:47,520
დავუშვათ, რომ ეს არის ნომერი
მოსწონს 121, 124, და შემდეგ, dammit,

359
00:16:47,520 --> 00:16:48,610
მე გარეთ სივრცეში.

360
00:16:48,610 --> 00:16:50,390
მაგრამ დაველოდოთ წუთში, მე არ ვარ.

361
00:16:50,390 --> 00:16:55,630
ამრიგად, ამ ეტაპზე იმ ამბავს,
ვარაუდობენ, რომ ზომა არის ერთი, ორი,

362
00:16:55,630 --> 00:17:00,370
სამი, ოთხი, ამიტომ ვარაუდობენ, რომ
ზომა არის ოთხი, წინა ერთი,

363
00:17:00,370 --> 00:17:01,621
ასე რომ, 51 წინ.

364
00:17:01,621 --> 00:17:04,329
მინდა, რომ მეორე ნომერი აქ,
მაგრამ, dammit, მე გარეთ სივრცეში.

365
00:17:04,329 --> 00:17:06,710
მაგრამ მე არ ვარ ნამდვილად, არა?

366
00:17:06,710 --> 00:17:11,192
სად დააყენა რამდენიმე
დამატებითი ღირებულების, ისევე როგორც 171?

367
00:17:11,192 --> 00:17:13,400
ჰო, მე შეიძლება მხოლოდ სახის
დაბრუნდეს იქ, არა?

368
00:17:13,400 --> 00:17:18,161
და მაშინ გადაკვეთა 50, ან
მხოლოდ გადაწერა იგი 171.

369
00:17:18,161 --> 00:17:20,410
და თუ თქვენ გაინტერესებთ, რატომ
ჩვენი ნომრები ისე შემთხვევითი,

370
00:17:20,410 --> 00:17:24,150
ეს საყოველთაოდ მიღებული კომპიუტერული
მეცნიერებათა კურსები ჰარვარდის შემდეგ CS50.

371
00:17:24,150 --> 00:17:27,510
მაგრამ ეს იყო კარგი ოპტიმიზაცია,
რადგან ახლა მე არ გაყვანაა სივრცეში.

372
00:17:27,510 --> 00:17:30,750
მე მაინც უნდა გვახსოვდეს
რამდენად დიდი ეს რამ არის საერთო.

373
00:17:30,750 --> 00:17:31,500
ეს ხუთი შეადგენს.

374
00:17:31,500 --> 00:17:33,375
იმიტომ, რომ მე არ მინდა, რომ
დავიწყო overwriting 51.

375
00:17:33,375 --> 00:17:36,260
ასე რომ, ახლა მე ჯერ კიდევ გარეთ სივრცეში,
ასე რომ, იგივე პრობლემა, როგორც ადრე.

376
00:17:36,260 --> 00:17:39,140
მაგრამ თქვენ ხედავთ, როგორ ახლა
თქვენი კოდი, ალბათ,

377
00:17:39,140 --> 00:17:41,910
უნდა დაწეროს ცოტა მეტი
სირთულის, რომ მოხდეს.

378
00:17:41,910 --> 00:17:44,510
და სინამდვილეში, რა ოპერატორი
in C ალბათ საშუალებას

379
00:17:44,510 --> 00:17:48,110
თქვენ magically ამისათვის circularity?

380
00:17:48,110 --> 00:17:50,160
ჰო modulo ოპერატორი,
პროცენტი ნიშანი.

381
00:17:50,160 --> 00:17:53,160
ასე რომ, რა სახის მაგარი მდგომ,
მიუხედავად იმისა, რომ ჩვენ შევინარჩუნოთ ხატვის კოლექტორები

382
00:17:53,160 --> 00:17:56,520
როგორც ეს, როგორც სწორი ხაზები, თუ
სახის ვიფიქროთ, რომ ეს curving

383
00:17:56,520 --> 00:18:00,341
გარშემო წრე, მაშინ მხოლოდ
ინტუიციურად ეს ერთგვარი მუშაობს გონებრივად

384
00:18:00,341 --> 00:18:01,590
მე ვფიქრობ, რომ ცოტა მეტი cleanly.

385
00:18:01,590 --> 00:18:05,190
თქვენ მაინც უნდა განახორციელოს
რომ ფსიქიკური მოდელის კოდი.

386
00:18:05,190 --> 00:18:07,550
ასე რომ, არ არის რთული,
საბოლოო ჯამში, განხორციელება,

387
00:18:07,550 --> 00:18:12,430
მაგრამ ჩვენ მაინც დაკარგავს ზომა უფრო სწორად,
უნარი ზომის შეცვლა, თუ ჩვენ ამის გაკეთება.

388
00:18:12,430 --> 00:18:15,310
>> ჩვენ უნდა დავაღწიოთ მასივი, ჩვენ
შეცვალოს იგი ერთი მაჩვენებელი,

389
00:18:15,310 --> 00:18:20,010
და მერე სადღაც ჩემი კოდი მაქვს
გამოძახების რა ფუნქცია რეალურად შექმნა

390
00:18:20,010 --> 00:18:23,720
მასივი მოუწოდა ნომრები?

391
00:18:23,720 --> 00:18:26,190
Malloc, ან რაღაც მსგავსი
ფუნქცია, ზუსტად.

392
00:18:26,190 --> 00:18:30,481
ნებისმიერი კითხვები stacks და რიგები.

393
00:18:30,481 --> 00:18:30,980
ჰო?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
კარგი კითხვაა.

396
00:18:34,240 --> 00:18:35,830
რა modulo თქვენ იყენებთ აქ.

397
00:18:35,830 --> 00:18:38,520
ასე რომ, ზოგადად, როდესაც გამოყენებით
mod, თქვენ ამის გაკეთება

398
00:18:38,520 --> 00:18:40,620
ერთად ზომა
მთელი მონაცემები სტრუქტურა.

399
00:18:40,620 --> 00:18:44,120
ასე რომ რაღაც ხუთი ან მოცულობა, თუ
ეს მუდმივი, ალბათ ჩართული.

400
00:18:44,120 --> 00:18:47,100
მაგრამ მხოლოდ ამით modulo ხუთ
ალბათ, არ არის საკმარისი,

401
00:18:47,100 --> 00:18:51,380
იმიტომ, რომ ჩვენ უნდა ვიცოდეთ, რომ ჩვენ
გადაიტანოთ გარშემო აქ ან აქ ან აქ.

402
00:18:51,380 --> 00:18:54,160
ასე რომ, თქვენ, ალბათ, ასევე
აპირებს მინდა ჩართვა

403
00:18:54,160 --> 00:18:57,220
ზომა რამ, ან
წინა ცვლადი ასევე.

404
00:18:57,220 --> 00:19:00,140
ასე რომ, ეს მხოლოდ ამ შედარებით
მარტივი არითმეტიკული გამოხატვის,

405
00:19:00,140 --> 00:19:02,000
მაგრამ modulo იქნება ძირითადი ნივთიერება.

406
00:19:02,000 --> 00:19:03,330
>> ასე მოკლე ფილმი თუ გნებავთ.

407
00:19:03,330 --> 00:19:05,780
ანიმაცია, რომ ზოგიერთი
ეგ სხვა უნივერსიტეტში

408
00:19:05,780 --> 00:19:08,060
ერთად რომ ჩვენ
ადაპტირებული ამ დისკუსიაში.

409
00:19:08,060 --> 00:19:12,630
იგი მოიცავს ჯეკ სასწავლო
ფაქტები რიგები და სტატისტიკა.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> ფილმი: ერთხელ,
იყო ბიჭი სახელად ჯეკ.

412
00:19:21,890 --> 00:19:25,330
როდესაც საქმე მიღების მეგობრები,
Jack არ აქვს knack.

413
00:19:25,330 --> 00:19:28,220
ასე რომ, ჯეკ წავიდა გაიგო
ყველაზე პოპულარული ბიჭი იცოდა.

414
00:19:28,220 --> 00:19:30,920
წავიდა Lou და სთხოვა, რა გავაკეთო?

415
00:19:30,920 --> 00:19:33,400
Lou დაინახა, რომ მის მეგობარს
ნამდვილად შეწუხდა.

416
00:19:33,400 --> 00:19:36,050
ისე, მან დაიწყო, უბრალოდ,
შევხედოთ, თუ როგორ თქვენ ჩაცმული.

417
00:19:36,050 --> 00:19:38,680
ნუ თქვენ გაქვთ რაიმე ტანსაცმელი
სხვადასხვა სახეს?

418
00:19:38,680 --> 00:19:39,660
დიახ, განაცხადა ჯეკ.

419
00:19:39,660 --> 00:19:40,840
მე დარწმუნებული ვარ, ამის გაკეთება.

420
00:19:40,840 --> 00:19:43,320
მოვიდა ჩემს სახლში და
მე გაჩვენებთ მათ თქვენ.

421
00:19:43,320 --> 00:19:44,550
ასე რომ, ისინი წავიდნენ ჯეკ.

422
00:19:44,550 --> 00:19:47,520
და ჯეკ აჩვენა Lou ყუთი
სადაც იგი ინახება ყველა მისი მაისური,

423
00:19:47,520 --> 00:19:49,260
და მისი შარვალი და მისი წინდები.

424
00:19:49,260 --> 00:19:52,290
Lou განაცხადა, მე ვხედავ, თქვენ უნდა
ყველა თქვენი ტანსაცმელი წყობის.

425
00:19:52,290 --> 00:19:54,870
რატომ არ აცვიათ გარკვეული
სხვები ერთხელ awhile?

426
00:19:54,870 --> 00:19:58,020
>> ჯეკ განაცხადა, ასევე, როდესაც მე
ამოიღონ ტანსაცმელი და წინდები,

427
00:19:58,020 --> 00:20:00,780
მე დაიბანეთ მათ და ამით
მათ მოშორებით ყუთში.

428
00:20:00,780 --> 00:20:03,210
შემდეგ მოდის შემდეგი
დილით, და მე hop.

429
00:20:03,210 --> 00:20:06,380
მე წასვლა ყუთი და მიიღეთ
ჩემი ტანსაცმელი off დაბრუნება.

430
00:20:06,380 --> 00:20:09,070
Lou სწრაფად მიხვდა,
პრობლემა ჯეკ.

431
00:20:09,070 --> 00:20:12,080
მან გადაარჩინა ტანსაცმელი, CD- ს,
და წიგნები Stack.

432
00:20:12,080 --> 00:20:14,420
როდესაც მან მიაღწია
რაღაც იკითხება ან აცვიათ,

433
00:20:14,420 --> 00:20:17,100
ის მინდა აირჩიოს საუკეთესო წიგნი ან საცვლების.

434
00:20:17,100 --> 00:20:19,500
მაშინ, როდესაც ის იყო, მან
მისთვის უფლება უკან.

435
00:20:19,500 --> 00:20:21,970
უკან ის წავიდოდა, თავზე Stack.

436
00:20:21,970 --> 00:20:24,460
მე ვიცი გამოსავალი,
განაცხადა ტრიუმფალური Loud.

437
00:20:24,460 --> 00:20:27,090
თქვენ უნდა ვისწავლოთ
დაიწყოს გამოყენებით რიგი.

438
00:20:27,090 --> 00:20:29,870
Lou მიიღო ჯეკ ტანსაცმელი და
ეკიდა მათ კარადა.

439
00:20:29,870 --> 00:20:32,710
და როდესაც მან დაიცალა
ყუთი, ის უბრალოდ არ გაიზიარა იგი.

440
00:20:32,710 --> 00:20:36,500
>> ამის შემდეგ მან განაცხადა, ახლა ჯეკ, ბოლოს
დღეს, თქვენს ტანსაცმელი მარცხენა

441
00:20:36,500 --> 00:20:37,990
როცა ისინი მოშორებით.

442
00:20:37,990 --> 00:20:41,300
მაშინ ხვალ დილით, როდესაც თქვენ
ვხედავ sunshine, თქვენი ტანსაცმელი

443
00:20:41,300 --> 00:20:43,440
მარჯვენა ბოლოს ხაზი.

444
00:20:43,440 --> 00:20:44,880
არ ხედავთ? განაცხადა Lou.

445
00:20:44,880 --> 00:20:46,370
ეს იქნება ასე ლამაზი.

446
00:20:46,370 --> 00:20:49,770
თქვენ აცვიათ ყველაფერი ერთხელ
სანამ აცვიათ რაღაც ორჯერ.

447
00:20:49,770 --> 00:20:52,670
და ყველაფერი რიგები
მისი კარადა და თარო,

448
00:20:52,670 --> 00:20:55,160
ჯეკ დაიწყო გრძნობს
დანამდვილებით თავს.

449
00:20:55,160 --> 00:20:59,720
ყველა წყალობით Lou და
მისი მშვენიერი რიგიდან.

450
00:20:59,720 --> 00:21:01,220
დინამიკები 1: ყველა უფლება, ეს adorable.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
ასე რომ, რაც უკვე მართლაც აპირებს
ქვეშ hood ახლა?

453
00:21:10,080 --> 00:21:12,370
რომ ჩვენ გვაქვს პოინტერები,
რომ ჩვენ გვაქვს malloc,

454
00:21:12,370 --> 00:21:15,680
რომ ჩვენ გვაქვს შესაძლებლობა, რომ შევქმნათ
მოცულობით მეხსიერება საკუთარ თავს

455
00:21:15,680 --> 00:21:16,344
დინამიურად ვითარდება.

456
00:21:16,344 --> 00:21:18,510
ასე რომ, ეს არის სურათი ჩვენ
glimpsed მხოლოდ მეორე დღეს.

457
00:21:18,510 --> 00:21:21,180
ჩვენ ნამდვილად არ არენაზე
მასზე, მაგრამ ეს სურათი

458
00:21:21,180 --> 00:21:24,180
უკვე მიმდინარეობს ქვეშ
კაპოტის for კვირაა.

459
00:21:24,180 --> 00:21:27,050
ასე რომ, ეს წარმოადგენს, უბრალოდ
მართკუთხედი, რომ ჩვენ შედგენილი,

460
00:21:27,050 --> 00:21:28,180
თქვენი კომპიუტერის მეხსიერებაში.

461
00:21:28,180 --> 00:21:31,850
და, შესაძლოა, თქვენს კომპიუტერში, ან CS50
ID, აქვს Gigabyte მეხსიერების ან RAM

462
00:21:31,850 --> 00:21:33,050
ან ორი გიგაბაიტი ან ოთხ.

463
00:21:33,050 --> 00:21:34,450
ეს ნამდვილად არ აქვს.

464
00:21:34,450 --> 00:21:37,240
თქვენი ოპერაციული სისტემა
Windows და Mac OS და Linux,

465
00:21:37,240 --> 00:21:41,120
არსებითად საშუალებას თქვენი პროგრამა
ვფიქრობ, რომ მას აქვს დაშვება

466
00:21:41,120 --> 00:21:42,982
რომ მთლიანად
თქვენი კომპიუტერის მეხსიერების,

467
00:21:42,982 --> 00:21:45,440
მიუხედავად იმისა, რომ თქვენ შეიძლება იყოს გაშვებული
სხვადასხვა პროგრამები ერთდროულად.

468
00:21:45,440 --> 00:21:46,990
ასე რომ, რეალურად, რომ ნამდვილად არ იმუშავებს.

469
00:21:46,990 --> 00:21:49,448
მაგრამ ეს ერთგვარი ილუზია,
მოცემული ყველა თქვენი პროგრამები.

470
00:21:49,448 --> 00:21:53,110
ასე რომ, თუ თქვენ ორი gigs of RAM, ამ
არის, თუ როგორ კომპიუტერი შეიძლება ვიფიქროთ, რომ ეს.

471
00:21:53,110 --> 00:21:57,110
>> ახლა ერთსა, ერთ-ერთი ასეთი
რამ, ერთი ამ სეგმენტების მეხსიერება,

472
00:21:57,110 --> 00:21:58,350
ეწოდება Stack.

473
00:21:58,350 --> 00:22:01,680
და მართლაც, ნებისმიერ დროს
დღემდე წერილობით კოდი

474
00:22:01,680 --> 00:22:05,900
რომ თქვენ არ მოუწოდა
ფუნქცია, მაგალითად მთავარი.

475
00:22:05,900 --> 00:22:08,410
შეგახსენებთ, რომ ნებისმიერ დროს მე
შედგენილი კომპიუტერის მეხსიერებაში,

476
00:22:08,410 --> 00:22:10,640
მე ყოველთვის მიაპყროს სახის
ნახევარი მართკუთხედი აქ

477
00:22:10,640 --> 00:22:12,520
და არ გადაიტვირთოთ საუბარი
რა არის ზემოთ.

478
00:22:12,520 --> 00:22:15,980
იმის გამო, რომ მაშინ, როდესაც მთავარი ჰქვია, მე პრეტენზია
რომ თქვენ ამ კუთხეში მეხსიერება

479
00:22:15,980 --> 00:22:16,970
რომ მიდის ქვემოთ აქ.

480
00:22:16,970 --> 00:22:20,650
და თუ მთავარი მოუწოდა ფუნქცია
ისევე როგორც swap, ასევე swap მიდის აქ.

481
00:22:20,650 --> 00:22:23,720
და აღმოჩნდება, რომ
სადაც ის დამთავრებული.

482
00:22:23,720 --> 00:22:26,277
რაღაც მოუწოდა დასტის
შიგნით თქვენი კომპიუტერის მეხსიერებაში.

483
00:22:26,277 --> 00:22:28,360
ახლა დასასრულს დღეს,
ეს არის მხოლოდ მიმართავს.

484
00:22:28,360 --> 00:22:30,680
ეს იგივეა, byte ნულოვანი,
byte ერთი, byte 2 მლრდ.

485
00:22:30,680 --> 00:22:33,130
მაგრამ თუ ფიქრობთ, რომ ეს
როგორც ამ მართკუთხა ობიექტი,

486
00:22:33,130 --> 00:22:35,130
ყველა ვაკეთებთ ყოველ
ჩვენ მოვუწოდებთ ფუნქცია

487
00:22:35,130 --> 00:22:37,180
layering ახალი ნაჭერი მეხსიერება.

488
00:22:37,180 --> 00:22:41,700
ჩვენ ვაძლევთ, რომ ფუნქცია ნაჭერი
საკუთარი მეხსიერება მუშაობა.

489
00:22:41,700 --> 00:22:44,490
>> და გავიხსენოთ, ახლა, რომ ეს არის მნიშვნელოვანი.

490
00:22:44,490 --> 00:22:46,400
იმიტომ, რომ თუ ჩვენ გვაქვს
რაღაც swap

491
00:22:46,400 --> 00:22:51,610
და ორი ადგილობრივი ცვლადები, როგორიც A, B და
ჩვენ შეცვლის იმ ღირებულებებს, ერთი და ორი

492
00:22:51,610 --> 00:22:55,130
ორი და ერთი, გავიხსენოთ
რომ როდესაც swap ბრუნდება,

493
00:22:55,130 --> 00:22:58,330
ეს თითქოს ამ ნაჭერი
მეხსიერების უბრალოდ გაქრა.

494
00:22:58,330 --> 00:23:00,080
სინამდვილეში, ეს ჯერ კიდევ
არ forensically.

495
00:23:00,080 --> 00:23:01,940
და რაღაც მაინც რეალურად არსებობს.

496
00:23:01,940 --> 00:23:05,410
მაგრამ კონცეპტუალურად, ეს როგორც
მიუხედავად იმისა, რომ ის მთლიანად გაქრა.

497
00:23:05,410 --> 00:23:10,910
ასე რომ, მთავარი არ ვიცი არც ერთი სამუშაო
რომ გაკეთდა, რომ swap ფუნქციის,

498
00:23:10,910 --> 00:23:14,890
თუ ეს რეალურად გაიარა იმ
არგუმენტები მაჩვენებელი ან მითითებით.

499
00:23:14,890 --> 00:23:17,790
ახლა, ფუნდამენტური გადაწყვეტა
რომ პრობლემა swap

500
00:23:17,790 --> 00:23:19,970
გადის რამ by მისამართზე.

501
00:23:19,970 --> 00:23:23,250
მაგრამ აღმოჩნდება, ძალიან, რა არის
უკვე მიმდინარეობს, რომ ზემოთ ნაწილი

502
00:23:23,250 --> 00:23:26,330
მართკუთხედის ყველა ამ დროს
ჯერ არ არის მეტი მეხსიერების არსებობს.

503
00:23:26,330 --> 00:23:28,790
და როცა დინამიურად
გამოყოს მეხსიერება,

504
00:23:28,790 --> 00:23:32,020
არის თუ არა ეს შიგნით GetString, რომელიც
ჩვენ ვაკეთებთ თქვენთვის CS50

505
00:23:32,020 --> 00:23:34,710
ბიბლიოთეკა, ან, თუ ბიჭები
მოვუწოდებთ malloc და ვთხოვ

506
00:23:34,710 --> 00:23:37,950
ოპერაციული სისტემა ბლოკი
მეხსიერება, ეს არ მოდის Stack.

507
00:23:37,950 --> 00:23:40,960
მას გააჩნია სხვა ადგილას
თქვენი კომპიუტერის მეხსიერების

508
00:23:40,960 --> 00:23:42,220
რომ მოუწოდა ბევრი.

509
00:23:42,220 --> 00:23:43,430
და ეს არ არის რაიმე განსხვავებული.

510
00:23:43,430 --> 00:23:44,285
ეს იგივეა, რაც მეხსიერება.

511
00:23:44,285 --> 00:23:45,160
ეს იგივეა, რაც მეხსიერება.

512
00:23:45,160 --> 00:23:49,080
უბრალოდ RAM რომ მდე
იქ ნაცვლად ქვემოთ აქ.

513
00:23:49,080 --> 00:23:50,750
>> ასე რომ, რას ნიშნავს ეს?

514
00:23:50,750 --> 00:23:53,650
ისე, თუ თქვენი კომპიუტერი
სასრული რაოდენობით მეხსიერება

515
00:23:53,650 --> 00:23:57,450
და დასტის იზრდებოდა, ასე რომ
ვთქვათ, და ბევრი, შესაბამისად

516
00:23:57,450 --> 00:23:59,349
ამ arrow, იზრდება down.

517
00:23:59,349 --> 00:24:01,140
სხვა სიტყვებით, ყოველ
მოვუწოდებთ malloc,

518
00:24:01,140 --> 00:24:03,430
თქვენ უტარდება ნაჭერი
მეხსიერების ზემოდან,

519
00:24:03,430 --> 00:24:06,630
მაშინ იქნებ ცოტა დაბალია, მაშინ პატარა
ქვედა, ყოველ ჯერზე რეკავთ malloc,

520
00:24:06,630 --> 00:24:10,100
ბევრი, მისი გამოყენება,
არის სახის იზრდება,

521
00:24:10,100 --> 00:24:11,950
უფრო და უფრო უახლოვდება, თუ რა?

522
00:24:11,950 --> 00:24:13,382
დასტის.

523
00:24:13,382 --> 00:24:14,840
ასე რომ, ჯერ ეს, როგორც ჩანს, კარგი იდეა?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
ვგულისხმობ, სადაც ეს ნამდვილად არ არის ნათელი
რა შეგიძლიათ გააკეთოთ, თუ თქვენ მხოლოდ

526
00:24:22,140 --> 00:24:23,910
აქვს სასრული რაოდენობით მეხსიერება.

527
00:24:23,910 --> 00:24:25,200
მაგრამ ეს არ არის აუცილებლად ცუდი.

528
00:24:25,200 --> 00:24:27,920
ეს ორი ისრებით წლის
ავარიის რა თქმა უნდა, ერთმანეთს.

529
00:24:27,920 --> 00:24:31,930
>> და აღმოჩნდება, რომ ცუდი ბიჭი, დაკარგულია
განსაკუთრებით კარგი პროგრამირების,

530
00:24:31,930 --> 00:24:36,140
და ცდილობენ hack კომპიუტერები,
შეიძლება გამოეყენებინათ ეს რეალობა.

531
00:24:36,140 --> 00:24:38,290
ფაქტობრივად, განვიხილოთ
პატარა მონაკვეთში.

532
00:24:38,290 --> 00:24:41,350
ასე რომ, ეს არის მაგალითი შეგიძლიათ წაიკითხოთ
შესახებ უფრო დეტალურად ვიკიპედიაში.

533
00:24:41,350 --> 00:24:43,100
ჩვენ აღვნიშნო, რომ თქვენ დროს
სტატია თუ აინტერესებს.

534
00:24:43,100 --> 00:24:45,650
მაგრამ არსებობს თავდასხმის ზოგადად
ცნობილია, როგორც ბუფერული overflow რომ

535
00:24:45,650 --> 00:24:49,570
არსებობდა, რადგან ადამიანები
არ ჰქონდა უნარი მანიპულირება

536
00:24:49,570 --> 00:24:53,120
კომპიუტერის მეხსიერებაში, განსაკუთრებით C.
ასე რომ, ეს არის ძალიან თვითნებური პროგრამა,

537
00:24:53,120 --> 00:24:55,130
მაგრამ მოდით წაიკითხავს ბოლოში მდე.

538
00:24:55,130 --> 00:24:57,650
მთავარი შევიდა Argc char ვარსკვლავი argv.

539
00:24:57,650 --> 00:24:59,830
ასე რომ, ეს პროგრამა, რომელიც იღებს
ბრძანების ხაზი არგუმენტები.

540
00:24:59,830 --> 00:25:03,620
და ყველა ძირითადი -ს, როგორც ჩანს, დარეკეთ
ფუნქცია, მას F სიმარტივის.

541
00:25:03,620 --> 00:25:04,610
და ეს გადის რა?

542
00:25:04,610 --> 00:25:05,490
Argv ერთი.

543
00:25:05,490 --> 00:25:09,320
ასე გადის F რასაც
სიტყვა, რომელიც მომხმარებლის აკრეფილი

544
00:25:09,320 --> 00:25:11,500
ზოლზე შემდეგ
პროგრამის სახელწოდება ყველა.

545
00:25:11,500 --> 00:25:15,730
ასე რომ ჰგავს Caesar ან Vigenere, რომელიც
თქვენ ალბათ გახსოვთ აკეთებს argv.

546
00:25:15,730 --> 00:25:16,680
>> რა არის F?

547
00:25:16,680 --> 00:25:19,760
F იღებს სიმებიანი
როგორც მისი ერთადერთი არგუმენტი,

548
00:25:19,760 --> 00:25:22,100
AKA char ვარსკვლავი, იგივე
რამ, როგორც სიმებიანი.

549
00:25:22,100 --> 00:25:24,920
და ეს ე.წ. თვითნებურად
ბარი ამ მაგალითს.

550
00:25:24,920 --> 00:25:27,710
და მაშინ char c 12
მხოლოდ ერისკაცად წარმოგვიდგება მისი თვალსაზრისით,

551
00:25:27,710 --> 00:25:31,750
რა არის char გ bracket 12 აკეთებენ?

552
00:25:31,750 --> 00:25:33,440
რა გავაკეთოთ?

553
00:25:33,440 --> 00:25:36,490
გამოყოფის მეხსიერება, კონკრეტულად
12 ბაიტი, 12 სიმბოლო.

554
00:25:36,490 --> 00:25:36,990
ზუსტად.

555
00:25:36,990 --> 00:25:40,000
და შემდეგ ბოლო ხაზი, აურიეთ და
ასლი, თქვენ ალბათ არ მინახავს.

556
00:25:40,000 --> 00:25:43,360
ეს არის ტექსტი ასლი
ფუნქცია, რომლის მიზანი ცხოვრებაში

557
00:25:43,360 --> 00:25:48,160
კოპირება მეორე არგუმენტი
მისი პირველი არგუმენტი,

558
00:25:48,160 --> 00:25:51,190
მაგრამ მხოლოდ ერთი
გარკვეული რაოდენობის ბაიტი.

559
00:25:51,190 --> 00:25:53,860
ასე რომ, მესამე არგუმენტი ამბობს,
რამდენი ბაიტი უნდა ასლი?

560
00:25:53,860 --> 00:25:56,720
ხანგრძლივობა ბარი,
რასაც მომხმარებლის აკრეფილი.

561
00:25:56,720 --> 00:25:59,320
და შინაარსი
ბარი, რომ ტექსტი, არიან

562
00:25:59,320 --> 00:26:02,330
გადაწერა ხსოვნას აღნიშნა ზე C.

563
00:26:02,330 --> 00:26:04,060
>> ასე რომ, ეს, როგორც ჩანს, ასეთი სულელური, და ეს არის.

564
00:26:04,060 --> 00:26:06,300
ეს არის contrived მაგალითად,
მაგრამ ის წარმომადგენელი

565
00:26:06,300 --> 00:26:10,100
კლასის თავდასხმის ვექტორები,
გზა თავდასხმაში პროგრამა.

566
00:26:10,100 --> 00:26:15,050
ყველა კარგად არის და კარგი, თუ მომხმარებელი
სახის სიტყვა, რომელიც არის 11 პერსონაჟი

567
00:26:15,050 --> 00:26:18,040
ან ნაკლები, ასევე წარმატებული ნულოვანი.

568
00:26:18,040 --> 00:26:22,830
რა მოხდება, თუ მომხმარებლის ტიპების მეტი ვიდრე
11 ან 12 ან 20 ან 50 სიმბოლო?

569
00:26:22,830 --> 00:26:25,090
რა არის ამ პროგრამის აპირებს?

570
00:26:25,090 --> 00:26:29,360
პოტენციურად seg ბრალია. ის აპირებს
ბრმად კოპირება ყველაფერი ბარი

571
00:26:29,360 --> 00:26:31,750
მისი სიგრძე, რომელიც არის
ფაქტიურად ყველაფერი ბარი,

572
00:26:31,750 --> 00:26:36,307
შევიდა მისამართი მიუთითა C. მაგრამ C
მხოლოდ წინასწარ მოცემული, როგორც 12 ბაიტი.

573
00:26:36,307 --> 00:26:37,640
მაგრამ არ არსებობს დამატებითი ქვითარი.

574
00:26:37,640 --> 00:26:38,700
იქ არ არის, თუ პირობები.

575
00:26:38,700 --> 00:26:40,580
არ არსებობს შეცდომა შემოწმების აქ.

576
00:26:40,580 --> 00:26:43,270
>> ასე რომ, რა არის, ეს პროგრამა
ვაპირებ ამის გაკეთებას, უბრალოდ ბრმად

577
00:26:43,270 --> 00:26:45,750
ასლი ერთი რამ სხვა.

578
00:26:45,750 --> 00:26:47,880
ასე რომ, თუ ჩვენ გავამახვილო ეს
როგორც სურათზე, აქ

579
00:26:47,880 --> 00:26:49,860
უბრალოდ კუთხეში მეხსიერების სივრცე.

580
00:26:49,860 --> 00:26:53,470
ასე რომ შეამჩნია ბოლოში, ჩვენ
აქვს ადგილობრივი ცვლადი ბარი.

581
00:26:53,470 --> 00:26:57,330
ასე რომ კურსორი, რომელიც აპირებს store--
უფრო სწორად, რომ ადგილობრივი არგუმენტი რომ

582
00:26:57,330 --> 00:26:58,672
აპირებს შესანახად სიმებიანი ბარი.

583
00:26:58,672 --> 00:27:00,380
და მაშინ შეამჩნია მხოლოდ
ზემოთ ის დასტის,

584
00:27:00,380 --> 00:27:02,505
რადგან ყოველ ჯერზე თქვენ ვთხოვო
მეხსიერების დასტის,

585
00:27:02,505 --> 00:27:04,310
ის მიდის ცოტა
ზემოთ ის ილუსტრირებული,

586
00:27:04,310 --> 00:27:06,270
ცნობა, რომ ჩვენ მივიღეთ 12 ბაიტი არსებობს.

587
00:27:06,270 --> 00:27:10,690
ზედა მარცხენა ერთი C bracket ნულოვანი და
ქვედა მარჯვენა ერთი არის C bracket 11.

588
00:27:10,690 --> 00:27:12,870
ეს არის ის, თუ რამდენად კომპიუტერები
ჩაუყარა ის.

589
00:27:12,870 --> 00:27:18,300
ასე რომ მხოლოდ ინტუიციურად, თუ ბარი აქვს მეტი
ვიდრე 12 სიმბოლო სულ, მათ შორის,

590
00:27:18,300 --> 00:27:25,790
წარმატებული ნულოვანი, სადაც არის
12 ან C bracket 12 აპირებს?

591
00:27:25,790 --> 00:27:28,440
უფრო სწორად, სადაც არის 12
ხასიათი და მე -13 ხასიათი,

592
00:27:28,440 --> 00:27:30,900
მეასედ ხასიათი აპირებს
უნდა დამთავრდეს ამ სურათზე?

593
00:27:30,900 --> 00:27:33,400
ზემოთ ან ქვემოთ?

594
00:27:33,400 --> 00:27:36,300
>> მარჯვენა, რადგან მიუხედავად იმისა, რომ
დასტის თავად იზრდება წლიდან მოყოლებული,

595
00:27:36,300 --> 00:27:39,590
ერთხელ თქვენ დააყენა პერსონალი
ის, რომ ეს დიზაინი მიზეზების გამო,

596
00:27:39,590 --> 00:27:41,294
აყენებს მეხსიერების ზემოდან.

597
00:27:41,294 --> 00:27:44,460
ასე რომ, თუ თქვენ მოხვდით მეტი ვიდრე 12 ბაიტი,
თქვენ აპირებს დაიწყოს გადაწერა ბარი.

598
00:27:44,460 --> 00:27:47,280
ახლა რომ შეცდომაა, მაგრამ ეს
ნამდვილად არ არის დიდი გარიგება.

599
00:27:47,280 --> 00:27:51,130
მაგრამ ეს არის დიდი გარიგება, რადგან იქ
უფრო პერსონალის მიმდინარეობს მეხსიერებაში.

600
00:27:51,130 --> 00:27:53,074
ასე რომ, აქ როგორ შეიძლება
ბოლო hello, უნდა იყოს ნათელი.

601
00:27:53,074 --> 00:27:54,490
თუ მე აკრეფილი მიესალმები ზოლზე.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O წარმატებული ნულოვანი, მთავრდება ფარგლებში
იმ 12 ბაიტი, და ჩვენ სუპერ უსაფრთხო.

603
00:27:59,330 --> 00:28:00,330
ყველაფერი კარგად არის.

604
00:28:00,330 --> 00:28:03,020
მაგრამ თუ მე აკრიფოთ რაღაც
აღარ, პოტენციურად ეს

605
00:28:03,020 --> 00:28:05,860
აპირებს შემოგეპაროთ შევიდა ბარი სივრცეში.

606
00:28:05,860 --> 00:28:08,405
მაგრამ უარესი არ არის, თურმე
ყველა ამ დროს,

607
00:28:08,405 --> 00:28:11,530
მიუხედავად იმისა, რომ ჩვენ არასდროს არ ისაუბრა
ის, დასტის გამოიყენება სხვა პერსონალი.

608
00:28:11,530 --> 00:28:13,560
ეს არ არის მხოლოდ ადგილობრივი ცვლადები.

609
00:28:13,560 --> 00:28:15,100
>> C არის ძალიან დაბალი დონე ენაზე.

610
00:28:15,100 --> 00:28:17,810
და ეს ერთგვარი ფარულად
იყენებს დასტის ასევე

611
00:28:17,810 --> 00:28:21,260
უნდა გვახსოვდეს, როდესაც
ფუნქცია ეწოდება, რა

612
00:28:21,260 --> 00:28:26,040
მისამართი არის წინა ფუნქცია,
ასე რომ მას შეუძლია ხტომა უკან რომ ფუნქცია.

613
00:28:26,040 --> 00:28:29,980
ასე რომ, როდესაც მთავარ მოუწოდებს სვოპ, მათ შორის
რამ აიძულა გადატანა დასტის

614
00:28:29,980 --> 00:28:34,380
არ არის მხოლოდ სვოპების ადგილობრივი ცვლადები,
ან მისი არგუმენტები, ასევე ფარულად მივიღებთ

615
00:28:34,380 --> 00:28:37,510
გადატანა დასტის წარმოდგენილი
წითელი ნაჭერი აქ,

616
00:28:37,510 --> 00:28:40,520
არის მისამართი მთავარი ფიზიკურად
თქვენს კომპიუტერის მეხსიერებაში,

617
00:28:40,520 --> 00:28:44,180
ასე რომ, როდესაც swap კეთდება, კომპიუტერი
იცის, რომ მე უნდა დაბრუნდეს მთავარი

618
00:28:44,180 --> 00:28:46,760
და დასრულდება შესრულებაში მთავარი ფუნქცია.

619
00:28:46,760 --> 00:28:51,960
ასე რომ, ეს საშიშია, ახლა, იმიტომ, რომ თუ
მომხმარებლის ტიპის კარგად ზე მეტი hello,

620
00:28:51,960 --> 00:28:57,030
ისეთი, რომ მომხმარებლის შეყვანის clobbers
ან overwrites, რომ წითელი განყოფილებიანი,

621
00:28:57,030 --> 00:28:59,820
ლოგიკურად თუ კომპიუტერის
მხოლოდ აპირებს ბრმად ვივარაუდოთ,

622
00:28:59,820 --> 00:29:03,830
რომ bytes, რომ წითელი ნაჭერი არის
მიმართვაში, რომელიც მას უნდა დაუბრუნდეს,

623
00:29:03,830 --> 00:29:09,020
რა მოხდება, თუ მოწინააღმდეგე არის ჭკვიანი საკმარისი და
იღბლიანი საკმარისი იმისათვის, რომ თანმიმდევრობა bytes

624
00:29:09,020 --> 00:29:13,450
იქ რომ ჰგავს მისამართი,
მაგრამ ეს მისამართი კოდი

625
00:29:13,450 --> 00:29:18,730
რომ მას სურს კომპიუტერული
შეასრულოს ნაცვლად მთავარი?

626
00:29:18,730 --> 00:29:21,670
>> სხვა სიტყვებით, თუ რა
მომხმარებლის აკრეფის დროს სწრაფი,

627
00:29:21,670 --> 00:29:23,850
არ არის რაღაც
უწყინარი, როგორც hello,

628
00:29:23,850 --> 00:29:28,210
მაგრამ სინამდვილეში კოდი, რომელიც ექვივალენტურია
წაშლა ყველა ამ მომხმარებლის ფაილი?

629
00:29:28,210 --> 00:29:30,060
ან ელ მათი დაგავიწყდათ ჩემთვის?

630
00:29:30,060 --> 00:29:31,940
ან დაიწყოს ხე მათი
keystrokes, არა?

631
00:29:31,940 --> 00:29:34,920
არის გზა, მოდით ითვალისწინებს, დღეს,
რომ მათ შეეძლოთ ჩაწერეთ არა მხოლოდ მიესალმები

632
00:29:34,920 --> 00:29:36,711
მსოფლიოში და მათი სახელი,
მათ შეეძლოთ არსებითად

633
00:29:36,711 --> 00:29:39,570
გაივლის კოდი, zeros და
პირობა, რომ კომპიუტერი

634
00:29:39,570 --> 00:29:43,450
შეცდომები ორივე კოდი და მისამართი.

635
00:29:43,450 --> 00:29:48,950
ასე რომ, თუმცა გარკვეულწილად აბსტრაქტულად, თუ
მომხმარებლის სახის საკმარისი შეჯიბრებითობის კოდი

636
00:29:48,950 --> 00:29:52,330
ის, რომ ჩვენ განზოგადება აქ,
ა არის შეტევა და მოწინააღმდეგეებს.

637
00:29:52,330 --> 00:29:53,140
ასე რომ, უბრალოდ ცუდი პერსონალი.

638
00:29:53,140 --> 00:29:55,306
ჩვენ არ აინტერესებს
ნომრები ან zeros და პირობა

639
00:29:55,306 --> 00:29:59,470
დღეს, მაგალითად, რომ თქვენ დასრულდება მდე
overwriting რომ წითელი განყოფილებიანი,

640
00:29:59,470 --> 00:30:01,580
შეამჩნია, რომ თანმიმდევრობა bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C ნულოვანი რვა ნულოვანი.

642
00:30:05,020 --> 00:30:08,960
და ახლა, როგორც ვიკიპედიის სტატია აქ
აქვს შემოთავაზებული, თუ ახლა რეალურად დაიწყოს

643
00:30:08,960 --> 00:30:12,460
ეტიკეტირების bytes თქვენი კომპიუტერის
მეხსიერება, თუ რა Wikipedia article არის

644
00:30:12,460 --> 00:30:19,060
შემოთავაზების არის, რომ, თუ მისამართი
რომ ზედა მარცხენა byte 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> სხვა სიტყვებით, თუ ცუდი ბიჭი არის
ჭკვიანი საკმარისი მის კოდი

646
00:30:22,200 --> 00:30:26,650
რეალურად დააყენოს ნომერი აქ
შეესაბამება მისამართი კოდი

647
00:30:26,650 --> 00:30:29,180
მას გაუკეთეს
კომპიუტერი, თქვენ

648
00:30:29,180 --> 00:30:31,050
შეგიძლიათ შეასრულა კომპიუტერული
შევიდა აკეთებს არაფერი.

649
00:30:31,050 --> 00:30:34,140
მოხსნის ფაილი, emailing
რამ, შესასუნთქი თქვენი მოძრაობის,

650
00:30:34,140 --> 00:30:36,710
ფაქტიურად არაფერი შეიძლება იყოს
გაუკეთეს შევიდა კომპიუტერი.

651
00:30:36,710 --> 00:30:39,220
ასე რომ ბუფერული overflow
თავდასხმის დროს მისი ძირითადი

652
00:30:39,220 --> 00:30:43,530
მხოლოდ სულელური, სულელური
ძალიან მნიშვნელოვანი მასივი, რომ

653
00:30:43,530 --> 00:30:45,840
არ აქვს საზღვრები გადამოწმებული.

654
00:30:45,840 --> 00:30:48,850
და ეს არის ის, რაც სუპერ სახიფათო
და ერთდროულად სუპერ ძლიერი

655
00:30:48,850 --> 00:30:52,560
C არის, რომ ჩვენ მართლაც აქვს
ხელმისაწვდომობის სადმე მეხსიერება.

656
00:30:52,560 --> 00:30:55,320
ეს ჩვენთვის, პროგრამისტების,
ვინც დაწერა ორიგინალური კოდი

657
00:30:55,320 --> 00:30:59,330
უნდა შეამოწმოს darn სიგრძე ნებისმიერი
კოლექტორები, რომ ჩვენ მანიპულირება.

658
00:30:59,330 --> 00:31:00,750
ასე უნდა იყოს მკაფიო, რა გადავწყვიტოთ?

659
00:31:00,750 --> 00:31:03,190
თუ ჩვენ გააფართოვოს უკან ამ
კოდი, მე არ უნდა უბრალოდ

660
00:31:03,190 --> 00:31:08,000
შეცვლის სიგრძეზე ბარი, რა
სხვა უნდა იყოს შემოწმება?

661
00:31:08,000 --> 00:31:10,620
რა უნდა მე უნდა აკეთებს
თავიდან ავიცილოთ ეს თავდასხმა მთლიანად?

662
00:31:10,620 --> 00:31:14,110
მე არ მინდა, რომ უბრალოდ ბრმად ამბობენ
რომ თქვენ უნდა დააკოპირეთ როგორც ბევრი bytes

663
00:31:14,110 --> 00:31:16,140
როგორც არის სიგრძეზე ბარი.

664
00:31:16,140 --> 00:31:18,910
მე მინდა ვთქვა, კოპირება
ბევრი bytes როგორც არის ბარი

665
00:31:18,910 --> 00:31:24,090
მდე გამოყოფილი
მეხსიერება, ან 12 მაქსიმალურად.

666
00:31:24,090 --> 00:31:27,450
ასე რომ, მე უნდა გარკვეული თუ მდგომარეობა
რომ არ შეამოწმოს სიგრძეზე ბარი,

667
00:31:27,450 --> 00:31:32,800
მაგრამ თუ იგი აღემატება 12, ჩვენ მხოლოდ მძიმე კოდი
12 მაქსიმალური მანძილი.

668
00:31:32,800 --> 00:31:35,910
წინააღმდეგ შემთხვევაში, ე.წ. ბუფერულ
overflow თავდასხმა შეიძლება მოხდეს.

669
00:31:35,910 --> 00:31:38,451
ბოლოში იმ სლაიდები,
თუ თქვენ საინტერესო ვრცლად

670
00:31:38,451 --> 00:31:41,200
ფაქტობრივი ორიგინალური სტატია
თუ გსურთ შევხედოთ.

671
00:31:41,200 --> 00:31:44,550
>> მაგრამ ახლა, მათ შორის ფასები
გადახდილი აქ იყო არაეფექტური.

672
00:31:44,550 --> 00:31:46,680
ასე რომ, სწრაფი
დაბალი დონე შევხედოთ რა

673
00:31:46,680 --> 00:31:49,709
პრობლემები შეიძლება წარმოიშვას, რომ ჩვენ
გვაქვს წვდომა კომპიუტერის მეხსიერებაში.

674
00:31:49,709 --> 00:31:51,750
მაგრამ კიდევ ერთი პრობლემა,
უკვე stumbled on ორშაბათი

675
00:31:51,750 --> 00:31:53,800
იყო მხოლოდ არაეფექტურობა
უკავშირდება სიაში.

676
00:31:53,800 --> 00:31:56,019
ჩვენ უკან ხაზოვანი დრო.

677
00:31:56,019 --> 00:31:57,560
ჩვენ უკვე აღარ გვაქვს მომიჯნავე მასივი.

678
00:31:57,560 --> 00:31:58,980
ჩვენ არ გვაქვს წვდომის.

679
00:31:58,980 --> 00:32:00,710
ჩვენ არ შეგვიძლია გამოვიყენოთ კვადრატული ფრჩხილი ნოტაცია.

680
00:32:00,710 --> 00:32:04,590
ჩვენ ფაქტიურად თავიდან უნდა გამოიყენოთ ხოლო მარყუჟის
როგორც დავწერე მომენტში წინ.

681
00:32:04,590 --> 00:32:09,740
მაგრამ ორშაბათს, ჩვენ ამტკიცებდა, რომ ჩვენ შეგვიძლია
Creep ისევ სფეროში ეფექტურობის

682
00:32:09,740 --> 00:32:13,040
მისაღწევად, რომ რაღაც
ლოგარითმული იქნებ, ან საუკეთესო არ არის,

683
00:32:13,040 --> 00:32:16,120
შესაძლოა, რომ რაღაც
ე.წ. მუდმივი დრო.

684
00:32:16,120 --> 00:32:19,840
მაშ, როგორ შეგვიძლია გავაკეთოთ, რომ გამოყენებით ამ ახალი
იარაღები, ამ მისამართები, ამ მითითებას,

685
00:32:19,840 --> 00:32:22,210
და threading რამ ჩვენი საკუთარი?

686
00:32:22,210 --> 00:32:23,960
ისე, ვფიქრობ, რომ
აქ, ეს არის bunch

687
00:32:23,960 --> 00:32:27,170
ციფრები, რომ ჩვენ გვინდა, რომ მაღაზიის
მონაცემები სტრუქტურა და ძებნის ეფექტურად.

688
00:32:27,170 --> 00:32:30,960
ჩვენ შეგვიძლია სრულიად გადახვევა კვირაში
ორი, იმისათვის, რომ ამ მასივი,

689
00:32:30,960 --> 00:32:33,150
და ძებნის მათი გამოყენებით ორობითი ძებნა.

690
00:32:33,150 --> 00:32:34,040
დაყავი და იბატონე.

691
00:32:34,040 --> 00:32:37,720
და სინამდვილეში, თქვენ დაწერა
ბინარული ძებნის pset3,

692
00:32:37,720 --> 00:32:40,100
სადაც თქვენ განხორციელებული იპოვოს პროგრამა.

693
00:32:40,100 --> 00:32:40,890
მაგრამ იცით, რა.

694
00:32:40,890 --> 00:32:45,060
აქ არის ერთგვარი უფრო
ჭკვიანი გზა ამით.

695
00:32:45,060 --> 00:32:47,390
ეს ცოტა მეტი
დახვეწილი და ეს, ალბათ,

696
00:32:47,390 --> 00:32:50,830
საშუალებას გვაძლევს, თუ რატომ ორობითი
ძიება იმდენად სწრაფად.

697
00:32:50,830 --> 00:32:52,980
პირველ რიგში, მოდით გააცნობს
ცნება ხე.

698
00:32:52,980 --> 00:32:54,730
რომელი მიუხედავად იმისა, რომ
რეალობა ხეები სახის

699
00:32:54,730 --> 00:32:57,730
იზრდება, როგორც ეს, მსოფლიოში კომპიუტერული
მეცნიერება ისინი სახის იზრდება ქვევით

700
00:32:57,730 --> 00:33:00,830
მოსწონს ოჯახის ხე, სადაც თქვენ უნდა
თქვენი ბებია ან დიდი ბებია და ბაბუა

701
00:33:00,830 --> 00:33:04,580
ან whatnot ზედა, პატრიარქს და
matriarch ოჯახის, მხოლოდ ერთი

702
00:33:04,580 --> 00:33:07,930
ე.წ. root, კვანძის, ქვემოთ
რომლებიც მისი შვილი,

703
00:33:07,930 --> 00:33:11,442
ქვემოთ რაც არის მისი შვილი, ან
მისი შთამომავლები უფრო ზოგადად.

704
00:33:11,442 --> 00:33:13,400
და ყველას ჩამოკიდებული off
ბოლოში ოჯახის

705
00:33:13,400 --> 00:33:16,070
ხე, გარდა იმისა, რომ
ახალგაზრდა ოჯახში,

706
00:33:16,070 --> 00:33:19,520
ასევე შეგიძლიათ უბრალოდ იყოს generically
ეწოდება ფოთლები ხე.

707
00:33:19,520 --> 00:33:21,800
>> ასე რომ, ეს მხოლოდ რამოდენიმე
სიტყვა და განმარტებები

708
00:33:21,800 --> 00:33:25,790
რაღაც მოუწოდა ხე კომპიუტერული
მეცნიერების, ჰგავს ოჯახის ხე.

709
00:33:25,790 --> 00:33:28,770
მაგრამ არსებობს fancier ინკარნაციაში
ხეები, რომელთაგან ერთ-ერთი

710
00:33:28,770 --> 00:33:30,780
ეწოდება ორობითი ძებნა ხე.

711
00:33:30,780 --> 00:33:34,380
და შეგიძლიათ სახის გაღიზიანება
გარდა რა ეს რამ აქვს.

712
00:33:34,380 --> 00:33:37,180
ისე, ეს ორობითი რა გაგებით?

713
00:33:37,180 --> 00:33:41,455
სად ორობითი მოდის აქ?

714
00:33:41,455 --> 00:33:41,955
ბოდიში?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
ეს არ არის იმდენად ან ან.

717
00:33:47,210 --> 00:33:52,000
ეს უფრო, რომ თითოეული კვანძების ვიზიტორების
მეტი ორი შვილი, როგორც ვხედავთ, აქ.

718
00:33:52,000 --> 00:33:54,990
ზოგადად, ხე და
თქვენი მშობლები და ბებია

719
00:33:54,990 --> 00:33:57,640
შეგიძლიათ იმდენი ბავშვები ან
შვილიშვილებს, რადგან ისინი რეალურად გვინდა,

720
00:33:57,640 --> 00:34:00,820
და ასე მაგალითად, ჩვენ გვაქვს სამი
ბავშვებს, რომ მარჯვენა ხელის კვანძი,

721
00:34:00,820 --> 00:34:05,480
მაგრამ ორობითი ხე, კვანძის აქვს
ნულოვანი, ერთი, ან ორი შვილი მაქსიმალურად.

722
00:34:05,480 --> 00:34:08,496
და ეს ლამაზი ქონება,
იმიტომ, რომ თუ ის capped მიერ ორი,

723
00:34:08,496 --> 00:34:10,620
ჩვენ ვაპირებთ, რომ შეძლებს
კიდევ ცოტა ჟურნალი ბაზა ორი

724
00:34:10,620 --> 00:34:11,975
მოქმედება ხდება აქ საბოლოოდ.

725
00:34:11,975 --> 00:34:13,350
ასე რომ, ჩვენ გვაქვს რაღაც ლოგარითმული.

726
00:34:13,350 --> 00:34:14,558
მაგრამ უფრო, რომ ამ მომენტში.

727
00:34:14,558 --> 00:34:19,810
ძებნა ხე იმას ნიშნავს, რომ ნომრები
მოწყობილი ასეთი, რომ მარცხენა ბავშვის

728
00:34:19,810 --> 00:34:22,429
მნიშვნელობა მეტია ძირი.

729
00:34:22,429 --> 00:34:26,010
და მისი უფლება ბავშვი
უფრო დიდი, ვიდრე root.

730
00:34:26,010 --> 00:34:29,290
სხვა სიტყვებით, თუ თქვენ მიიღოს ნებისმიერი
კვანძების, წრეები ამ სურათს,

731
00:34:29,290 --> 00:34:31,840
და უყურებს მისი მარცხენა
ბავშვი და მისი უფლება ბავშვს,

732
00:34:31,840 --> 00:34:34,739
პირველი ნაკლები უნდა იყოს,
მეორე უნდა იყოს მეტი.

733
00:34:34,739 --> 00:34:36,159
ასე რომ საღი აზრის ქვითარი 55.

734
00:34:36,159 --> 00:34:37,780
ეს მარცხენა ბავშვი არის 33.

735
00:34:37,780 --> 00:34:38,620
ეს არის ნაკლები.

736
00:34:38,620 --> 00:34:40,929
55, მისი სწორი შვილი არის 77.

737
00:34:40,929 --> 00:34:41,783
ეს უფრო მეტია, ვიდრე.

738
00:34:41,783 --> 00:34:43,199
და რომ რეკურსიული განმარტება.

739
00:34:43,199 --> 00:34:46,480
ჩვენ შეიძლება შეამოწმოს ყველა იმ
კვანძების და იგივე ნიმუში იქნებოდა გამართავს.

740
00:34:46,480 --> 00:34:49,389
>> ასე რომ, რა ლამაზი წელს
ორობითი ძებნა ხე, არის

741
00:34:49,389 --> 00:34:52,204
რომ ერთი, ჩვენ შეიძლება ეს
struct, ისევე, როგორც ეს.

742
00:34:52,204 --> 00:34:54,620
და მიუხედავად იმისა, ჩვენ სროლა
უამრავი სტრუქტურების თქვენი,

743
00:34:54,620 --> 00:34:56,560
ისინი გარკვეულწილად
ინტუიციური იმედია.

744
00:34:56,560 --> 00:35:00,570
სინტაქსი არის კიდევ arcane დარწმუნებული ვარ,
მაგრამ შინაარსი კვანძში ამ

745
00:35:00,570 --> 00:35:02,786
კონტექსტში და ჩვენ შევინარჩუნოთ
გამოყენებით სიტყვა კვანძის,

746
00:35:02,786 --> 00:35:04,910
არის თუ არა ეს მართკუთხედი
ეკრანზე ან წრე,

747
00:35:04,910 --> 00:35:08,970
ეს მხოლოდ რამდენიმე ზოგადი კონტეინერი,
ამ შემთხვევაში ხე, როგორც ერთი

748
00:35:08,970 --> 00:35:11,780
ჩვენ ვნახეთ, ჩვენ გვჭირდება რიცხვი
თითოეულ კვანძების

749
00:35:11,780 --> 00:35:15,460
და მერე უნდა ორ მითითებას მიუთითებს
მარცხენა ბავშვის და უფლება ბავშვი,

750
00:35:15,460 --> 00:35:16,590
შესაბამისად.

751
00:35:16,590 --> 00:35:20,730
ასე რომ, თუ როგორ შეიძლება
განახორციელოს, რომ struct.

752
00:35:20,730 --> 00:35:22,315
და როგორ შეიძლება მე განახორციელოს ეს კოდი?

753
00:35:22,315 --> 00:35:26,730
ისე, მოდით მიიღოს სწრაფი
შევხედოთ ამ პატარა მაგალითი.

754
00:35:26,730 --> 00:35:29,820
ეს არ არის ფუნქციონალური, მაგრამ მე
გადაწერა და გაკრული, რომ სტრუქტურა.

755
00:35:29,820 --> 00:35:33,510
და თუ ჩემი ფუნქცია ორობითი
ძებნა ხე ეწოდება ძიება,

756
00:35:33,510 --> 00:35:36,980
და ეს ხდება ორი არგუმენტები,
რიცხვი N და მომცეთ

757
00:35:36,980 --> 00:35:41,400
კვანძის, ასე მომცეთ ხე
ან მომცეთ ძირი ხე,

758
00:35:41,400 --> 00:35:43,482
როგორ შემიძლია წასვლა ეძებს N?

759
00:35:43,482 --> 00:35:45,440
პირველ რიგში, იმიტომ, რომ მე
საქმე მითითებას,

760
00:35:45,440 --> 00:35:46,750
მე ვაპირებ ამის საღი აზრის ქვითარი.

761
00:35:46,750 --> 00:35:54,279
თუ ხე შეადგენს შეადგენს null, არის N
ამ ხე თუ არა ამ ხეს?

762
00:35:54,279 --> 00:35:55,070
ეს არ შეიძლება იყოს, არა?

763
00:35:55,070 --> 00:35:56,870
თუ მე ვარ წარსული null,
იქ არაფერია.

764
00:35:56,870 --> 00:35:59,230
მე შეიძლება ასევე მხოლოდ
ბრმად ამბობენ დაბრუნების ცრუ.

765
00:35:59,230 --> 00:36:04,050
თუ მაძლევს არაფერი, მე ნამდვილად ვერ
მოძიების ნებისმიერი რაოდენობის N. ასე რომ, რა შეიძლება მე

766
00:36:04,050 --> 00:36:04,750
შეამოწმეთ ახლა?

767
00:36:04,750 --> 00:36:12,830
მე ვაპირებ ვთქვა ასევე სხვა თუ N არის
ნაკლებია, ვიდრე რაც at ხე კვანძის

768
00:36:12,830 --> 00:36:16,300
რომ მე უკვე გადასცა N ღირებულება.

769
00:36:16,300 --> 00:36:20,270
სხვა სიტყვებით, თუ ნომერი ვარ
ეძებს, N, ნაკლებია კვანძის

770
00:36:20,270 --> 00:36:21,340
რომ მე ეძებს.

771
00:36:21,340 --> 00:36:23,190
და კვანძის ვეძებ
განთავსებულია ეწოდება ხე,

772
00:36:23,190 --> 00:36:26,370
და გავიხსენოთ წინა მაგალითი
მისაღებად საათზე ღირებულების მაჩვენებელი,

773
00:36:26,370 --> 00:36:28,310
მე გამოიყენოთ arrow ნოტაცია.

774
00:36:28,310 --> 00:36:35,960
ასე რომ, თუ N ნაკლებია, ვიდრე ხე arrow
N, მინდა კონცეპტუალურად წასვლა მარცხენა.

775
00:36:35,960 --> 00:36:38,590
როგორ შემიძლია გამოხატული ძიების დარჩა?

776
00:36:38,590 --> 00:36:41,560
იყოს ნათელი, თუ ეს
სურათი კითხვა,

777
00:36:41,560 --> 00:36:44,612
და მე უკვე გავიდა, რომ უმაღლეს
arrow, რომელიც მიუთითებს, ქვემოთ.

778
00:36:44,612 --> 00:36:45,570
ეს არის ჩემი ხე მაჩვენებელი.

779
00:36:45,570 --> 00:36:48,060
მე მიუთითებს ძირი ხე.

780
00:36:48,060 --> 00:36:52,100
და ვეძებ ვთქვათ,
ნომერი 44, თვითნებურად.

781
00:36:52,100 --> 00:36:55,300
44-ზე ნაკლები და
აღემატება 55 აშკარად?

782
00:36:55,300 --> 00:36:56,360
ასე რომ, ეს ნაკლები.

783
00:36:56,360 --> 00:36:58,760
ასე რომ, თუ პირობა ვრცელდება.

784
00:36:58,760 --> 00:37:03,981
ასე რომ, კონცეპტუალურად, რას მინდა
ძიება მომდევნო თუ ვეძებ 44?

785
00:37:03,981 --> 00:37:04,480
ჰო?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> სწორედ, მე მინდა
ძიება მარცხენა ბავშვი,

788
00:37:11,100 --> 00:37:12,789
ან მარცხენა sub-tree ამ სურათს.

789
00:37:12,789 --> 00:37:14,830
და ფაქტობრივად, ნება მომეცით მეშვეობით
სურათზე ქვემოთ აქ

790
00:37:14,830 --> 00:37:17,770
მხოლოდ ერთი წუთით, მას შემდეგ, რაც
მე არ შემიძლია ნულიდან გარეთ.

791
00:37:17,770 --> 00:37:21,150
თუ მე აქ 55 და
მე ვიცი, რომ ღირებულება 44

792
00:37:21,150 --> 00:37:23,180
ვეძებ არის
მარცხენა, ეს არის სახის

793
00:37:23,180 --> 00:37:26,010
მოსწონს გაწყვეტა სატელეფონო წიგნი
ნახევარი ან tearing ხე ნახევარი.

794
00:37:26,010 --> 00:37:29,660
მე აღარ აინტერესებს
მთელი ამ ნახევარი ხე.

795
00:37:29,660 --> 00:37:33,270
და მაინც, საინტერესოა იმ თვალსაზრისით,
სტრუქტურა, ეს რაღაც აქ, რომ

796
00:37:33,270 --> 00:37:36,682
იწყება 33, რომ თავად
არის ორობითი ძებნა ხე.

797
00:37:36,682 --> 00:37:39,890
მე ვთქვი, სიტყვა რეკურსიული ადრე, რადგან
მართლაც ეს არის მონაცემთა სტრუქტურა, რომელიც

798
00:37:39,890 --> 00:37:41,707
ზოგადად არის რეკურსიული.

799
00:37:41,707 --> 00:37:44,540
თქვენ შეიძლება ჰქონდეს ხე, რომელიც ამ
დიდი, მაგრამ ყველა მისი შვილები

800
00:37:44,540 --> 00:37:46,870
წარმოადგენს ხის უბრალოდ ცოტა პატარა.

801
00:37:46,870 --> 00:37:50,910
იმის ნაცვლად, რომ ის, რომ ბაბუის
ან ბებიას, ახლა ეს მხოლოდ დედა

802
00:37:50,910 --> 00:37:54,300
or-- მე ვერ ვთქვა, არ დედა
ან მამა, ეს იქნება უცნაური.

803
00:37:54,300 --> 00:37:59,000
იმის ნაცვლად, რომ ორი შვილი იქ
იქნება, როგორც ძმა და ძმა.

804
00:37:59,000 --> 00:38:01,120
ახალი თაობის ოჯახის ხე.

805
00:38:01,120 --> 00:38:02,900
მაგრამ სტრუქტურულად, ეს იმავე იდეას.

806
00:38:02,900 --> 00:38:06,790
და აღმოჩნდება, რომ მაქვს ფუნქცია
რომელიც მე შეგიძლიათ მოძებნოთ ორობითი ძებნა

807
00:38:06,790 --> 00:38:07,290
ხე.

808
00:38:07,290 --> 00:38:08,680
მას უწოდებენ ძებნა.

809
00:38:08,680 --> 00:38:17,870
ვეძებ N ხე arrow მარცხენა
სხვაგან თუ N მეტია მნიშვნელობა

810
00:38:17,870 --> 00:38:18,870
რომ მე გაკეთებული.

811
00:38:18,870 --> 00:38:20,800
55 ამბავი მომენტში წინ.

812
00:38:20,800 --> 00:38:23,780
მაქვს ფუნქცია მოუწოდა
ძებნა, რომელიც მე შემიძლია უბრალოდ

813
00:38:23,780 --> 00:38:29,660
გაივლის N და რეკურსიული ძიება
ქვე-ხე და მხოლოდ დაბრუნების

814
00:38:29,660 --> 00:38:30,620
რაც არ უნდა, რომ პასუხი.

815
00:38:30,620 --> 00:38:33,530
სხვაგან მოხვდით გარკვეული საბოლოო ბაზის შემთხვევაში აქ.

816
00:38:33,530 --> 00:38:35,310
>> რა არის საბოლოო შემთხვევაში?

817
00:38:35,310 --> 00:38:36,570
ხე ან null.

818
00:38:36,570 --> 00:38:39,980
ღირებულება მე არც ეძებენ
ნაკლებია, ვიდრე ან უფრო მეტი, ვიდრე

819
00:38:39,980 --> 00:38:42,610
ან ტოლია იგი.

820
00:38:42,610 --> 00:38:44,750
და მე ვერ ვიტყვი, თანაბარი
თანაბარი, მაგრამ ლოგიკურად ეს

821
00:38:44,750 --> 00:38:46,500
ექვივალენტი უბრალოდ ვამბობ, სხვა აქ.

822
00:38:46,500 --> 00:38:49,150
ამიტომ ჭეშმარიტი არის, თუ როგორ მე რაღაც.

823
00:38:49,150 --> 00:38:51,710
ასე რომ, იმედია, ეს არის
კიდევ უფრო მყარი მაგალითად

824
00:38:51,710 --> 00:38:54,900
ვიდრე სულელური სიგმა ფუნქცია
ჩვენ გავაკეთეთ რამდენიმე ლექციები უკან,

825
00:38:54,900 --> 00:38:58,360
სადაც იგი იყო ისეთივე მარტივი მარყუჟის
ითვლიან up ყველა ნომრები ერთი

826
00:38:58,360 --> 00:39:02,390
ნ აქ მონაცემები სტრუქტურა
რომ თავად არის რეკურსიული

827
00:39:02,390 --> 00:39:07,050
განსაზღვრული და რეკურსიული შედგენილი, ახლა ჩვენ
აქვს უნარი გამოხატოს საკუთარი თავი

828
00:39:07,050 --> 00:39:09,780
ამ კოდი, რომელიც თავად არის რეკურსიული.

829
00:39:09,780 --> 00:39:12,580
ასე რომ, ეს არის ზუსტად იგივე კოდი აქ.

830
00:39:12,580 --> 00:39:14,400
>> ასე რომ, სხვა რა პრობლემები შეიძლება ჩვენ მოგვარება?

831
00:39:14,400 --> 00:39:18,160
ასე სწრაფად ნაბიჯი დაშორებით
ხეები მხოლოდ ერთი წუთით.

832
00:39:18,160 --> 00:39:20,130
აქ არის, ვთქვათ, გერმანიის დროშა.

833
00:39:20,130 --> 00:39:22,020
და იქ აშკარად
ნიმუში ამ დროშით.

834
00:39:22,020 --> 00:39:23,811
და არსებობს უამრავი
დროშები მსოფლიოს, რომ

835
00:39:23,811 --> 00:39:27,560
როგორც მარტივი, როგორც ამ თვალსაზრისით
მათი ფერები და შაბლონებს.

836
00:39:27,560 --> 00:39:31,930
მაგრამ ვფიქრობ, რომ ეს ინახება როგორც
.GIF, ან JPEG, ან bitmap, ან ping,

837
00:39:31,930 --> 00:39:34,240
ნებისმიერი გრაფიკული ფაილის ფორმატი
რომლითაც თქვენ იცნობს,

838
00:39:34,240 --> 00:39:36,460
ზოგიერთი რომელიც ჩვენ
სათამაშო in Pset4.

839
00:39:36,460 --> 00:39:41,550
ეს არ ჩანს იმასაც შესანახად
შავი pixel, შავი pixel, შავი pixel,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, მთელი bunch
შავი პიქსელი პირველად scanline,

841
00:39:44,790 --> 00:39:47,430
ან ზედიზედ, შემდეგ მთელი bunch
იგივე, მაშინ მთელი bunch

842
00:39:47,430 --> 00:39:49,530
იგივე, და შემდეგ
მთელი bunch წითელი პიქსელი,

843
00:39:49,530 --> 00:39:53,020
წითელი პიქსელი, წითელი პიქსელი, შემდეგ მთელი
რამოდენიმე ყვითელი პიქსელი, ყვითელი, არა?

844
00:39:53,020 --> 00:39:55,050
>> არსებობს ასეთი არაეფექტურობას აქ.

845
00:39:55,050 --> 00:39:59,040
როგორ დაახასიათებდით ინტუიციურად
შეკუმშოს გერმანიის დროშა

846
00:39:59,040 --> 00:40:01,320
თუ ახორციელებს, როგორც ფაილი?

847
00:40:01,320 --> 00:40:04,940
Like რა ინფორმაციას ჩვენ არ
გადაიტვირთოთ შენახვა დისკზე, რათა

848
00:40:04,940 --> 00:40:08,040
შემცირება ჩვენი ფაილი ზომა მოსწონს
მეგაბაიტი რომ kilobyte, რაღაც

849
00:40:08,040 --> 00:40:09,430
პატარა?

850
00:40:09,430 --> 00:40:13,130
რაში მდგომარეობს redundancy
აქ უნდა იყოს ნათელი?

851
00:40:13,130 --> 00:40:13,880
რა შეგიძლიათ გააკეთოთ?

852
00:40:13,880 --> 00:40:14,380
ჰო?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
ზუსტად.

855
00:40:21,970 --> 00:40:24,550
რატომ არ ვიდრე მახსოვს
ფერი ყოველ darn pixel

856
00:40:24,550 --> 00:40:28,200
ისევე, როგორც თქვენ აკეთებთ Pset4
ერთად bitmap ფორმატში,

857
00:40:28,200 --> 00:40:32,060
რატომ არ მხოლოდ წარმოადგენს
leftmost სვეტი პიქსელი, მაგალითად

858
00:40:32,060 --> 00:40:35,370
რამოდენიმე შავი პიქსელი, bunch
წითელი და რამოდენიმე ყვითელი,

859
00:40:35,370 --> 00:40:39,210
და შემდეგ უბრალოდ რატომღაც encode
იდეა ვიმეორებ ამ 100 ჯერ

860
00:40:39,210 --> 00:40:41,020
ან გაიმეოროს ეს 1000-ჯერ?

861
00:40:41,020 --> 00:40:43,430
სად 100 და 1000 არის
უბრალოდ რიცხვი, ასე რომ თქვენ

862
00:40:43,430 --> 00:40:47,290
შეუძლია მიიღოს away მასთან მხოლოდ ერთი ნომერი
ნაცვლად ასობით და ათასობით

863
00:40:47,290 --> 00:40:48,270
დამატებითი პიქსელი.

864
00:40:48,270 --> 00:40:50,990
და მართლაც, ის, თუ როგორ
შეიძლება შეკუმშოს გერმანიის დროშა.

865
00:40:50,990 --> 00:40:51,490
და

866
00:40:51,490 --> 00:40:53,470
ახლა, რაც შეეხება საფრანგეთის დროშა?

867
00:40:53,470 --> 00:40:58,930
და ცოტა გარკვეული
ფსიქიკური განხორციელება, რომელიც დროშა

868
00:40:58,930 --> 00:41:01,040
შეიძლება შეკუმშვას უფრო დისკზე?

869
00:41:01,040 --> 00:41:05,720
გერმანიის დროშა ან ფრანგული
დროშა, თუ ავიღებთ, რომ მიდგომა?

870
00:41:05,720 --> 00:41:08,490
გერმანიის დროშა, იმიტომ, რომ იქ
უფრო ჰორიზონტალური redundancy.

871
00:41:08,490 --> 00:41:12,190
და დიზაინი, მრავალი გრაფიკული ფაილი
ფორმატების მართლაც მუშაობა, როგორც სკანირების ხაზები

872
00:41:12,190 --> 00:41:12,830
ჰორიზონტალურად.

873
00:41:12,830 --> 00:41:14,674
მათ შეეძლოთ მუშაობა
ვერტიკალურად, უბრალოდ კაცობრიობის

874
00:41:14,674 --> 00:41:17,090
გადაწყვიტა წლის წინ, რომ ჩვენ
ზოგადად ვფიქრობ, რამ row

875
00:41:17,090 --> 00:41:18,880
მიერ ზედიზედ ნაცვლად სვეტი მიერ სვეტი.

876
00:41:18,880 --> 00:41:20,820
ასე რომ, მართლაც, თუ თქვენ
შევხედოთ ფაილი

877
00:41:20,820 --> 00:41:24,670
ზომა გერმანიის დროშა და საფრანგეთის
დროშა, ასე რომ სანამ რეზოლუცია

878
00:41:24,670 --> 00:41:27,530
იგივე, იგივე სიგანე
და სიმაღლე, ამ ერთი

879
00:41:27,530 --> 00:41:31,580
აქ იქნება უფრო დიდი, იმიტომ, რომ თქვენ
უნდა გავიმეოროთ თავს სამჯერ.

880
00:41:31,580 --> 00:41:35,570
თქვენ უნდა მიუთითოთ ლურჯი, განმეორებითი
თავს, თეთრი, ვიმეორებ თავს, წითელი,

881
00:41:35,570 --> 00:41:36,740
ვიმეორებ თავს.

882
00:41:36,740 --> 00:41:39,000
თქვენ არ შეგიძლიათ უბრალოდ წავიდეთ ყველა
გზა მარჯვნივ.

883
00:41:39,000 --> 00:41:41,200
და როგორც განზე, რათა
გარკვევა შეკუმშვის

884
00:41:41,200 --> 00:41:43,910
ყველგან არის, თუ ეს
ოთხი ფარგლებში საწყისი ვიდეოში თქვენ

885
00:41:43,910 --> 00:41:45,890
ალბათ გახსოვთ, რომ ფილმი
ან ვიდეო ზოგადად

886
00:41:45,890 --> 00:41:47,286
ისევე როგორც 29 ან 30 კადრი წამში.

887
00:41:47,286 --> 00:41:50,410
ეს იგივეა, ცოტა flip წიგნი, სადაც თქვენ
უბრალოდ ვხედავ სურათი, სურათი, სურათი, სურათი,

888
00:41:50,410 --> 00:41:54,410
სურათი უბრალოდ სუპერ სწრაფი, ასე რომ ჰგავს
მსახიობები ეკრანზე მივდივართ.

889
00:41:54,410 --> 00:41:57,130
აი Bumble Bee on
თავზე ყვავილების თაიგული.

890
00:41:57,130 --> 00:41:59,790
მიუხედავად იმისა, რომ ეს შეიძლება იყოს სახის
იმისთვის, რომ ვხედავ, ერთი შეხედვით,

891
00:41:59,790 --> 00:42:04,020
ერთადერთი, რაც მოძრაობს
ეს ფილმი არის bee.

892
00:42:04,020 --> 00:42:06,880
>> რა არის მითუმეტეს შესახებ შენახვის
ვიდეო uncompressed?

893
00:42:06,880 --> 00:42:11,420
ეს არის სახის ნარჩენების შესანახად ვიდეო
ოთხი თითქმის იდენტური სურათები რომ

894
00:42:11,420 --> 00:42:13,670
განსხვავდება მხოლოდ იმდენად, რამდენადაც, სადაც ფუტკარი.

895
00:42:13,670 --> 00:42:16,280
თქვენ შეგიძლიათ გადაყარეთ ყველაზე
ამ ინფორმაციას,

896
00:42:16,280 --> 00:42:20,190
და მახსოვს მხოლოდ, მაგალითად,
პირველი ჩარჩო და ბოლო ფარგლებში,

897
00:42:20,190 --> 00:42:22,180
გასაღები ფარგლებში, თუ თქვენ
ოდესმე მოისმინა სიტყვა,

898
00:42:22,180 --> 00:42:24,337
და მხოლოდ შესანახად
შუა, სადაც ფუტკრის არის.

899
00:42:24,337 --> 00:42:26,170
და თქვენ არ უნდა
შესანახად ყველა ვარდისფერი,

900
00:42:26,170 --> 00:42:28,330
და ლურჯი და
მწვანე ღირებულებები ისევე.

901
00:42:28,330 --> 00:42:31,200
ასე რომ, ეს არის ის, რომ მხოლოდ იმას, რომ
შეკუმშვის არის ყველგან.

902
00:42:31,200 --> 00:42:34,900
ეს ტექნიკა, ჩვენ ხშირად იყენებენ
ან თავისთავად ამ დღეებში.

903
00:42:34,900 --> 00:42:38,750
>> მაგრამ, როგორ უნდა შეკუმშოს ტექსტი?

904
00:42:38,750 --> 00:42:40,450
როგორ დადიხართ შესახებ compressing ტექსტი?

905
00:42:40,450 --> 00:42:45,410
ისე, თითოეული პერსონაჟი
ASCII არის ერთი ბაიტი, რვა ბიტი.

906
00:42:45,410 --> 00:42:47,360
და ეს არის უსარგებლო, უფლება?

907
00:42:47,360 --> 00:42:51,160
იმის გამო, რომ თქვენ ალბათ ტიპი
და E და მე და O და U ბევრი

908
00:42:51,160 --> 00:42:55,270
უფრო ხშირად, ვიდრე, როგორც W ან Q და Z,
დამოკიდებულია ენაზე, რომელიც

909
00:42:55,270 --> 00:42:56,610
თქვენ წერა რა თქმა უნდა.

910
00:42:56,610 --> 00:42:59,600
ასე რომ, რატომ ვართ გამოყენებით
რვა ბიტი ყველა წერილი,

911
00:42:59,600 --> 00:43:02,040
მათ შორის, სულ ცოტა
პოპულარული წერილები, უფლება?

912
00:43:02,040 --> 00:43:05,300
რატომ არ გამოიყენოს ნაკლები ბიტი
სუპერ პოპულარული წერილები,

913
00:43:05,300 --> 00:43:07,760
მოსწონს E, რამ იცი,
პირველი Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
და მეტი ბიტი
ნაკლებად პოპულარული წერილები?

915
00:43:10,450 --> 00:43:10,950
რატომ?

916
00:43:10,950 --> 00:43:13,130
იმიტომ, რომ ჩვენ უბრალოდ აპირებს
მათი გამოყენება ნაკლებად ხშირად.

917
00:43:13,130 --> 00:43:15,838
>> ისე, გამოდის, რომ იქ
იყო მცდელობა გააკეთა ამის გაკეთება.

918
00:43:15,838 --> 00:43:18,630
და თუ გავიხსენებთ კლასის
სკოლა და საშუალო სკოლა, Morse კოდი.

919
00:43:18,630 --> 00:43:20,400
Morse კოდი აქვს წერტილები
და dashes, რომელიც შეიძლება იყოს

920
00:43:20,400 --> 00:43:24,270
გადამდები გასწვრივ მავთულხლართების როგორც
ხმები ან სიგნალები გარკვეული.

921
00:43:24,270 --> 00:43:25,930
მაგრამ Morse კოდი სუპერ სუფთა.

922
00:43:25,930 --> 00:43:29,010
ეს არის სახის ორობითი სისტემა
რომ თქვენ გაქვთ წერტილები და dashes.

923
00:43:29,010 --> 00:43:30,977
მაგრამ თუ ხედავთ, მაგალითად, ორი წერტილი.

924
00:43:30,977 --> 00:43:33,810
ან თუ თქვენ ფიქრობთ, რომ ოპერატორი
ვინც მიდის, როგორც beep, beep, beep,

925
00:43:33,810 --> 00:43:36,760
beep, დარტყმის ცოტა გამოიწვევს
რომ აგზავნის სიგნალს,

926
00:43:36,760 --> 00:43:40,360
თუ თქვენ, მიმღები, იღებს ორ
წერტილები, რა გაგზავნა არ მიიღეთ?

927
00:43:40,360 --> 00:43:43,490
სრულიად უკანონო.

928
00:43:43,490 --> 00:43:44,450
>> მე?

929
00:43:44,450 --> 00:43:45,060
მე?

930
00:43:45,060 --> 00:43:47,500
ან რა ამაზე და მე

931
00:43:47,500 --> 00:43:49,570
იქნებ ეს მხოლოდ ორი E უფლება?

932
00:43:49,570 --> 00:43:52,480
ასე რომ, ეს პრობლემა
საქართველოს decodability ერთად Morse

933
00:43:52,480 --> 00:43:54,890
კოდი, რომლის დროსაც, თუ
პირი გაგზავნის თქვენ გაგზავნა

934
00:43:54,890 --> 00:43:59,510
რეალურად პაუზებით ასე რომ თქვენ შეგიძლიათ დაალაგოთ
ვხედავ ან მოისმენს ხარვეზები შორის წერილები,

935
00:43:59,510 --> 00:44:02,990
ეს არ არის საკმარისი მხოლოდ
გააგზავნოთ ნაკადი zeros და პირობა,

936
00:44:02,990 --> 00:44:05,610
ან წერტილების და dashes,
იმიტომ, რომ იქ გაურკვევლობა.

937
00:44:05,610 --> 00:44:08,640
E არის ერთ dot, ასე რომ, თუ თქვენ
იხილეთ ორი წერტილი ან მოისმინოს ორი წერტილი,

938
00:44:08,640 --> 00:44:11,254
შესაძლოა, ეს ორი E ან შესაძლოა ეს ერთი I.

939
00:44:11,254 --> 00:44:13,670
ასე რომ, ჩვენ გვჭირდება სისტემა, რომელიც არის
ცოტა უფრო ჭკვიანი, ვიდრე.

940
00:44:13,670 --> 00:44:16,851
ასე რომ, ერთი კაცი, სახელად Huffman წლის
წინ გამოვიდა სწორედ ეს არის.

941
00:44:16,851 --> 00:44:18,600
ასე რომ, ჩვენ უბრალოდ აპირებს
მიიღოს სწრაფი შეხედვით

942
00:44:18,600 --> 00:44:20,114
თუ როგორ ხეები გერმანე ეს.

943
00:44:20,114 --> 00:44:22,530
ვარაუდობენ, რომ ეს არის რაღაც
სულელური გაგზავნა გსურთ გააგზავნოთ,

944
00:44:22,530 --> 00:44:26,342
შედგება მხოლოდ A, B, C-ის D's და E ს,
მაგრამ არსებობს ბევრი redundancy აქ.

945
00:44:26,342 --> 00:44:27,550
ეს არ ნიშნავს, რომ ინგლისური.

946
00:44:27,550 --> 00:44:28,341
ეს არ არის დაშიფრული.

947
00:44:28,341 --> 00:44:30,540
ეს უბრალოდ სულელური გაგზავნა
უამრავი განმეორება.

948
00:44:30,540 --> 00:44:34,010
ასე რომ, თუ თქვენ ნამდვილად ითვლიან out ყველა
ა-ს, B- ს, C- ს, D's და E ს, აქ

949
00:44:34,010 --> 00:44:34,890
სიხშირე.

950
00:44:34,890 --> 00:44:37,800
20% ასო
ა-ს, 45% ასო

951
00:44:37,800 --> 00:44:39,660
არიან E, და სამი სხვა სიხშირეზე.

952
00:44:39,660 --> 00:44:41,960
ჩვენ დათვლილი up there ხელით
და უბრალოდ გააკეთა მათემატიკის.

953
00:44:41,960 --> 00:44:44,579
>> გამოდის, რომ
Huffman, რამდენიმე ხნის წინ,

954
00:44:44,579 --> 00:44:46,620
მიხვდა, რომ, თქვენ იცით,
რა, თუ დავიწყებ შენობა

955
00:44:46,620 --> 00:44:51,172
ხე, ან ტყის ხეების, თუ გნებავთ,
ასეთია, მე შემიძლია ამის შემდეგ.

956
00:44:51,172 --> 00:44:53,880
მე ვაპირებ, რათა კვანძის ყოველ
წერილებს, რომ მე აინტერესებს

957
00:44:53,880 --> 00:44:55,530
და მე ვაპირებ შესანახად
შიგნით რომ კვანძის

958
00:44:55,530 --> 00:44:58,610
სიხშირეები როგორც მცურავი წერტილი
ღირებულება, ან თქვენ შეიძლება გამოიყენოთ ეს N, ძალიან,

959
00:44:58,610 --> 00:45:00,210
მაგრამ ჩვენ უბრალოდ გამოიყენოთ float აქ.

960
00:45:00,210 --> 00:45:03,100
და ალგორითმი, რომელიც
მან შემოგვთავაზა, რომ თქვენ

961
00:45:03,100 --> 00:45:07,210
მიიღოს ამ ტყეში ერთი კვანძის
ხეები, ასე სუპერ მოკლე ხეები,

962
00:45:07,210 --> 00:45:11,920
და თქვენ დაიწყოს დამაკავშირებელი მათ
ახალი ჯგუფები, ახალი მშობლები, თუ გნებავთ.

963
00:45:11,920 --> 00:45:16,150
და თქვენ ამ არჩევით
ორი პატარა სიხშირეზე დროს.

964
00:45:16,150 --> 00:45:18,110
ამიტომ მე მივიღე 10% და 10%.

965
00:45:18,110 --> 00:45:19,090
მე შექმნა ახალი კვანძის.

966
00:45:19,090 --> 00:45:20,910
მე მოვუწოდებ ახალი კვანძის 20%.

967
00:45:20,910 --> 00:45:22,750
>> რომელი ორი კვანძების მე გაერთიანდება შემდეგი?

968
00:45:22,750 --> 00:45:23,810
ეს ცოტა ბუნდოვანია.

969
00:45:23,810 --> 00:45:26,643
ასე რომ, არსებობს რამდენიმე კუთხეში შემთხვევებში
განიხილოს, მაგრამ შენარჩუნება რამ საკმაოდ,

970
00:45:26,643 --> 00:45:29,300
მე ვაპირებ აირჩიოს 20% -
მე ახლა იგნორირება შვილი.

971
00:45:29,300 --> 00:45:33,640
მე ვაპირებ აირჩიოს 20% და
15% და დავხატოთ ორი ახალი კიდეები.

972
00:45:33,640 --> 00:45:35,624
და ახლა, რომელიც ორ კვანძების
შემიძლია ლოგიკურად აერთიანებს?

973
00:45:35,624 --> 00:45:38,540
იგნორირება ყველა ბავშვები, ყველა
შვილიშვილი, უბრალოდ შევხედოთ ფესვები

974
00:45:38,540 --> 00:45:39,070
ახლა.

975
00:45:39,070 --> 00:45:42,220
რომელი ორი კვანძების შემიძლია უსიამოვნოა ერთად?

976
00:45:42,220 --> 00:45:44,530
Point ორი და 0.35.

977
00:45:44,530 --> 00:45:45,890
დავხატავ ორი ​​ახალი კიდეები.

978
00:45:45,890 --> 00:45:47,570
და მაშინ მე მხოლოდ ერთი მარცხენა.

979
00:45:47,570 --> 00:45:48,650
ასე რომ, აქ ხე.

980
00:45:48,650 --> 00:45:51,160
და ეს უკვე შედგენილი განზრახ
გამოიყურება სახის საკმაოდ,

981
00:45:51,160 --> 00:45:55,870
მაგრამ შეამჩნია, რომ კიდეები აქვს
ასევე უკვე შეაფასა, ნულოვანი და ერთი.

982
00:45:55,870 --> 00:45:59,510
ასე რომ, ყველა მარცხენა კიდეები ნულოვანი
თვითნებურად, მაგრამ თანმიმდევრულად.

983
00:45:59,510 --> 00:46:01,170
ყველა უფლება კიდეები მიიჩნიეს.

984
00:46:01,170 --> 00:46:05,070
>> ასე რომ, რა Hoffman შემოთავაზებული არის,
თუ გვინდა, რომ წარმოადგენს B,

985
00:46:05,070 --> 00:46:10,080
ვიდრე წარმოადგენს რაოდენობა 66, როგორც
ASCII რომელიც რვა მთელი ბიტი,

986
00:46:10,080 --> 00:46:13,360
თქვენ იცით, რა, უბრალოდ მაღაზიაში
ნიმუში ნულოვანი, ნულოვანი, ნულოვანი,

987
00:46:13,360 --> 00:46:17,030
ნულოვანი, იმიტომ, რომ ის გზას
ჩემი ხე, ბატონი Huffman ნაძვის ხე,

988
00:46:17,030 --> 00:46:18,600
ფოთოლი root.

989
00:46:18,600 --> 00:46:20,970
თუ გსურთ შესანახად
E განსხვავებით, არ

990
00:46:20,970 --> 00:46:26,290
გაუგზავნე რვა ბიტი, რომ წარმოადგენს E.
ამის ნაცვლად, გაგზავნას რა ნიმუში ბიტი?

991
00:46:26,290 --> 00:46:26,890
ერთ-ერთი.

992
00:46:26,890 --> 00:46:30,410
და რა არის ლამაზი ამ არის
რომ E არის ყველაზე პოპულარული წერილი,

993
00:46:30,410 --> 00:46:32,340
და თქვენ იყენებთ
უმოკლეს კოდი იგი.

994
00:46:32,340 --> 00:46:34,090
შემდეგი ყველაზე პოპულარული
წერილი ჰგავს ეს

995
00:46:34,090 --> 00:46:37,380
იყო A. ასე რომ რამდენი ბიტი
მას ასევე არ ვთავაზობ, რომ?

996
00:46:37,380 --> 00:46:38,270
ნულოვანი, ერთი.

997
00:46:38,270 --> 00:46:41,060
>> და რადგან იგი განხორციელდა
რადგან ეს ხე, ახლა

998
00:46:41,060 --> 00:46:43,350
მიადევნე თვალი ითვალისწინებს იქ
გაურკვევლობა როგორც Morse

999
00:46:43,350 --> 00:46:46,090
კოდი, იმიტომ, რომ ყველა
წერილები აინტერესებს

1000
00:46:46,090 --> 00:46:48,780
დასასრულს ამ კიდეები.

1001
00:46:48,780 --> 00:46:50,580
ასე რომ, მხოლოდ ერთი
განაცხადის ხე.

1002
00:46:50,580 --> 00:46:52,538
ეს is-- და მე ტალღის
ჩემი მხრივ ეს, თუ როგორ

1003
00:46:52,538 --> 00:46:55,570
შეიძლება განახორციელოს ეს როგორც C სტრუქტურა.

1004
00:46:55,570 --> 00:46:58,260
ჩვენ უბრალოდ უნდა დააკავშიროთ
სიმბოლო, როგორც char,

1005
00:46:58,260 --> 00:46:59,910
და სიხშირე მარცხენა და მარჯვენა.

1006
00:46:59,910 --> 00:47:02,510
მაგრამ მოდით შევხედოთ ორი
საბოლოო მაგალითები, რომ თქვენ

1007
00:47:02,510 --> 00:47:06,070
საკმაოდ იცნობს მას შემდეგ, რაც
ვიქტორინა ნულოვანი პრობლემა მითითებული ხუთ.

1008
00:47:06,070 --> 00:47:09,210
>> ასე რომ, არსებობს მონაცემები სტრუქტურა
ცნობილია, როგორც hash მაგიდა.

1009
00:47:09,210 --> 00:47:12,247
და hash მაგიდა არის ერთგვარი
გაგრილებას, რომ მას აქვს თაიგულების.

1010
00:47:12,247 --> 00:47:14,830
და ვარაუდობენ, რომ იქ ოთხი თაიგულების
აქ, მხოლოდ ოთხი ცარიელი ფართები.

1011
00:47:14,830 --> 00:47:20,830
აი deck ბარათების, და აქ არის
კლუბი, ბარი, კლუბი, ბრილიანტები, კლუბი,

1012
00:47:20,830 --> 00:47:25,960
ბრილიანტები, შესვლა, ბრილიანტები,
clubs-- ასე რომ ეს არის შემთხვევითი.

1013
00:47:25,960 --> 00:47:30,330
გულები, hearts-- ასე რომ მე ვარ
bucketizing ყველა საშუალებებით აქ.

1014
00:47:30,330 --> 00:47:32,430
და hash მაგიდა საჭიროებების
შევხედოთ თქვენი input,

1015
00:47:32,430 --> 00:47:34,850
და შემდეგ დააყენოს ის გარკვეული
განათავსეთ საფუძველზე რას ვხედავ.

1016
00:47:34,850 --> 00:47:35,600
ეს ალგორითმი.

1017
00:47:35,600 --> 00:47:37,980
და მე გამოყენებით სუპერ
მარტივი ვიზუალური ალგორითმი.

1018
00:47:37,980 --> 00:47:40,030
უმძიმესი ნაწილი, რომელიც
დამახსოვრების რა სურათები იყო.

1019
00:47:40,030 --> 00:47:41,590
და მაშინ იქ ოთხი სულ რამ.

1020
00:47:41,590 --> 00:47:45,440
>> ახლა stacks იზრდება, რომელიც
არის მიზანმიმართული დიზაინი, რაც აქ.

1021
00:47:45,440 --> 00:47:46,540
მაგრამ რა შეიძლება გავაკეთო?

1022
00:47:46,540 --> 00:47:49,080
ასე რომ, რეალურად, აქ ჩვენ გვაქვს
რამოდენიმე ძველი სკოლა გამოცდა წიგნები.

1023
00:47:49,080 --> 00:47:51,240
ვარაუდობენ, რომ bunch of
სტუდენტები სახელები აქ.

1024
00:47:51,240 --> 00:47:52,570
აი დიდი hash მაგიდა.

1025
00:47:52,570 --> 00:47:54,867
იმის ნაცვლად, რომ ოთხი თაიგულების,
მე, ვთქვათ, 26.

1026
00:47:54,867 --> 00:47:57,950
და ჩვენ არ გვინდა, რომ ვისესხო 26
რამ გარედან [? Annenberg?], ასე

1027
00:47:57,950 --> 00:48:00,289
აქ არის ხუთი, რომელიც წარმოადგენს
მეშვეობით ზ და თუ მე

1028
00:48:00,289 --> 00:48:03,580
იხილეთ სტუდენტი, რომლის სახელი იწყება,
მე ვაპირებ დააყენოს მისი ინტელექტუალური არსებობს.

1029
00:48:03,580 --> 00:48:08,850
თუ ვინმე იწყება C, იქ,
A-- რეალურად, არ სურს ამის გაკეთება.

1030
00:48:08,850 --> 00:48:10,060
B მიდის აქ.

1031
00:48:10,060 --> 00:48:13,390
ასე რომ, მაქვს A, B და C. და
ახლა აქ არის კიდევ ერთი სტუდენტი.

1032
00:48:13,390 --> 00:48:16,212
მაგრამ თუ ეს hash მაგიდა
განხორციელდეს მასივი,

1033
00:48:16,212 --> 00:48:17,920
მე სახის ბრალია
ამ ეტაპზე, არა?

1034
00:48:17,920 --> 00:48:19,510
მე სახის უნდა დააყენოს ამ სადღაც.

1035
00:48:19,510 --> 00:48:24,380
>> ასე რომ, ერთი გზა მე შეუძლია გადაწყვიტოს ეს არის, ყველა
მარჯვნივ, დაკავებულია, B არის დაკავებული, C არის დაკავებული.

1036
00:48:24,380 --> 00:48:28,880
მე ვაპირებ, რომ მას დ ასე რომ,
პირველი, მე შემთხვევითი მყისიერი ხელმისაწვდომობის

1037
00:48:28,880 --> 00:48:31,064
თითოეულ თაიგულების სტუდენტებს.

1038
00:48:31,064 --> 00:48:33,230
მაგრამ ახლა ეს სახის გადადის
რაღაც წრფივი,

1039
00:48:33,230 --> 00:48:36,750
იმიტომ, რომ თუ მინდა მოვძებნო ვინმე
რომლის სახელი იწყება, მე შეამოწმეთ აქ.

1040
00:48:36,750 --> 00:48:38,854
მაგრამ თუ ეს არ არის ა
სტუდენტი ვეძებ,

1041
00:48:38,854 --> 00:48:41,520
ასეთი უნდა დაიწყოს შემოწმების
თაიგულების, რადგან ის, რაც მე

1042
00:48:41,520 --> 00:48:44,530
იყო ერთგვარი ხაზოვანი
გამოძიების მონაცემების სტრუქტურას.

1043
00:48:44,530 --> 00:48:47,710
სულელი გზას ვამბობ, უბრალოდ გამოიყურება
პირველად ხელმისაწვდომი გახსნა,

1044
00:48:47,710 --> 00:48:51,850
და, როგორც გეგმა B, ასე ვთქვათ,
ან გეგმა D ამ შემთხვევაში, ღირებულება

1045
00:48:51,850 --> 00:48:53,340
ამ ადგილას ნაცვლად.

1046
00:48:53,340 --> 00:48:56,470
ეს არის მხოლოდ იმიტომ, რომ, თუ თქვენ
მიიღო 26 ადგილას და სტუდენტებს

1047
00:48:56,470 --> 00:49:00,600
სახელით Q და Z, ან რაღაც
რომ, მინიმუმ თქვენ იყენებთ სივრცეში.

1048
00:49:00,600 --> 00:49:03,140
>> მაგრამ ჩვენ უკვე ჩანს მეტი
ჭკვიანი გადაწყვეტილებები აქ, არა?

1049
00:49:03,140 --> 00:49:04,870
რას იზამდით, ნაცვლად
თუ თქვენ გაქვთ შეჯახება?

1050
00:49:04,870 --> 00:49:06,670
თუ ორ ადამიანს აქვს
სახელი A, თუ რა

1051
00:49:06,670 --> 00:49:09,160
არ ყოფილა მსოფლიოს სასურველი სტუმარი გახდებით და უფრო
ინტუიციური გადაწყვეტა, ვიდრე უბრალოდ

1052
00:49:09,160 --> 00:49:12,840
აყენებს, სადაც D უნდა იყოს?

1053
00:49:12,840 --> 00:49:14,810
რატომ არ მე უბრალოდ წასვლა
გარეთ [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
როგორც malloc, ერთი კვანძის, ამას
აქ, და შემდეგ დააყენა, რომ სტუდენტი აქ.

1055
00:49:19,960 --> 00:49:22,120
ასე რომ, მე არსებითად
გარკვეული სახის მასივი,

1056
00:49:22,120 --> 00:49:25,590
ან იქნებ უფრო ელეგანტურად როგორც ჩვენ
დაწყებული დაინახოს უკავშირდება სიაში.

1057
00:49:25,590 --> 00:49:29,520
>> ასე რომ hash მაგიდა არის სტრუქტურა
რომ შეიძლება გამოიყურებოდეს ისევე, როგორც ეს,

1058
00:49:29,520 --> 00:49:33,900
მაგრამ უფრო ჭკვიანურად, თქვენ რაღაც მოუწოდა
ცალკე chaining, რომლის hash მაგიდა

1059
00:49:33,900 --> 00:49:38,340
უბრალოდ მასივი, თითოეული
რომლის ელემენტები არ არის ნომერი,

1060
00:49:38,340 --> 00:49:40,470
თავისთავად უკავშირდება სიაში.

1061
00:49:40,470 --> 00:49:45,080
ასე, რომ თქვენ სუპერ სწრაფი დაშვება
გადაწყვეტილების მიღებისას, სადაც hash თქვენი ღირებულების.

1062
00:49:45,080 --> 00:49:48,059
ჰგავს ბარათები მაგალითად,
მე მივიღე სუპერ სწრაფი გადაწყვეტილებები.

1063
00:49:48,059 --> 00:49:49,600
გულები მიდის აქ, ბრილიანტები მიდის აქ.

1064
00:49:49,600 --> 00:49:52,180
იგივე აქ, A მიდის აქ,
D მიდის აქ, B მიდის აქ.

1065
00:49:52,180 --> 00:49:55,740
ასე რომ, სუპერ სწრაფი look-ups, და თუ
თქვენ არ გადაეყარონ შემთხვევაში

1066
00:49:55,740 --> 00:49:59,429
სადაც თქვენ მოხვდით collisions, ორი
ადამიანი, ამავე სახელწოდების, ასევე მაშინ

1067
00:49:59,429 --> 00:50:00,970
თქვენ დავიწყო აკავშირებს მათ ერთად.

1068
00:50:00,970 --> 00:50:03,900
და იქნებ თქვენ შენარჩუნება მათ დალაგებულია
ალფავიტის მიხედვით, შესაძლოა, თქვენ არ.

1069
00:50:03,900 --> 00:50:05,900
მაგრამ მაინც, ახლა ჩვენ გვაქვს დინამიკას.

1070
00:50:05,900 --> 00:50:10,250
ასე რომ, ერთის მხრივ, ჩვენ გვაქვს სუპერ სწრაფი
მუდმივი, და სახის ხაზოვანი დრო

1071
00:50:10,250 --> 00:50:14,110
ჩართული, თუ ეს დაკავშირებული სიები
დაიწყოს მიიღოს ცოტა ხანი.

1072
00:50:14,110 --> 00:50:16,880
>> ასე რომ, ეს სახის სულელური,
geeky ხუმრობა წლის წინ.

1073
00:50:16,880 --> 00:50:19,590
ამავე CS50 hack-a-thon,
როდესაც სტუდენტები შემოწმება,

1074
00:50:19,590 --> 00:50:22,040
ზოგიერთი TF ან CA ყოველწლიურად
ფიქრობს, რომ ეს სასაცილო დაფასოებული

1075
00:50:22,040 --> 00:50:27,772
ნიშანი, როგორც ეს, სადაც იგი მხოლოდ
ნიშნავს თუ თქვენი სახელი იწყება A,

1076
00:50:27,772 --> 00:50:28,870
წავიდეთ ამ გზით.

1077
00:50:28,870 --> 00:50:31,110
თუ თქვენი სახელი იწყება
ერთად B, წასვლა ამას OK,

1078
00:50:31,110 --> 00:50:33,290
ეს სასაცილოა, შესაძლოა, შემდეგ სემესტრში.

1079
00:50:33,290 --> 00:50:36,420
მაგრამ არსებობს კიდევ ერთი
გზა ამით, ძალიან.

1080
00:50:36,420 --> 00:50:37,410
დავბრუნდებით რომ.

1081
00:50:37,410 --> 00:50:38,600
>> ასე რომ ეს სტრუქტურა.

1082
00:50:38,600 --> 00:50:40,420
და ეს არის ჩვენი ბოლო
სტრუქტურა, დღეს,

1083
00:50:40,420 --> 00:50:42,400
რომელიც რაღაც მოუწოდა trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, რომელიც რატომღაც მოკლე
კითხვის, მაგრამ ეს ე.წ. trie.

1085
00:50:47,140 --> 00:50:51,389
ამიტომ trie არის კიდევ ერთი საინტერესო
დარეგულირებაზე ბევრი იდეები.

1086
00:50:51,389 --> 00:50:52,930
ეს არის ხე, რომელიც ჩვენ ვნახეთ ადრე.

1087
00:50:52,930 --> 00:50:54,180
ეს არ არის ორობითი ძებნა ხე.

1088
00:50:54,180 --> 00:50:58,410
ეს ხე ნებისმიერი რაოდენობის შვილი,
მაგრამ თითოეული ბავშვების trie

1089
00:50:58,410 --> 00:51:00,090
მასივი.

1090
00:51:00,090 --> 00:51:04,790
მასივი ზომა, ვთქვათ, 26 ან იქნებ 27
თუ გვინდა, რომ მხარს ვუჭერთ hyphenated სახელები

1091
00:51:04,790 --> 00:51:06,790
ან ხაზს ხალხის სახელები.

1092
00:51:06,790 --> 00:51:08,280
>> ასე რომ, ეს არის მონაცემები სტრუქტურა.

1093
00:51:08,280 --> 00:51:10,290
და თუ გადავხედავთ ზემოდან
ქვედა, როგორიცაა, თუ

1094
00:51:10,290 --> 00:51:13,710
შეხედეთ ზევით კვანძის იქ, M, არის
მიუთითებს leftmost რამ არსებობს,

1095
00:51:13,710 --> 00:51:17,665
რომელიც შემდეგ A, X, W, E, L, L. ეს არის
უბრალოდ მონაცემები სტრუქტურა, რომელიც თვითნებურად

1096
00:51:17,665 --> 00:51:19,120
არის შენახვის ხალხის სახელები.

1097
00:51:19,120 --> 00:51:25,720
და მაქსველი ინახება მხოლოდ შემდეგი
გზა მასივი მასივი მასივი.

1098
00:51:25,720 --> 00:51:30,050
მაგრამ რა არის საოცარი trie არის
რომ, მაშინ, როდესაც უკავშირდება სიაში და კიდევ

1099
00:51:30,050 --> 00:51:34,520
მასივი, საუკეთესო ჩვენ ოდესმე მიღებული არის
ხაზოვანი დროს და ლოგარითმული დრო ეძებს

1100
00:51:34,520 --> 00:51:35,600
ვინმე up.

1101
00:51:35,600 --> 00:51:40,530
ამ მონაცემების სტრუქტურა trie, თუ
ჩემი მონაცემები სტრუქტურა აქვს ერთი სახელი და გვარი

1102
00:51:40,530 --> 00:51:43,720
და ვეძებ Maxwell, მე
აპირებთ პოულობენ მას საკმაოდ სწრაფად.

1103
00:51:43,720 --> 00:51:47,910
მე უბრალოდ ვეძებთ M-A-X-W-E-L-L. თუ
ამ მონაცემების სტრუქტურას, პირიქით,

1104
00:51:47,910 --> 00:51:51,830
თუ N მილიონი, თუ არ არის
მილიონი სახელები ამ მონაცემების სტრუქტურას,

1105
00:51:51,830 --> 00:51:57,100
Maxwell მაინც იქნება
discoverable შემდეგ მხოლოდ M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
ნაბიჯები.

1107
00:51:58,090 --> 00:52:01,276
და დავით დ-A-V-I-D ნაბიჯები.

1108
00:52:01,276 --> 00:52:03,400
სხვა სიტყვებით, აშენებს
მონაცემთა სტრუქტურა, რომელიც არის

1109
00:52:03,400 --> 00:52:07,240
მივიღე ყველა ამ მასივები, რაც
თავად მხარს ვუჭერთ წვდომის,

1110
00:52:07,240 --> 00:52:11,090
შემიძლია დაიწყოს ეძებს ხალხის
ასახელებს გამოყენებით დროის, რომ

1111
00:52:11,090 --> 00:52:14,340
პროპორციული არ არის რიცხვი
რამ მონაცემები სტრუქტურა,

1112
00:52:14,340 --> 00:52:16,330
როგორც მილიონი არსებული სახელები.

1113
00:52:16,330 --> 00:52:20,135
დროის სჭირდება ჩემთვის იპოვოს
M-A-X-W-E-L-L ამ მონაცემების სტრუქტურას

1114
00:52:20,135 --> 00:52:22,260
პროპორციული არა
ზომა მონაცემთა სტრუქტურა,

1115
00:52:22,260 --> 00:52:25,930
მაგრამ სიგრძეზე სახელი.

1116
00:52:25,930 --> 00:52:28,440
და რეალურად
სახელები ჩვენ ვეძებთ up

1117
00:52:28,440 --> 00:52:29,970
არასოდეს იქნება გიჟები ხანგრძლივი.

1118
00:52:29,970 --> 00:52:32,600
იქნებ ვინმეს აქვს 10 ხასიათი
ასახელებს, 20 ხასიათის სახელი.

1119
00:52:32,600 --> 00:52:33,900
ეს, რა თქმა სასრულ, არა?

1120
00:52:33,900 --> 00:52:37,110
არ არის ადამიანის დედამიწაზე, რომელიც
აქვს გრძელი შესაძლებელია სახელი,

1121
00:52:37,110 --> 00:52:39,920
მაგრამ ეს სახელი არის მუდმივი
მნიშვნელობა სიგრძე, არა?

1122
00:52:39,920 --> 00:52:41,980
იგი არ განსხვავდება ნებისმიერი გაგებით.

1123
00:52:41,980 --> 00:52:45,090
ასე რომ, ამ გზით, ჩვენ
მიღწეული მონაცემთა სტრუქტურა

1124
00:52:45,090 --> 00:52:47,800
რომ არის მუდმივი დრო სახეს-მდე.

1125
00:52:47,800 --> 00:52:50,670
ეს არ მიიღოს რიგი ნაბიჯები
დამოკიდებულია სიგრძე შეყვანა,

1126
00:52:50,670 --> 00:52:54,250
მაგრამ არა რაოდენობის სახელი
ამ მონაცემების სტრუქტურას.

1127
00:52:54,250 --> 00:52:58,700
ასე რომ, თუ ჩვენ რაოდენობის გაორმაგება სახელები
მომავალ წელს მილიარდი შეადგინა,

1128
00:52:58,700 --> 00:53:03,720
დასკვნა Maxwell აპირებს
ზუსტად იგივე რაოდენობის შვიდი ნაბიჯები

1129
00:53:03,720 --> 00:53:04,650
პოულობენ მას.

1130
00:53:04,650 --> 00:53:08,810
ასე რომ, ჩვენ, როგორც ჩანს, არ მიაღწია
ჩვენი წმინდა გრაალი ქრონომეტრაჟი.

1131
00:53:08,810 --> 00:53:10,860
>> ასე რომ, რამდენიმე სწრაფ განცხადებები.

1132
00:53:10,860 --> 00:53:11,850
ვიქტორინა ნულოვანი ახლოვდება.

1133
00:53:11,850 --> 00:53:14,600
უფრო, რომ, რა თქმა უნდა ვებ-
მომდევნო რამდენიმე დღის განმავლობაში.

1134
00:53:14,600 --> 00:53:17,120
ორშაბათს ლექცია, რომ ეს დღესასწაული
აქ ჰარვარდის ორშაბათს.

1135
00:53:17,120 --> 00:53:18,850
ეს არ არის New Haven,
ასე რომ, ჩვენ აღების კლასი

1136
00:53:18,850 --> 00:53:20,310
-დან New Haven ლექცია ორშაბათს.

1137
00:53:20,310 --> 00:53:22,550
ყველაფერი იქნება გადაღებული,
და ტრანსლირება, როგორც ყოველთვის,

1138
00:53:22,550 --> 00:53:24,900
მაგრამ მოდით, დღეს დასრულდება
30 მეორე კლიპი

1139
00:53:24,900 --> 00:53:26,910
სახელწოდებით "ღრმა ფიქრები"
მიერ Daven Farnham, რომელიც

1140
00:53:26,910 --> 00:53:30,850
იყო ინსპირირებული შარშან შაბათი
Night Live ის "ღრმა ფიქრები"

1141
00:53:30,850 --> 00:53:35,700
ჯეკ Handy, რომელიც
ახლა უნდა აზრი.

1142
00:53:35,700 --> 00:53:38,810
>> ფილმი: ახლა, "Deep
ფიქრები "მიერ Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash მაგიდასთან.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> დინამიკები 1: ყველა უფლება, რომ ის ახლა.

1147
00:53:47,660 --> 00:53:48,805
ჩვენ დავინახავთ, თქვენ მომავალ კვირას.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: იმისათვის, რომ ნახოთ ეს ქმედება.

1150
00:53:56,680 --> 00:53:58,304
მოდით შევხედოთ, რომ ახლა.

1151
00:53:58,304 --> 00:53:59,890
ასე რომ, ჩვენ გვაქვს დაუხარისხებელი მასივი.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, შეგიძლიათ წავიდეთ წინ და გადატვირთეთ
ეს მხოლოდ ერთი მეორე, გთხოვთ.

1153
00:54:04,860 --> 00:54:08,562
ყველა უფლება კამერები მოძრავი, ისე,
მოქმედება, როდესაც თქვენ მზად, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG ყველა უფლება, ასე რომ ჩვენ
აქ არის დაუხარისხებელი მასივი.

1155
00:54:11,020 --> 00:54:13,960
და მე ფერადი ყველა ელემენტები
წითელი მიუთითებს იმაზე, რომ ეს არის, ფაქტობრივად,

1156
00:54:13,960 --> 00:54:14,460
დაუხარისხებელი.

1157
00:54:14,460 --> 00:54:17,960
ასე რომ გავიხსენოთ, რომ პირველი, რასაც ვაკეთებთ
არის ჩვენ დასალაგებლად მარცხენა ნახევარში მასივი.

1158
00:54:17,960 --> 00:54:20,630
მაშინ ჩვენ დასალაგებლად მარჯვენა
ნახევარში მასივი.

1159
00:54:20,630 --> 00:54:22,830
და ya-da, ya-da, ya-da,
ჩვენ შერწყმა მათ ერთად.

1160
00:54:22,830 --> 00:54:24,520
და ჩვენ გვაქვს სრულიად დახარისხებული მასივი.

1161
00:54:24,520 --> 00:54:25,360
ასე რომ, თუ როგორ შერწყმა დალაგების მუშაობს.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, Whoa, Whoa,
დაჭრილი, დაჭრილი, დაჭრილი, დაჭრილი.

1163
00:54:27,109 --> 00:54:30,130
Doug, შეგიძლიათ არა მხოლოდ ya-da, ya-da,
ya-da, თქვენი გზა მეშვეობით შერწყმა დალაგების.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: მე უბრალოდ გააკეთეს.

1165
00:54:31,970 --> 00:54:32,832
ეს ჯარიმა.

1166
00:54:32,832 --> 00:54:33,540
ჩვენ კარგი წასვლა.

1167
00:54:33,540 --> 00:54:34,760
მოდით უბრალოდ შეინახოს მოძრავი.

1168
00:54:34,760 --> 00:54:35,380
ასე რომ, მაინც,

1169
00:54:35,380 --> 00:54:37,800
>> IAN თქვენ უნდა ავუხსნათ
ეს უფრო სრულად, ვიდრე.

1170
00:54:37,800 --> 00:54:39,999
ეს უბრალოდ არ არის საკმარისი.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, ჩვენ არ
უნდა დაბრუნდეს ერთი.

1172
00:54:41,790 --> 00:54:42,350
ეს ჯარიმა.

1173
00:54:42,350 --> 00:54:45,690
ასე რომ, მაინც, თუ ჩვენ გავაგრძელებთ merge--
იან, ჩვენ შუა გადაღება.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: მე ვიცი.

1175
00:54:46,612 --> 00:54:49,320
და ჩვენ არ შეგვიძლია უბრალოდ ya-da, ya-da,
ya-da, მთელი პროცესი.

1176
00:54:49,320 --> 00:54:52,200
თქვენ უნდა ავუხსნათ, თუ როგორ
ორ მხარეს უნდა გაერთიანდა.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: მაგრამ ჩვენ უკვე
განმარტა, თუ როგორ ორი sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: თქვენ უბრალოდ ნაჩვენები
მათ შერწყმა მასივი.

1179
00:54:55,321 --> 00:54:56,486
DOUG: მათ იციან პროცესში.

1180
00:54:56,486 --> 00:54:57,172
ისინი ჯარიმა.

1181
00:54:57,172 --> 00:54:58,380
ჩვენ წავიდა მას ათჯერ.

1182
00:54:58,380 --> 00:55:00,330
>> IAN თქვენ უბრალოდ გამოტოვებენ უფლება მას.

1183
00:55:00,330 --> 00:55:03,360
ჩვენ ვაპირებთ უკან ერთი, თქვენ
არ შეგიძლია ya-da, ya-da მას.

1184
00:55:03,360 --> 00:55:05,480
ყველა უფლება, უკან ერთი.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: მე უნდა დაბრუნდეს
ყველა სლაიდები?

1186
00:55:07,833 --> 00:55:08,332
ჩემი ღმერთი.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
ეს იგივეა, მეექვსე იან.

1189
00:55:13,004 --> 00:55:13,940
ეს ჯარიმა.

1190
00:55:13,940 --> 00:55:15,200
>> IAN ყველა უფლება.

1191
00:55:15,200 --> 00:55:16,590
თქვენ მზად?

1192
00:55:16,590 --> 00:55:17,400
შესანიშნავი.

1193
00:55:17,400 --> 00:55:18,950
აქცია.